vectors: rend() is being invalidated by erase()

Question

According to the C++ specification (23.2.4.3), vector::erase() only invalidates "all the iterators and references after the point of the erase"

As such, when using reverse_iterators to pass over all vector members, an erase on the current iterator should not cause the rend() member to be invalidated.

This code will run under G++ but will provide a runtime exception on Windows (VS2010):

#include <vector>

using namespace std;

int main()
{
    vector<int> x;
    x.push_back(1);
    x.push_back(2);
    x.push_back(3);

    //Print
    for(vector<int>::const_iterator i = x.begin(); i != x.end(); ++i)
        printf("%d\n", *i);

    //Delete second node
    for(vector<int>::reverse_iterator r = x.rbegin(); r != x.rend(); ++r)
        if(*r == 2)
            x.erase((r+1).base());

    //Print
    for(vector<int>::const_iterator i = x.begin(); i != x.end(); ++i)
        printf("%d\n", *i);

    return 0;
}

The error is interesting:

Expression: vector iterator not decrementable

Given on the line of the second for loop upon the second run. The decrement refers to the internal "current" iterator member of the reverse_iterator, which is decremented whenever reverse_iterator is incremented.

Can anyone explain this behavior, please?

Thanks.

EDIT

I think this code sample better shows that it's not a problem with r, but rather with rend():

//Delete second node
for(vector<int>::reverse_iterator r = x.rbegin(); r != x.rend();)
{
    vector<int>::reverse_iterator temp = r++;

    if(*temp == 2)
        x.erase((temp+1).base());
}

And errors out with vector iterators incompatible on the for loop upon entry after erase.

Answer 1

Your program invokes Undefined Behavior. Therefore, neither compiler is incorrect.

According to the Standard, std::vector<int>::reverse_iterator is a typedef for std::reverse_iterator<std::vector<int>::iterator>. The implementation of std::reverse_iterator<Iter> is specified to have a protected member Iter current;, and all other members and functions of reverse_iterator are specified based on the behavior of the member current.

So suppose we have r == reverse_iterator(i), where i is a valid iterator into std::vector<int> x;. Each of these is then guaranteed by the Standard.

r.current == i
(r+1).current == (i-1)
(r+1).base() == (i-1)

On calling x.erase((r+1).base());, all iterators after i-1 are invalidated. Of course, this includes i, and therefore also r.current.

The next thing your program attempts to evaluate is ++r. This expression is specified as having an effect --r.current;. But since r.current was invalidated, this expression is Undefined Behavior; and so is ++r.