Guideline 2: Use distance and advance to Convert const_iterators to iterators
Guideline 1 points out that some container member functions that take iterators as parameters insist on iterators; const_iterators won’t do. So what do you do if you have a const_iterator in hand, and you want to, say, insert a new value into a container at the position indicated by the iterator? Somehow you’ve got to turn your const_iterator into an iterator, and you have to take an active role in doing it, because there is no implicit conversion from const_iterator to iterator.
I know what you’re thinking. You’re thinking, “When all else fails, get a bigger hammer.” In the world of C++, that can mean only one thing: casting. Shame on you for such thoughts. Honestly, where do you get these ideas?
Let us confront this cast obsession of yours head on. Look what happens when you try to cast a const_iterator to an iterator:
// convenience typedefs typedef deque<int> IntDeque; typedef IntDeque::iterator Iter; typedef IntDeque::const_iterator ConstIter; // ci is a const_iterator ConstIter ci; ... // error! no implicit conversion from // const_iterator to iterator Iter i(ci); // still an error! can't cast a // const_iterator to an iterator Iter i(const_cast<Iter>(ci));
This example happens to employ deque, but the outcome would be the same for list, set, multiset, map, and multimap, as well as the non-standard STL containers based on hash tables. The line using the cast might compile in the case of vector or string, but those are special cases we’ll consider in a moment.
The reason the cast generally won’t compile is that for these container types, iterator and const_iterator are completely different classes, barely more closely related to one another than are string and complex<double>. Trying to cast one type to the other is nonsensical, and that’s why the const_cast is rejected. static_cast, reinterpret_cast, and a C-style cast would lead to the same end.
Alas, the cast that won’t compile might compile if the iterators’ container were a vector or a string. That’s because it is common for implementations of these containers to use real pointers as iterators. For such implementations, vector<T>::iterator is a typedef for T*, vector<T>::const_iterator is a typedef for const T*, string::iterator is a typedef for char*, and string::const_iterator is a typedef for const char*. With such implementations, the const_cast from a const_iterator to an iterator will compile and do the right thing, because the cast is converting a const T* into a T*. Even under such implementations, however, reverse_iterators and const_reverse_iterators are true classes, so you can’t const_cast a const_reverse_iterator to a reverse_iterator. Also, even implementations where vector and string iterators are pointers might use that representation only when compiling in release mode. All these factors lead to the conclusion that casting const iterators to iterators is ill-advised even for vector and string, because its portability is doubtful.
If you have access to the container a const_iterator came from, there is a safe, portable way to get its corresponding iterator, and it involves no casts that circumvent the type system. Here’s the essence of the solution, though it has to be modified slightly before it will compile:
// as before
typedef deque<int> IntDeque;
typedef IntDeque::iterator Iter;
typedef IntDeque::const_iterator
ConstIter;
IntDeque d;
ConstIter ci;
... // make ci point into d
// initialize i to d.begin()
Iter i(d.begin());
// move i up to where ci is
// (but see below for why this must
// be tweaked before it will compile)
advance(i, distance(i, ci));
This approach is so simple and straightforward, it’s startling. To get an iterator pointing to the same container element as a const_iterator, create a new iterator at the beginning of the container, and then move it forward until it’s as far from the beginning of the container as the const_iterator is! This task is facilitated by the utility algorithms advance and distance, both of which are declared in <iterator>. The distance algorithm reports how far apart two iterators into the same container are, and advance moves an iterator a specified distance. When i and ci point into the same container, the expression advance(i, distance(i, ci)) makes i and ci point to the same place in the container.
Well, it would if it would compile, but it won’t. To see why, look at the declaration for distance:
template <typename InputIterator>
typename
iterator_traits<InputIterator>::difference_type
distance(InputIterator first,
InputIterator last);
Don’t get hung up on the fact that the return type of the function is 56 characters long and mentions dependent types like difference_type. Instead, focus your attention on the uses of the type parameter InputIterator:
template <typename InputIterator>
typename
iterator_traits<InputIterator>::difference_type
distance(InputIterator first,
InputIterator last);
When faced with a call to distance, your compilers must deduce the type represented by InputIterator by looking at the arguments used in the call. Look again at the call to distance in the code I said wasn’t quite right:
// move i up to where ci is advance(i, distance(i, ci));
Two parameters are passed to distance, i and ci. i is of type Iter, which is a typedef for deque<int>::iterator. To compilers, that implies that InputIterator in the call to distance is deque<int>::iterator. The ci parameter, however, is of type ConstIter, which is a typedef for deque<int>::const_iterator. That implies that InputIterator is of type deque<int>::const_iterator. It’s not possible for InputIterator to be two different types at the same time, so the call to distance fails, typically yielding some long-winded error message that may or may not indicate that the compiler couldn’t figure out what type InputIterator is supposed to be.
To get the call to compile, you must eliminate the ambiguity. The easiest way to do that is to explicitly specify the type parameter to be used by distance, thus obviating the need for your compilers to figure it out for themselves:
// figure the distance between // i and ci (as const_iterators), // then move i that distance advance(i, distance<ConstIter>(i, ci));
We now know how to use advance and distance to get an iterator corresponding to a const_iterator, but we have so far side-stepped a question of considerable practical interest: How efficient is this technique? The answer is simple. It’s as efficient as the iterators allow it to be. For random access iterators (such as those sported by vector, string, and deque), it’s a constant-time operation. For bidirectional iterators (i.e., those for all other standard containers and for some implementations of the hashed containers), it’s a linear-time operation.
Because it may take linear time to produce an iterator equivalent to a const_iterator, and because it can’t be done at all unless the container for the const_iterator is available when the const_iterator is, you may wish to rethink designs that require producing iterators from const_iterators.
