At first glance, STL iterators appear straightforward. Look more closely, however, and youll notice that containers actually offer four different iterator types:
const_reverse_iterator. From there its only a matter of time until you note that of these four types, only one is accepted by containers in certain forms of
erase. Thats when the questions begin. Why four different types? What is the relationship among them? Are they interconvertible? Can the different types be mixed in calls to algorithms and STL utility functions? How do these types relate to containers and their member functions?
This article, drawn from my new book, Effective STL, answers these questions through three specific guidelines that will help you get the most out of STL iterators.
Guideline 1: Prefer iterator to const_iterator, reverse_iterator, and const_reverse_iterator
container<T>, the type
iterator acts like a
const_iterator acts like a
const T* (which you may also see written as a
T const *; they mean the same thing). Incrementing an
iterator or a
const_iterator moves you to the next element in the container in a traversal starting at the front of the container and proceeding to the back.
const_reverse_iterator also act like
const T*, respectively, except that incrementing these iterator types moves you to the next element in the container in a traversal from back to front.
Let me show you two things. First, take a look at some signatures for
iterator insert(iterator position, const T& x); iterator erase(iterator position); iterator erase(iterator rangeBegin, iterator rangeEnd);
Every standard container offers functions analogous to these, though the return types vary, depending on the container type. The thing to notice is that these functions demand parameters of type
iterator. Though containers support four iterator types, one of those types has privileges the others do not have. That type is
iterator is special.
The second thing I want to show you is this diagram, which displays the conversions that exist among iterator types:
The diagram shows that there are implicit conversions from
reverse_iterator, and from
const_reverse_iterator. It also shows that a
reverse_iterator may be converted into an
iterator by using the
base member function, and a
const_reverse_iterator may similarly be converted into a
base. The diagram does not show that the iterators obtained from
base may not be the ones you want. Well explore that issue in Guideline 3.
Observe that there is no way to get from a
const_iterator to an
iterator or from a
const_reverse_iterator to a
reverse_iterator. This is important, because it means that if you have a
const_iterator or a
const_reverse_iterator, youll find it difficult to use those iterators with some container member functions. Such functions demand
iterators, and since theres no conversion path from the const iterator types back to
iterator, the const iterator types are largely useless if you want to use them to specify insertion positions or elements to be erased.
Dont be fooled into thinking that this means const iterators are useless in general. Theyre not. Theyre perfectly useful with algorithms, because algorithms dont usually care what kind of iterators they work with, as long as they are of the appropriate category. Const iterators are also acceptable for many container member functions. Its only some forms of
erase that are picky.
I wrote that const iterators are largely useless if you want to specify insertion positions or elements to be erased. The implication is that they are not completely useless. Thats true. They can be useful if you can find a way to get an
iterator from a
const_iterator or from a
const_reverse_iterator. Thats often possible. It isnt always possible, however, and even when it is, the way to do it isnt terribly obvious. It may not be terribly efficient, either. Guideline 2 is devoted to this topic, so Ill defer it until then. For now, we have enough information to understand why it often makes sense to prefer
iterators to const and reverse iterators:
- Some versions of
iterators. If you want to call those functions, youre going to have to produce
Constand reverse iterators wont do.
- Its not possible to implicitly convert a
constiterator to an
iterator, and the technique described in Guideline 2 for generating an
const_iteratoris neither universally applicable nor guaranteed to be efficient.
- Conversion from a
iteratormay require iterator adjustment after the conversion. Guideline 3 explains when and why.
All these things conspire to make working with containers easiest, most efficient, and least likely to harbor subtle bugs if you prefer
iterators to their
const and reverse colleagues.
Practically speaking, you are more likely to have a choice when it comes to
const_iterators. The decision between
reverse_iterator is often made for you. You either need a front-to-back traversal or a back-to-front traversal, and thats pretty much that. You choose the one you need, and if that means choosing
reverse_iterator, you choose
reverse_iterator and use
base to convert it to an
iterator (possibly preceded by an offset adjustment, as well see in Guideline 3) when you want to make calls to container member functions that require
When choosing between
const_iterators, there are reasons to choose
iterators even when you could use a
const_iterator and when you have no need to use the iterator as a parameter to a container member function. One of the most irksome involves comparisons between
const_iterators. I hope we can all agree that this is reasonable code:
// STL container and iterator types // are easier to work with if you // use some typedefs typedef deque<int> IntDeque; typedef IntDeque::iterator Iter; typedef IntDeque::const_iterator ConstIter; Iter i; ConstIter ci; ... // make i and ci point into // the same container // compare an iterator and a // const_iterator if (i == ci) ...
All were doing here is comparing two iterators into a container, the kind of comparison thats the bread and butter of the STL. The only twist is that one object is of type
iterator and one is of type
const_iterator. This should be no problem. The
iterator should be implicitly converted into a
const_iterator, and the comparison should be performed between two
With well-designed STL implementations, this is precisely what happens, but with other implementations, the code will not compile. The reason is that such implementations declare
const_iterators as a member function instead of as a non-member function, but the cause of the problem is likely to be of less interest to you than the workaround, which is to swap the order of the iterators, like this:
// workaround for when the // comparison above won't compile if (ci == i) ...
This kind of problem can arise whenever you mix
const_reverse_iterators) in the same expression, not just when you are comparing them. For example, if you try to subtract one random access iterator from another,
if (i - ci >= 3) ... // if i is at // least 3 // beyond ci ...
your (valid) code may be (incorrectly) rejected if the iterators arent of the same type. The workaround is what youd expect (swap the order of
ci), but in this case you have to take into account that you cant just replace
i - ci with
ci - i:
// workaround for when the above // won't compile if (ci + 3 <= i) ...
The easiest way to guard against these kinds of problems is to minimize your mixing of iterator types, and that, in turn, leads back to preferring
const_iterators. From the perspective of const correctness (a worthy perspective, to be sure), staying away from
const_iterators simply to avoid potential implementation shortcomings (all of which have straightforward workarounds) seems unjustified, but in conjunction with the anointed status of
iterators in some container member functions, its hard to avoid the practical conclusion that
const_iterators are not only less useful than
iterators, sometimes theyre just not worth the trouble.