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

Difference in answers in unordered_map and map
Автор zeref_dragoneel, история, 9 лет назад, По-английски

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

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

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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...

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          → Ответить
»
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.

→ Ответить