Understanding Iterators in the STL

I'm being lazy. So I would not type describing what an iterator is and how they're used, especially when there're already lots of articles online that you can read yourself.

Here are few that I can quote for a start, proividing the links to complete articles:

MSDN says,

Iterators are a generalization of pointers, abstracting from their requirements in a way that allows a C++ program to work with different data structures in a uniform manner. Iterators act as intermediaries between containers and generic algorithms. Instead of operating on specific data types, algorithms are defined to operate on a range specified by a type of iterator. Any data structure that satisfies the requirements of the iterator may then be operated on by the algorithm. There are five types or categories of iterator [...]

By the way, it seems the MSDN has taken the text in bold from C++ Standard itself, specifically from the section §24.1/1 which says

Iterators are a generalization of pointers that allow a C + + program to work with different data structures (containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, the library formalizes not just the interfaces but also the semantics and complexity assumptions of iterators. All iterators i support the expression *i, resulting in a value of some class, enumeration, or built-in type T, called the value type of the iterator. All iterators i for which the expression (*i).m is well-defined, support the expression i->m with the same semantics as (*i).m. For every iterator type X for which equality is defined, there is a corresponding signed integral type called the difference type of the iterator.

cplusplus says,

In C++, an iterator is any object that, pointing to some element in a range of elements (such as an array or a container), has the ability to iterate through the elements of that range using a set of operators (at least, the increment (++) and dereference (*) operators).

The most obvious form of iterator is a pointer [...]

And you can also read these:

What Is an Iterator?
Iterators in the Standard C++ Library
Iterator (at wiki entry)

Have patience and read all these. Hopefully, you will have some idea what an iterator is, in C++. Learning C++ requires patience and time.

There are three building blocks in the STL:

Containers
Algorithms
Iterators

At the conceptual level containers hold data. That by itself isn't very useful, because you want to do something with the data; you want to operate on it, manipulate it, query it, play with it. Algorithms do exactly that. But algorithms don't hold data, they have no data -- they need a container for this task. Give a container to an algorithm and you have an action going on.

The only problem left to solve is how does an algorithm traverse a container, from a technical point of view. Technically a container can be a linked list, or it can be an array, or a binary tree, or any other data structure that can hold data. But traversing an array is done differently than traversing a binary tree. Even though conceptually all an algorithm wants is to "get" one element at a time from a container, and then work on that element, the operation of getting the next element from a container is technically very container-specific.

It appears as if you'd need to write the same algorithm for each container, so that each version of the algorithm has the correct code for traversing the container. But there's a better solution: ask the container to return an object that can traverse over the container. The object would have an interface algorithms know. When an algorithm asks the object to "get the next element" the object would comply. Because the object came directly from the container it knows how to access the container's data. And because the object has an interface the algorithm knows, we need not duplicate an algorithm for each container.

This is the iterator.

The iterator here glues the algorithm to the container, without coupling the two. An iterator is coupled to a container, and an algorithm is coupled to the iterator's interface. The source of the magic here is really template programming. Consider the standard copy() algorithm:

template<class In, class Out>
Out copy(In first, In last, Out res)
{
    while( first != last ) {
        *res = *first;
        ++first;
        ++res;
    }
    return res;
}

The copy() algorithm takes as parameters two iterators templated on the type In and one iterator of type Out. It copies the elements starting at position first and ending just before position last, into res. The algorithm knows that to get the next element it needs to say ++first or ++res. It knows that to read an element it needs to say x = *first and to write an element it needs to say *res = x. That's part of the interface algorithms assume and iterators commit to. If by mistake an iterator doesn't comply with the interface then the compiler would emit an error for calling a function over type In or Out, when the type doesn't define the function.

An iterator is to an STL container what a pointer is to an array. You can think of them as pointer objects to STL containers. As pointers, you will be able to use them with the pointer notation (e.g. *iElementLocator, iElementLocator++). As objects, they will have their own attributes and methods (http://www.cplusplus.com/reference/std/iterator).

An iterator is not the same as the container itself. The iterator refers to a single item in the container, as well as providing ways to reach other items.

Consider designing your own container without iterators. It could have a size function to obtain the number of items it contains, and could overload the [] operator to allow you to get or set an item by its position.

But "random access" of that kind is not easy to implement efficiently on some kinds of container. If you obtain the millionth item: c[1000000] and the container internally uses a linked list, it will have to scan through a million items to find the one you want.

You might instead decide to allow the collection to remember a "current" item. It could have functions like start and more and next to allow you to loop through the contents:

c.start();
while (c.more()) 
{
    item_t item = c.next();

    // use the item somehow
}

But this puts the "iteration state" inside the container. This is a serious limitation. What if you wanted to compare each item in the container with every other item? That requires two nested loops, both iterating through all the items. If the container itself stores the position of the iteration, you have no way to nest two such iterations - the inner loop will destroy the working of the outer loop.

So iterators are an independent copy of an iteration state. You can begin an iteration:

container_t::iterator i = c.begin();

That iterator, i, is a separate object that represents a position within the container. You can fetch whatever is stored at that position:

item_t item = *i;

You can move to the next item:

i++;

With some iterators you can skip forward several items:

i += 1000;

Or obtain an item at some position relative to the position identified by the iterator:

item_t item = i[1000];

And with some iterators you can move backwards.

And you can discover if you've reached beyond the contents of the container by comparing the iterator to end:

while (i != c.end())

You can think of end as returning an iterator that represents a position that is one beyond the last position in the container.

An important point to be aware of with iterators (and in C++ generally) is that they can become invalid. This usually happens for example if you empty a container: any iterators pointing to positions in that container have now become invalid. In that state, most operations on them are undefined - anything could happen!

Understanding Iterators in the STL

Tags:

C++

Stl

Iterator

Related

Recent Posts