Three Guidelines for Effective Iterator Usage

Guideline 3: Understand How to Use a reverse_iterator’s Base iterator

Invoking the base member function on a reverse_iterator yields the “corresponding” iterator, but it’s not really clear what that means. As an example, take a look at this code, which puts the numbers 1-5 in a vector, sets a reverse_iterator to point to the 3, and sets an iterator to the reverse_iterator’s base:

vector<int> v;

// put 1-5 in the vector
for (int i = 1; i <= 5; ++i) {
  v.push_back(i);
}

// make ri point to the 3
vector<int>::reverse_iterator ri =
  find(v.rbegin(), v.rend(), 3);

// make i the same as ri's base
vector<int>::iterator i(ri.base());

After executing this code, things can be thought of as looking like this:

This picture is nice, displaying the characteristic offset of a reverse_iterator and its corresponding base iterator that mimics the offset of rbegin() and rend() with respect to begin() and end(), but it doesn’t tell you everything you need to know. In particular, it doesn’t explain how to use i to perform operations you’d like to perform on ri.

As Guideline 1 explains, some container member functions accept only iterators as iterator parameters, so if you want to, say, insert a new element at the location identified by ri, you can’t do it directly, because vector’s insert function won’t take reverse_iterators. You’d have a similar problem if you wanted to erase the element pointed to by ri. The erase member functions haughtily reject reverse_iterators, insisting instead on iterators. To perform erasures and some forms of insertion, you must convert reverse_iterators into iterators via the base function, then use the iterators to get the jobs done.

So let’s suppose you did want to insert a new element into v at the position indicated by ri. In particular, let’s assume you want to insert the value 99. Bearing in mind that ri is part of a traversal from right to left in the picture above and that insertion takes place in front of the element indicated by the iterator used to specify the insertion position, we’d expect the 99 to end up in front of the 3 with respect to a reverse traversal. After the insertion, then, v would look like this:

Of course, we can’t use ri to indicate where to insert something, because it’s not an iterator. We must use i instead. As noted above, when ri points at 3, i (which is ri.base()) points at 4. That’s exactly where i needs to point for an insertion if the inserted value is to end up where it would if we had used ri to specify the insertion location. Conclusion?

• To emulate insertion at a position specified by a reverse_iterator ri, insert at the position ri.base() instead. For purposes of insertion, ri and ri.base() are equivalent, and ri.base() is truly the iterator corresponding to ri.

Let us now consider erasing an element. Look again at the relationship between ri and i in the original vector (i.e., prior to the insertion of 99):

If we want to erase the element pointed to by ri, we can’t just use i, because i doesn’t point to the same element as ri. Instead, we must erase the element preceding i. Hence,

• To emulate erasure at a position specified by a reverse_iterator ri, erase at the position preceding ri.base() instead. For purposes of erasure, ri and ri.base() are not equivalent, and ri.base() is not the iterator corresponding to ri.

It’s worth looking at the code to perform such an erasure, because it holds a surprise.

vector<int> v;
... // as above, put 1-5 in v

// as above, make ri point to the 3
vector<int>::reverse_iterator ri =
  find(v.rbegin(), v.rend(), 3);

// attempt to erase at the position
// preceding ri.base(); for a vector,
// this will typically not compile
v.erase(--ri.base());

There’s nothing wrong with this design. The expression --ri.base() correctly specifies the element we’d like to erase. Furthermore, this code will work with every standard container except vector and string. It might work with vector and string, too, but for many vector and string implementations, it won’t compile. In such implementations, iterators (and const_iterators) are implemented as built-in pointers, so the result of ri.base() is a pointer.

Both C and C++ impose the constraint that pointers returned from functions may not be modified, so for STL platforms where string and vector iterators are pointers, expressions like --ri.base() won’t compile. To portably erase something at a position specified by a reverse_iterator, then, you must take pains to avoid modifying base’s return value. No problem. If you can’t decrement the result of calling base, just increment the reverse_iterator and then call base!

... // as above

// erase the element pointed to by
// ri; this should always compile
v.erase((++ri).base());

Because this approach works with every standard container, it is the preferred technique for erasing an element pointed to by a reverse_iterator.

It should now be clear that it’s not accurate to say that a reverse_iterator’s base member function returns the “corresponding” iterator. For insertion purposes, it does, but for erasure purposes, it does not. When converting reverse_iterators to iterators, it’s important that you know what you plan to do with the resulting iterator, because only then can you determine whether the iterator you have is the one you need.

Summary

STL containers offer four iterator types, but in practice, iterator tends to be the most useful. If you have a const_iterator and access to the container for that const_iterator, you can use distance and advance to generate the corresponding iterator. If you have a reverse_iterator, you can use its base member function to generate a “corresponding” iterator, but if you want to use the iterator in a call to erase, you’ll probably need to increment the reverse_iterator before calling base.

Scott Meyers is one of the world’s foremost authorities on C++; Effective STL is his third C++ book. He has a Ph.D. in Computer Science from Brown University, is a member of the Advisory Boards of NumeriX LLC and InfoCruiser Inc., and provides training and consulting services to clients worldwide. His web site is <http://www.aristeia.com/>.