Does std::map::erase(it++) maintain a valid iterator pointing to the next element in the map? [duplicate]

Question

This question already has answers here:

How to remove from a map while iterating it? (6 answers)

Closed 9 years ago.

I'm using Xcode with C++ 11 for a std::map. Some elements in my map have a flag that says they need to be removed.

I want to iterate through the map, erasing the flagged elements in O(n) time. The call to erase does not return an iterator. I have seen some kind of erase(it++) implementation, but I have no evidence that such a call can work since the iterator will become invalid after the erase operation but before the increment operation.

My current code seems so inefficient.

for(auto it = myMap.begin(); it != myMap.end(); ++it)
{
    delete *it;
    myMap.erase(it);
    it = myMap.begin(); //how can I avoid iterating through the map again
}

Answer 1

From the online documentation:

"Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity."

So maybe this:

for(auto it = myMap.begin(); it != myMap.end();)
{
    auto itPrev = it;
    ++it;

    if(shouldBeDeleted(*itPrev))
       myMap.erase(itPrev);
}

Edit: The erase(it++) idea you mention is actually ok, because the increment occurs (and returns a copy of the old, pre-increment value) before erase() is called. It's in effect the equivalent of:

template<typename IteratorT>
IteratorT PostIncrement(IteratorT& it)
{
   auto copy = it;
   ++it;
   return copy;
}

for(auto it = myMap.begin(); it != myMap.end();)
   myMap.erase(PostIncrement(it));

which amounts to the same thing as the other example. Incidentally, this is why you should normally use the prefix ++ with iterators; that copy operation is extra overhead, and you usually don't need it.

Answer 2

When std::map::erase() is passed an iterator, it returns an iterator to the next element that follows the element being erased. This allows you to continue your iteration without starting over.

Try this:

auto it = myMap.begin();
while (it != myMap.end())
{
    if (it->flagged)
    {
        delete *it;
        it = myMap.erase(it);
    }
    else
        ++it;
}