At first glance, STL iterators appear straightforward. Look more closely, however, and youll notice that containers actually offer four different iterator types: iterator
, const_iterator
, reverse_iterator
, and 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 insert
and 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
For a container<T>
, the type iterator
acts like a T*
, while 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. reverse_iterator
and const_reverse_iterator
also act like T*
and 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 insert
and erase
in vector<T>
:
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
. Not const_iterator
, not reverse_iterator
, not const_reverse_iterator
. Always iterator
. Though containers support four iterator types, one of those types has privileges the others do not have. That type is iterator
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 iterator
to const_iterator
, from iterator
to reverse_iterator
, and from reverse_iterator
to const_reverse_iterator
. It also shows that a reverse_iterator
may be converted into an iterator
by using the reverse_iterator
s base
member function, and a const_reverse_iterator
may similarly be converted into a const_iterator
via 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 iterator
s, 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 insert
and 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 iterator
s to const and reverse iterators:
- Some versions of
insert
anderase
requireiterator
s. If you want to call those functions, youre going to have to produceiterator
s.Const
and reverse iterators wont do. - Its not possible to implicitly convert a
const
iterator to aniterator
, and the technique described in Guideline 2 for generating aniterator
from aconst_iterator
is neither universally applicable nor guaranteed to be efficient. - Conversion from a
reverse_iterator
to aniterator
may 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 iterator
s to their const
and reverse colleagues.
Practically speaking, you are more likely to have a choice when it comes to iterator
s and const_iterator
s. The decision between iterator
and 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 iterator
s.
When choosing between iterator
s and const_iterator
s, there are reasons to choose iterator
s 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 iterator
s and const_iterator
s. 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 const_iterator
s.
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 operator==
for const_iterator
s 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 iterator
s and const_iterator
s (or reverse_iterator
s and const_reverse_iterator
s) 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 i
and 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 iterator
s to const_iterator
s. From the perspective of const correctness (a worthy perspective, to be sure), staying away from const_iterator
s simply to avoid potential implementation shortcomings (all of which have straightforward workarounds) seems unjustified, but in conjunction with the anointed status of iterator
s in some container member functions, its hard to avoid the practical conclusion that const_iterator
s are not only less useful than iterator
s, sometimes theyre just not worth the trouble.