C++ Programming: Make Your Way through a List

By Stephen R. Davis

The C++ programmer iterates through an array by providing the index of each element. However, this technique doesn’t work for containers like list that don’t allow for random access. One could imagine a solution based in methods such as getFirst() and getNext(); however, the designers of the Standard Template Library wanted to provide a common method for traversing any type of container.

For this, the Standard Template Library defines the iterator.

An iterator is an object that points to the members of a container. In general, every iterator supports the following functions:

  • A class can return an iterator that points to the first member of the collection.

  • The iterator can be moved from one member to the next.

  • The iterator returns an indication when it reaches the end of the list.

  • The program can retrieve the element pointed to by the iterator.

The Standard Template Library also provides reverse iterators for moving backward through lists. Everything here about iterators applies equally for reverse iterators.

The code necessary to iterate through a list is different from that necessary to traverse a vector (to name just two examples). However, the iterator hides these details.

The method begin() returns an iterator that points to the first element of a list. The indirection operator*() retrieves a reference to the object pointed at by the iterator. The ++ operator moves the iterator to the next element in the list.

A program continues to increment its way through the list until the iterator is equal to the value returned by end(). The following code snippet starts at the beginning of a list of students and displays each of their names:

void displayStudents(list<Student>& students)
    // allocate an iterator that points to the first
    // element in the list
    list<Student>::iterator iter = students.begin();
    // continue to loop through the list until the
    // iterator hits the end of the list
    while(iter != students.end())
        // retrieve the Student the iterator points at
        Student& s = *iter;
        cout << s.sName << endl;
        // now move the iterator over to the next element
        // in the list

Declarations for iterators can get very complex. This is probably the best justification for the auto declaration introduced with the ’11 standard:

for(auto iter = students.begin(); iter != students.end(); iter++)
    cout << iter->sName << endl;

This declares iter to be an iterator of whatever type is returned by the method list<Student>::begin(), avoiding the tortured declarations shown in the earlier code snippet. How cool is that!