0

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
}
Gandalf458
  • 2,139
  • 1
  • 21
  • 36
  • use `unique_ptr<>` to manage object lifetime then use `erase/remove_if` with a lambda that checks your removal flag. See http://en.cppreference.com/w/cpp/algorithm/remove for an example. – mythagel Apr 29 '14 at 01:17

2 Answers2

4

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.

dlf
  • 9,045
  • 4
  • 32
  • 58
  • what online documentation are you referring to? – Gandalf458 Apr 29 '14 at 01:20
  • The one I looked at is here: http://www.cplusplus.com/reference/map/map/erase/. That page also says C++11 should have `erase` overloads that return `iterator`s, but maybe they were left out of the implementation you're using. – dlf Apr 29 '14 at 01:22
  • OK, I did not notice the C++11 tab that I could click there. That seems to make sense, and I will mark it as correct if there are no errors. – Gandalf458 Apr 29 '14 at 01:33
  • Edited my answer with additional info. – dlf Apr 29 '14 at 01:48
  • The version of `std::map::erase()` that takes an interator as input and returns an iterator to the next element as output is not new in C++11, it existed in earlier versions as well. – Remy Lebeau Apr 29 '14 at 02:22
  • This can be made slightly more elegant by using `auto itPrev = it++;` instead. – isekaijin Apr 29 '14 at 02:37
4

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;
}
Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770