Identical codes. DFS Topological sort working with map and not with unordered_map

#1

I’m trying topological sort using dfs.

these two are identical codes, only that in one i used map where as in other i used unordered map.

the one with map works. the one with unordered map misses a node during topological function call.

can someone explain the reason to me.

Link to code using map: https://ide.codingblocks.com/s/224603

Link to code using unordered_map: https://ide.codingblocks.com/s/224523

Thanks

#2
#3

I am facing the same problem. Can somebody please tell what is the problem with unordered_map?

#4

Hey @POORVI_SAXENA,

Although I’m not 100% sure about the reason, but I think this happens due to the way unordered_map is implemented in cpp.

You can check the following links:

  1. Stack Overflow question
    https://stackoverflow.com/questions/59896613/error-in-topological-sort-when-representing-the-graph-as-an-unordered-mapstring

  2. Cpp Ref: (I think its because of the forced rehashing that causes the iterartor invalidation(check the bottom of the page in the link below))
    http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/

If you come across a solid reason do mention it here.
Thanks,
Mayank Kapur