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

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 te开发者_高级运维mp = r++;

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

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

---

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.

---

A reverse_iterator is often just a wrapper around a normal iterator, and so incrementing the reverse iterator probably decrements one underneath. Similarly, rbegin will return an iterator that is after all of the elements in the container, and so it would be invalidated in the same way.

---

Here is a much better way to do what you're trying to do:

struct CustomRemove
{
    bool operator()(int i)
    {
        return (i == 2);
    }
};

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

    CustomRemove custom_remove;

    std::copy(x.begin(), x.end(), std::ostream_iterator<int>(std::cout, "\n"));
    x.erase(std::remove_if(x.begin(), x.end(), custom_remove), x.end());
    std::copy(x.begin(), x.end(), std::ostream_iterator<int>(std::cout, "\n"));

    return 0;
}

---

A reverse_iterator internally stores a normal iterator to the position after its current position. It has to do that, because rend() would otherwise have to return something before begin(), which isn't possible. So you end up accidentally invalidating your base() iterator.

---

Since (r+1).base() and r effectively point to the same element, erasing (r+1).base() does in fact invalidate r. Most likely g++ just uses a pointer under the hood so it all appears to work correctly.

If you're trying to remove matching elements from a vector a much better approach is to use remove or remove_if.