Find and erase element from STL container while iterating

Question

While iterating over a multimap I want to delete elements, but not only the element the iterator is pointing to.

for (vector<int> myVec : myVectors) { auto range = myMultiMap.equal_range(myVector); for (auto it = range.first; it != range.second; ++it) { // secondPair is another element of this multimap auto secondPair = getSecondPair(it, myMultiMap); if (condition) { it = myMultiMap.erase(it); auto finder = myMultiMap.find(secondPair); // how can I delete secondPair? } } }

Maybe it's the xy-problem here, so let me explain what I need this for: What I'm trying to do is to shorten a set of vector<int>. There are associated elements of type MyPair for each element. Those associated elements are stored in an unordered multimap.

typedef unordered_multimap < vector<int>, MyPair, SomeHash > MyMultiMap;

An element of the set<vector <int> > can be removed if all associated pairs in the multimap have been processed successfully. It won't be successful for most of them, so most of them are expected to remain in the set. My idea was to delete the elements from the multimap and if there are no associated elements in the multimap anymore, it means the element can be removed from the set. Here again I have the problem to remove elements from a set while iterating. Again, not only the one the iterator is pointing to.

Do you need to do this in-place, or can you copy to a temporary set and swap it into myVectors? — Caleth
– Caleth, Commented Nov 6, 2017 at 15:01
FYI saying both it = myMultiMap.erase(it) and ++it is likely to lead to some errors. — AndyG
– AndyG, Commented Nov 6, 2017 at 15:07

Guillaume Gris · Accepted Answer · 2017-11-06 15:22:51Z

From cppreference on unordered_multimap::erase:

References and iterators to the erased elements are invalidated. Other iterators and references are not invalidated.

So I think that if you get an iterator to secondPair and secondPairIt != it then you can safely erase secondPairIt. You should also check that you are not invalidating the end of the range.

for (auto it = range.first; it != range.second;) { if (condition) { auto secondPairIt = getSecondPairIt(it, myMultiMap); // Assume this is not end if (secondPairIt != it) { if (secondPairIt == range.second) range.second = myMultiMap.erase(secondPairIt); else myMultiMap.erase(secondPairIt); } it = myMultiMap.erase(it); } else { ++it; } }

thanks for correcting my mistake of incrementing the iterator, even when calling it = myMultiMap.erase(it).

Collectives™ on Stack Overflow

Find and erase element from STL container while iterating

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related