How do I erase a reverse_iterator from an stl data structure?

Question

For some reason the following code fails. You can't simply erase a reverse_iterator by using its base() method.

#include <set>
#include <iostream>

int main()
{
    std::set<int> setOfInts;
    setOfInts.insert(1);
    setOfInts.insert(2);
    setOfInts.insert(3);

    std::set<int>::reverse_iterator rev_iter = setOfInts.rbegin();
    std::set<int>::reverse_iterator nextRevIter = setOfInts.rbegin();
    ++nextIter;

    while ( rev_iter != setOfInts.rend())
    {
        // Find 3 and try to erase
        if (*rev_iter == 3)
        {
            // SEGFAULT HERE
            setOfInts.erase( rev_iter.base());
        }
        rev_iter = nextRevIter;
        ++nextRevIter;
    }

}

How does one go about correctly doing the above? Given a reverse_iterator that corresponds to something you want to erase, how do you erase it?

Note, erase won't take reverse_iterators unfortunately. It wants the real thing.

Answer 1

Call erase with the iterator itself (no need to use base).

#include <set>
#include <iostream>

int main()
{
    std::set<int> setOfInts;
    setOfInts.insert(1);
    setOfInts.insert(2);
    setOfInts.insert(3);

    std::set<int>::reverse_iterator rev_iter = setOfInts.rbegin();

    while (rev_iter != setOfInts.rend())
    {
        // Find 3 and try to erase
        if (*rev_iter == 3)
        {
            rev_iter = setOfInts.erase(rev_iter);
        }
        else
        {
            ++rev_iter;
        }
    }
}

Also, you don't need that separate "next" iterator (see above changes). An even better way to do this is to use std::remove_if (or a function like it).

Answer 2

Apparently the solution is what base() returns is 1 off. The following identity holds for a reverse_iterator:

&*(reverse_iterator(i)) == &*(i - 1)

Or in other words, the reverse_iterator is always one pass the regular iterator it is the base of. Not sure why.

In GCC

Simply change

        // SEGFAULT HERE
        setOfInts.erase( rev_iter.base());

to

        // WORKS!
        setOfInts.erase( --rev_iter.base());

I'm definitely curious though as to why the identity above makes sense.

In Visual Studio

Coming back into work and trying this in visual studio, I see the above solution doesn't quite work. The "nextIter" becomes invalid on the erase. Instead, you need to save away the temporary from the erase to get the next iterator instead of keeping around a nextIter like above.

  set<int>::iterator tempIter = setOfInts.erase(--rev_iter.base());
  rev_iter = setOfInts.erase(tempIter);

So the final solution is

int main()
{
    using namespace std;

    set<int> setOfInts;
    setOfInts.insert(1);
    setOfInts.insert(2);
    setOfInts.insert(3);

    set<int>::reverse_iterator rev_iter = setOfInts.rbegin();

    while ( rev_iter != setOfInts.rend())
    {
     // Find 3 and try to erase
     if (*rev_iter == 3)
     {
      cout << "Erasing : " << *rev_iter;
      set<int>::iterator tempIter = setOfInts.erase( --rev_iter.base());
      rev_iter = set<int>::reverse_iterator(tempIter);   
     }
     else
     {
      ++rev_iter;
     }
    } 

}

Note, associative containers do not return an iterator from erase. So this solution wouldn't work for map, multimap, etc.

Answer 3

When you iterate with a reverse iterator and want to use base() to modify its container, always keep in mind that a reverse_iterator is always based on the next iterator from the original order. It's a little unintuitive but it actually makes the code simpler:

#include <set>
int main()
{
    std::set<int> setOfInts;
    setOfInts.insert(1);
    setOfInts.insert(2);
    setOfInts.insert(3);

    typedef std::set<int>::reverse_iterator RevIter;

    RevIter rev_iter = setOfInts.rbegin();
    while (rev_iter != setOfInts.rend())
    {
        // Find 3 and try to erase
        if (*rev_iter == 3)
            setOfInts.erase(--rev_iter.base());

        ++rev_iter;
    }
}

In this example, there is not need to keep a "next" iterator since the base iterator is not invalidated! (We do need it when dealing with normal iterators.)

The behavior of reverse iterators creates weird off-by-one difficulties when treating with a single item but in facts it simplify ranges:

riValue = find(riEnd.base(), riBegin.base(), value);

is using exactly the same objects (in reverse order) as

iValue = find(riBegin, riEnd, value);