Puzzling post and pre-increment behavior of reverse_iterators and base

Question

Consider the toy program (post.cpp):

#include <iostream>
#include <vector>

using namespace std;
int main() {
        vector<int > a;
        int i;
        for(i=0;i<10;i++)
                a.push_back(i);
        auto it=a.rbegin();
        while(it!=a.rend()) {
                if ((*it % 2)==0) {
                                cout << "about to erase "<<*it<<endl;
                                a.erase((it++).base());
                }
                else {
                        ++it;
                }
        }
        for(auto it2=a.begin(); it2 != a.end(); it2++) {
                cout << *it2 << endl;
        }
        return 0;
}

What I am trying to do is to test for evenness, and then delete the current number, since (it++) should return the current iterator and then advance the iterator. This is what I get as the output:

$ ./post 
about to erase 8
about to erase 6
about to erase 4
about to erase 2
about to erase 0
0
2
4
6
8

If, however, I change the line a.erase((it++).base()); to a.erase((++it).base());, I get the correct behavior. Why is this?

Useful clarification: I am using base() since reverse_iterators cannot be used in erase(). There is an application where I want to go reverse on the vector to erase stuff.

Kerrek SB · Accepted Answer · 2012-09-25T22:14:57.917

3

The base() of a reverse iterator is offset by 1. So rbegin().base() == end() and rend().base() == begin().

This is nothing other than the generalization of this reverse loop:

for (size_t i = 0; i != N; ++i)
{
    mutate(array[N - i - 1]);
}   //                 ^^^

The loop traverses the array in reverse order, and note how we need a - 1 on the "iterator".

Update: Now let's investigate what a reverse iterator is: It is simply a wrapper around a bidirectional iterator. Suppose the reverse iterator is called it; then it has an ordinary iterator member it.base(). For example, v.rbegin().base() == v.end(). When you say ++it, that just calls --it.base() (conceptually). The real magic is the dereference operation: This has to give us one element before the underlying iterator:

*it == *(it.base() - 1)

This is exactly the same arithmetic which told us that the i^th element from the back of an array is offset by one:array[N - i - 1]. This also shows us why we need a bidirectional iterator to form reverse iterators.

Now it is clear how we can erase via reverse iterators from a container that does not invalidate iterators, such as any node-based container:

if (meets_condition(*it))   // this examines *(it.base() - 1)!
{
     auto b = it.base();
     container.erase(it.base() - 1);
     it = std::reverse_iterator(b);
}

Remember that this requires that erasing does not invalidate any iterators other than the erasee, like in any node-based container. Erasing like this from a vector would be even more difficult. For a vector, erasing invalidates all iterators past the erasee (in forward direction), so we have to use the return value of the erase function:

if (meets_condition(*ut))   // again, examine *(it.base() - 1)
{
    it = std::reverse_iterator(container.erase(it.base() - 1));
}

In a picture (we're removing element "5"):

+---+---+---+---+---+---+---+
| 2 | 3 | 4 | 5 | 6 | 7 | 8 |     =:   v
+---+---+---+---+---+---+---+
              ^   ^
              |   |
|             |   +--- it.base()
|             |
|             +--- *it == *(it.base() - 1)
|
V

+---+---+---+---+---+---+
| 2 | 3 | 4 | 6 | 7 | 8 |
+---+---+---+---+---+---+
          ^   ^
          |   |
          |   +--- result of v.erase(it.base() - 1)
          |
          +--- *(std::reverse_iterator(v.erase(it.base() - 1)))

edited Sep 25 '12 at 22:14

answered Sep 25 '12 at 16:55

Kerrek SB

464,522
92
875
1,084

Thanks! But how would I go about doing what I am trying to do, namely delete elements while iterating in reverse on an STL container? In fact let me update my question at the top to include this. – highBandWidth Sep 25 '12 at 17:00
@highBandWidth: I thought you already knew how to get the correct behaviour?! – Kerrek SB Sep 25 '12 at 17:01
Ahh, I see. I guess you have answered the question, but then the program seems to depend on this little quirk. Is there a way to get the iterator corresponding to the same element? So that '(*it)== *(it.real_base())'? – highBandWidth Sep 25 '12 at 17:05
@highBandWidth: There's no quirk. Look at the array loop again: This is exactly what a reverse iterator is: just a wrapper around a bidirectional iterator. You simply offset the base by one. That's precisely what the dereference operation does. But to be honest, I'm not actually sure whether this is well-defined behaviour, because it looks like you're invalidating the iterator. I have to think about that. – Kerrek SB Sep 25 '12 at 17:06
1

The *correct way* is a bit trickier to get to, and it is not what is written in the question (which is undefined behavior), so my assumption is that he does not know it. The correct way of doing this would be to reconstruct a `reverse_iterator` out of the value returned by `erase`. – David Rodríguez - dribeas Sep 25 '12 at 17:11
@highBandWidth: That question is about `std::set`, not `std::vector`. The guarantees of the operations on the different containers are not the same. In particular in a `std::set`, the `erase` operation invalidates *only* the erased iterator, while on a `std::vector` it invalidates *all* iterators from the erased one to the end of the container. – David Rodríguez - dribeas Sep 25 '12 at 17:14
@DavidRodríguez-dribeas, where can I find the guarantees on the operations? I couldn't find them on the `set` page, for example at http://www.sgi.com/tech/stl/set.html – highBandWidth Sep 25 '12 at 17:22
@highBandWidth: Uhm... the last paragraph in the **Description** in your link actually says. – David Rodríguez - dribeas Sep 25 '12 at 17:25
@DavidRodríguez-dribeas: You're right. The `base()` iterator is just the actual iterator itself, which *will* be invalidated by the `erase` operation. Let me write something up. – Kerrek SB Sep 25 '12 at 21:22
I don't think the last piece of code is correct. I would expect something alike: `it = std::reverse_iterator(vector.erase(it.base()-1))`. That is, obtain the iterator to delete from the reverse iterator, take the result of the call to `erase` which is the a valid iterator to the element after the removed one and populate `it` with that value. Unlike forward iteration, in this case we still want to do the `++it` at the end of the iteration since the value returned by `erase` is an iterator *before* the one we are processing when seen in the backwards direction. – David Rodríguez - dribeas Sep 25 '12 at 21:35
... now whether this is a good option or not... I would still prefer using the *erase-remove* idiom, which can be combined with a backwards pass (if as the user suggests) there is an extra condition that means the iteration should stop. – David Rodríguez - dribeas Sep 25 '12 at 21:41
@DavidRodríguez-dribeas: Are you sure? in my code, `b` is never invalidated, only `b - 1` is... – Kerrek SB Sep 25 '12 at 21:49
The code in the question uses a `std::vector` for which `erase` invalidates all iterators after the one being removed. – David Rodríguez - dribeas Sep 25 '12 at 22:00
@DavidRodríguez-dribeas: Oh, of course - I was thinking `set`. OK, I'll make a note of that. – Kerrek SB Sep 25 '12 at 22:06

score 1 · Answer 2 · answered Sep 25 '12 at 17:05

1

Not an answer to your question, but a solution to your problem: Use the erase-remove idiom that is more efficient than what you are currently doing:

bool even( int value ) { return !(value%2); }
std::vector<int> v = { 1,2,3,4,5,6,7,8,9,10 }; // Assuming C++11 or build it otherwise
v.erase( std::remove_if( v.begin(), v.end(), even ),
         v.end() );

The difference in efficiency is that remove_if will copy only the values left in the container once to the final location, while your algorithm might copy some of the elements multiple times. In particular 9 will be copied 4 times, 7 3 times and so on.

answered Sep 25 '12 at 17:05

David Rodríguez - dribeas

204,818
23
294
489

Thanks! But you see the reason I was doing it this way is that in my real application I need to go reverse since I know after a while I can break out of the loop. Can you go in reverse and conditionally break out of the loop with erase-remove? – highBandWidth Sep 25 '12 at 17:08
@highBandWidth: You cannot. What the best solution depends on your actual requirements, and those are missing from the question. – David Rodríguez - dribeas Sep 25 '12 at 17:15
May be I should ask a separate question. I need to go over a vector or list, go over the container in reverse, conditionally remove elements, and also conditionally break out of the loop after a while. – highBandWidth Sep 25 '12 at 17:18
@highBandWidth: The question is how *conditionally* is determined. One thing you can do is walk backwards without modifying until you reach the condition, at which point you can use the *erase-remove* idiom. While this requires two passes over the end of the container, you will avoid the multiple copies and that might actually provide a gain. – David Rodríguez - dribeas Sep 25 '12 at 17:23

Puzzling post and pre-increment behavior of reverse_iterators and base

2 Answers2

Linked