Issue i am facing is, The iterator is skipping some of the entries in the map.
Details:
I'm working on undirected graph min cut algorithm.
I'm maintaining edges as
map< pair<int, int> , int> where
pair<int , int> is edge from i to j (i < j)
int is number of parallel edges from i to j
Once i randomly choose which edge to delete, I remove the second vertex of this edge from edge . Iterate through remaining edges to see if any compression required.
If so i remove the required edge and add the new edge (cant edit existing as each edge itself is the key).
Elements in the map are ordered by the key value. If you add an element while iterating over the map the new element could be positioned before or after the current element depending on the key.
If you erase an element, all iterators to that element are invalidated so you can no longer use such an iterator for anything. All other iterators stay valid.