Working with the STL iterators

Almost every programmer some how gets involved with STL iterators while programming. I’m quite fond of these concepts. So what exactly is an iterator?

STL stands for the Standard Template Library which has different flavors or implementations floating around with different compilers but the concept and structure behind all of them is the same. It’s a bunch of c++ classes which makes the life of programmer’s easy by providing implementations for popular data structure algorithms like…

  1. Singly/doubly linked lists
  2. Stack
  3. Queue
  4. DQueue
  5. Vector – used by almost everyone
  6. Map
  7. Hashed maps
  8. And others

So our point of discussion is what the heck does an iterator do and what is it for? Well as the name suggests it’s a way to traverse a list of items which can be ordered or unordered, in a generic fashion. Let’s see some examples of iterators…

[sourcecode language=’cpp’]typedef std::vector IntVector; // Represents a dynamic list of integers
IntVector Ints;
Ints.push_back( 10 ); // Add one int
Ints.push_back( 20 ); // Add one more int[/sourcecode]

Now we have a vector of integers with two ints. So to get first integer in this list we use following function…

[sourcecode language=’cpp’]IntVector::iterator Itr = Ints.begin(); // First int[/sourcecode]

And to get to next integer we simply use ++Itr/Itr++. Every STL container has it’s own flavor of ++(pre and post) operator. For e.g. for a list it will be moving to next element, for an output stream iterator it will be moving to next field in a file etc. So by now you might have understood how powerful the concept of an iterator is. In STL for traversing a container according to standard we must always use an iterator.

Note that it’s not correct to directly do a ‘+1’ or ‘-1’ with an iterator. It’s dangerous when container for an iterator changes. It’s quite ok with a vector (only if the iterator is a pointer) but a big disaster with lists. So for this purpose STL provides us with two functions std::advance and std::distance. As you might have understood by now std::advance advances an iterator by a count and std::distance returns the number of elements between two iterators. This will work with both ordered and unordered containers. So a poor alternative to Ints.size() will be std::distance(Ints.begin(), Ints.end()) ;). To increment our previous Itr by one we’ll do std::advance(Itr, 1) instead of Itr + 1. Also never check for NULL on an iterator, always check against corresponding container’s end() function since this is what represents an invalid case in STL containers.

If you’ve noticed a detail of iterators, it’s that they are very generic. For e.g. our previous Itr object represents an iterator for a std::vector but even if we change the container type to std::list still there won’t be any change in iterator part. That’s cool isn’t. I enjoy programming in STL these days. I’m trying to get into the details of this wonderful library. Will keep posting bits and bytes on whatever I find in this library.

Appreciate your comments...