How to Call Erase With a Reverse Iterator

How to call erase with a reverse iterator

After some more research and testing I found the solution. Apparently according to the standard [24.4.1/1] the relationship between i.base() and i is:

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

(from a Dr. Dobbs article):

alt text

So you need to apply an offset when getting the base(). Therefore the solution is:

m_CursorStack.erase( --(i.base()) );

EDIT

Updating for C++11.

reverse_iterator i is unchanged:

m_CursorStack.erase( std::next(i).base() );

reverse_iterator i is advanced:

std::advance(i, 1);
m_CursorStack.erase( i.base() );

I find this much clearer than my previous solution. Use whichever you require.

How to call erase with a reverse iterator using a for loop

After some use of this idiom, I think a modification to the loop in Jarod42's answer is in order to make things safer and maintain the typical for(;;) loop niceties:

for (auto it = testcont.rbegin(), nit = it; it != testcont.rend(); it = nit) {
    nit = next(it);

    // whatever... maybe a continue somewhere or maybe not

    if (WE_WANT_TO_ERASE(it)) {
        nit = decltype(it){ testcont.erase(std::next(it).base()) };
    }

    // whatever... maybe a continue somewhere or maybe not
}

Using the loop in the other answer is too dangerous. If one were to thoughtlessly add a continue; somewhere in the loop, without incrementing the iterator first, the result would be an infinite loop. Since, at first glace, this can look like a normal for(;;) loop, I believe that this is bound to happen sooner or later. Similarly, if there are branches in the loop, and if one of those branches neglects to increment the iterator, another bug is introduced. Finally, if you do an erase(), you need to be sure to continue before you increment the iterator or else you have yet another bug.

Using the modified loop above, the loop can be treated just like a normal for(;;) loop. The trick is to increment nit (the "next iterator") as the first line of the loop body. Then you don't have to worry. The only time you need to update nit is if you are doing an erase(). Everything else works as one would expect a for loop to work.

One final note: I originally asked the question with regard to maps, but this will work correctly for vector, list, etc, as well.

Does vector::erase not work with reverse iterators?

It does not. However, reverse iterators provide a base() method to obtain a forward iterator. Take note that the returned forward iterator points to the element following the element the reverse iterator points to.

Or, to put it another way, .rbegin().base() == .end() and .rend().base() == .begin()

So the fixed code would look like this:

some_vector.erase(
    (++(some_vector.rbegin())).base(),
    some_vector.rbegin().base()
);

Note that we have to swap the order of the iterators around since they are reverse iterators; the second argument must be an iterator that follows the first iterator in the sequence, but without swapping the order of the reverse iterators this wouldn't be true. So if we have two reverse iterators a and b, and b >= a then we can use this idiom for erase():

container.erase(b.base(), a.base());

More generally, it holds for the range of reverse iterators [a, b) that the range [b.base(), a.base()) iterates the same sequence of elements in the opposite order.

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

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());

        // 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.

vector::erase and reverse_iterator

In the question you have already quoted exactly what the standard says a reverse_iterator is:

The relationship between reverse_iterator and iterator is &*(reverse_iterator(i)) == &*(i- 1)

Remember that a reverse_iterator is just an 'adaptor' on top of the underlying iterator (reverse_iterator::current). The 'reference point', as you put it, for a reverse_iterator is that wrapped iterator, current. All operations on the reverse_iterator really occur on that underlying iterator. You can obtain that iterator using the reverse_iterator::base() function.

If you erase --vect_rit.base(), you are in effect erasing --current, so current will be invalidated.

As a side note, the expression --vect_rit.base() might not always compile. If the iterator is actually just a raw pointer (as might be the case for a vector), then vect_rit.base() returns an rvalue (a prvalue in C++11 terms), so the pre-decrement operator won't work on it since that operator needs a modifiable lvalue. See "Item 28: Understand how to use a reverse_iterator's base iterator" in "Effective STL" by Scott Meyers. (an early version of the item can be found online in "Guideline 3" of http://www.drdobbs.com/three-guidelines-for-effective-iterator/184401406).

You can use the even uglier expression, (++vect_rit).base(), to avoid that problem. Or since you're dealing with a vector and random access iterators: vect_rit.base() - 1

Either way, vect_rit is invalidated by the erase because vect_rit.current is invalidated.

However, remember that vector::erase() returns a valid iterator to the new location of the element that followed the one that was just erased. You can use that to 're-synchronize' vect_rit:

vect_rit = vector_type::reverse_iterator( vector.erase(vect_rit.base() - 1));

Erasing element from a vector – rbegin() vs begin()

There is no std::vector::erase() overload for reverse_iterator. However, you can obtain the corresponding iterator from a reverse_iterator by calling its base() member function:

auto rit = V.rbegin();
auto it = rit.base();
V.erase(it);

This code does compile but results in undefined behavior because the iterator counterpart of rbegin() corresponds to end(). From std::vector::erase() documentation:

iterator erase(const_iterator pos);

The iterator pos must be valid and dereferenceable. Thus the end() iterator (which is valid, but is not dereferencable) cannot be used as a value for pos.

rbegin().base() returns end(), not end() - 1. Nevertheless, you can advance rbegin() by one if you want a dereferencable iterator:

auto it = (std::next(rit)).base();

C++ map erase using forward and reverse iterators

First of all, let me reiterate LogicStuff's comment: You should really try to pass in compatible iterators instead.

If you really, really, really have no alternative to doing it the way you are doing it right now, you could use some template functions:

#include <vector>
#include <iostream>

// Used when both iterators have the same type
template <typename T>
void foo(T begin, T end)
{
  for (; begin != end; ++begin)
  {
    std::cout << " " << *begin;
  }
}

// Overload for a forward begin and reverse end
template <typename T>
void foo(T begin, std::reverse_iterator<T> end)
{
  foo(begin, end.base());
}

// Overload for a reverse begin and forward end
template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(begin, std::reverse_iterator<T>(end));
}

int main()
{
  std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  foo(v.begin(), v.end()); std::cout << std::endl;
  foo(v.begin(), v.rbegin()); std::cout << std::endl;
  foo(v.rbegin(), v.begin()); std::cout << std::endl;
  foo(v.rbegin(), v.rend()); std::cout << std::endl;
}

See it running on ideone.

Here I convert reverse iterators to forward iterators. This SO post gives you more details about that. But read that post very carefully, there be dragons. My example above just outputs numbers and does not modify the underlying container. And I do not check the validity of the iterators, nor do I do any bounds checking. For your own case, make sure you test all the edge cases (either iterator being at or beyond the beginning/end of your container; off-by-one errors, etc.).

Also, note that in your example code, the call to erase() invalidates the iterator, so you should write the loop body like this:

if (cond) {
  // guarantees to return an iterator to the element following
  // the erased element.
  start = m.erase(start);
} else {
  ++start;
}

Edit: If you require that iterators are always converted to their forward equivalents, you can change the last overload and add another:

template <typename T>
void foo(std::reverse_iterator<T> begin, T end)
{
  foo(end, begin.base()); // Note: order of iteration reversed!
}

template <typename T>
void foo(std::reverse_iterator<T> begin, std::reverse_iterator<T> end)
{
  foo(end.base(), begin.base()); // Note: order of iteration reversed!
}

But be aware that the order of iteration is now reversed: in my example, calling foo(v.rbegin(), v.rend()) printed 9 8 7 ... 1 in the first incarnation, and now it prints 1 2 3 ... 9. Example here.

And again, you'd be off much better if you could feed in compatible iterators instead.