Difference in answers in unordered_map and map

Блог пользователя zeref_dragoneel

Автор zeref_dragoneel, история, 9 лет назад, По-английски

http://codeforces.com/contest/512/problem/B

solution id : 12300691 and 12300696 http://codeforces.com/submissions/arbit

unordered_map is giving wrong answers while map gives the correct answer.

stl, hashmap

zeref_dragoneel
9 лет назад
6

Комментарии (6)

Написать комментарий?

vintage_Vlad_Makeev

9 лет назад, # |

Looks like you use fact, that in map all pairs are sorted. It's true for normal map(because it's based on BST), but wrong for unordered_map(because it's based on hash table and keys are sorted not by value, but by hashs)

→ Ответить

zeref_dragoneel

9 лет назад, # ^ |

According to the solution, the ordered property is not making any difference.

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # ^ |

Ok, that's my error :(

Here

if (it2 == M.end() || it2->second > cost)
	M[fc] = cost;

You can add element to map. Maybe it can make iterator it1 invalid...

→ Ответить

zeref_dragoneel

9 лет назад, # ^ |

According to what you are saying, map should give wrong answers however it is the other way round.

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # ^ |

When you change container there are magic with iterators, so it's better just not to do it :) You can never be sure what you will get

→ Ответить

CountZero

9 лет назад, # |

← Rev. 2 →

+20

std::map and std::unordered_map have different iterator invalidation rules. Basically, any std::unordered_map iterator can be invalidated after any insertion or deletion because of rehashing, and you can't control it. On other hand, std::map iterator is guaranteed to be valid until you erase it explicitly. That's why you got 2 different results.

→ Ответить