EECS 280: Programming and Introductory Data Structures

Section 17 Iterators

University of Michigan at Ann Arbor

Last Edit Date: 04/05/2023

Disclaimer and Term of Use:

We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

This personal note is adapted from Professor Amir Kamil, Andrew DeOrio, James Juett, Sofia Saleem, and Saquib Razak. Please contact us to delete this file if you think your rights have been violated.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Introduction to Iterator¶

We start off with something like a pointer that "points" to the beginning of the list, move it forward one element at a time, and stop when we get past the end of the list:

List<int> list;
...
for (Iterator it = list.begin(); it != list.end(); ++it) {
  cout << *it << endl;
}

We use an object called an iterator to iterate over the elements. The pattern above is called traversal by iterator, and it is a generalization of traversal by pointer.

To traverse with an iterator, it must provide the following operations:

dereference (prefix *)
increment (prefix ++)
equality checks (== and !=)

In addition, the container itself must provide two member functions:

begin() returns an iterator to the start of the sequence
end() returns a "past-the-end" iterator that represents a position that is past the last element of the sequence

An iterator is a class-type object that has the same interface as a pointer. We provide the same interface by overloading the required operators:

 1     template <typename T>
 2     class Iterator {
 3     public:
 4       T & operator*() const;
 5
 6       Iterator &operator++();
 7
 8       bool operator==(Iterator rhs) const;
 9
10       bool operator!=(Iterator rhs) const;
11     };

The unary * operator is overloaded to return the element the iterator is pointing to by reference. The prefix ++ operator moves the iterator to point to the next element in the sequence, and it returns the iterator itself by reference. This allows the operator to be chained:

++++it;

The equality operators determine if the receiver points to the same element as the rhs iterator.

Unlike most class types, we pass iterators by value – they are generally small, and it is standard practice in C++ to make copies of them when we pass them to a function, just like we would for pointers.

Before we proceed to implement the operators, we need a data representation. The representation of an iterator is specific to a particular kind of container. For a linked list, traversal by iterator is just an abstraction over the traversal in print():

A list iterator is an abstraction over a pointer to a node.
The call list.begin() returns an iterator constructed from first.
The past-the-end iterator returned by list.end() is represented by a null pointer.
Comparing two iterators compares their underlying node pointers.
Incrementing an iterator moves its node pointer to the next node using the original node's next member.
Derferencing the iterator obtains the datum member of the underlying node.

Thus, we represent an iterator with just a pointer to a node.

template <typename T>
class Iterator {
  ...
private:
  Node *node_ptr;
};

As mentioned above, we use a null pointer for an iterator that is past the end of a list. The end condition for the traversal in print() is when the node pointer is null – after the traversal reaches the last node, it sets the pointer to the value of the last node's next member, which is null according to the list’s representation invariant. Thus, it makes sense to use a null pointer to represent a past-the-end iterator.

Now that we have a representation, we should consider representation invariants. It is the case that node_ptr will either be null or point to a valid list node when the iterator is created. However, we will see that an iterator may be invalidated, which will result in node_ptr pointing to an invalid node. Thus, there is no invariant that will hold for a list iterator’s representation.

Iterator Definition¶

Before we proceed to implement Iterator, observe the following issues with its definition:

Node is not a top-level type, but a member of the List class template, so it cannot be named from the outside without the scope-resolution operator.
The Node struct is private, so it cannot be accessed from outside code.
The iterator type is associated with List, so it should be encapsulated within the List template.

We can solve these issues by defining Iterator as a member of the List template:

template <typename T>
class List {
  ...
private:
  struct Node {
    int datum;
    Node *next;
  };

public:
  class Iterator {
  public:
    T & operator*() const;

    Iterator &operator++();

    bool operator==(Iterator rhs) const;

    bool operator!=(Iterator rhs) const;

  private:
    Node *node_ptr;
  };

private:
  Node *first;
  Node *last;
};

Iterators provide a common interface for iteration

A generalized version of traversal by pointer
An iterator "points" to an element in a container and can be "incremented" to move to the next element

Iterators support these operations

Dereference - access the current element (*it)
Increment - move forward to the next element (++it)
Equality - check if two iterators point to the same place (it1 == it2 or it1 != it2)

Traverse by Iterator¶

The big picture

Walk an iterator across the elements
When you want an element, just dereference the iterator

 1     Iterator end = list.end();
 2     for (Iterator it = list.begin(); it != end; ++it) {
 3       cout << *it << endl;
 4     }

Dereference Operator¶

The dereference operator requires that the iterator is dereferenceable, which means that it is pointing to a valid element in the container. We cannot in general check that this is the case, but we can check whether the iterator is a past-the-end iterator:

 1     // REQUIRES: this is a dereferenceable iterator
 2     // EFFECTS:  Returns the element that this iterator points to.
 3     template <typename T>
 4     T & List<T>::Iterator::operator*() const {
 5       assert(node_ptr);  // check whether this is a past-the-end iterator
 6       return node_ptr->datum;
 7     }

Note: This format is used when it is defined outside of the class. We return by reference to allow both reading and writing through an iterator. An iterator is dereferenceable if it points to some element in the container.

The dereference operator does not modify the iterator. In addition, while the function returns an object by reference to non-const, modifying that object does not modify the iterator, since the object is not a member of the iterator itself. Thus, the dereference operator can be declared as a const member function.

Increment Operator¶

The operator++() function modifies the iterator by moving it to "point to" the next element, so it cannot be declared as const.

As with dereference, the past-the-end iterator cannot be incremented – node_ptr would be null, and there wouldn't be a next pointer to move the iterator to.

 1     // REQUIRES: this is a dereferenceable iterator
 2     // EFFECTS:  Returns the element that this iterator points to.
 3     template <typename T>
 4     typename List<T>::Iterator & List<T>::Iterator::operator++() {
 5       assert(node_ptr);  // check whether this is a past-the-end iterator
 6       node_ptr = node_ptr->next;
 7       return *this;
 8     }

The function moves the iterator to the next element by following the next pointer of the current node. Once the iterator has been moved, the function returns the iterator by reference, in keeping with the pattern for prefix increment.

Note: This format is used when it is defined outside of the class. The postfix increment operator can be overloaded as well. To distinguish its signature from prefix, C++ uses a dummy int parameter for postfix.

 1     template <typename T>
 2     typename List<T>::Iterator List<T>::Iterator::operator++(int) {
 3       assert(node_ptr);  // check whether this is a past-the-end iterator
 4       Iterator tmp = *this;               // make a copy of this iterator
 5       node_ptr = node_ptr->next;
 6       return tmp;                                      // return the copy
 7     }

Note: This format is used when it is defined outside of the class.

Equality Operator¶

Two iterators are defined as equal if either they are both past the end, or they "point to" the same element in the same list. Thus, they are equal exactly when their node_ptr members point to the same node.

 1     template <typename T>
 2     bool List<T>::Iterator::operator==(Iterator rhs) const {
 3       return node_ptr == rhs.node_ptr;
 4     }
 5
 6     template <typename T>
 7     bool List<T>::Iterator::operator!=(Iterator rhs) const {
 8       return node_ptr != rhs.node_ptr;
 9     }

Note: This format is used when it is defined outside of the class.

Creating Iterators¶

We need to provide two constructors for Iterator.

class Iterator {
public:
  // Public constructor. Creates an end Iterator
  Iterator()
    : node_ptr(nullptr) { }
  ...
private:
  // Private constructor. Creates an Iterator pointing
  // to the specified Node.
  Iterator(Node *np)
    : node_ptr(np) { }
  Node *node_ptr;
};

We can now implement begin() and end() member functions in List that return a start and past-the-end iterator, respectively.

template <typename T>
class List {
  ...
public:
  // EFFECTS: Returns an iterator that points to the first element,
  //          or a past-the-end iterator if this list is empty.
  Iterator begin() {
    return Iterator(first);
  }

  // EFFECTS: Returns a past-the-end iterator.
  Iterator end() {
    return Iterator();
  }
};

The begin() function returns an iterator that points to the first element in the list.

However, if the list is empty, first is null; this is the representation of a past-the-end iterator, so begin() returns such an iterator when the list is empty.

The end() function returns a default-constructed past-the-end iterator.

Unfortunately, the implementation of begin() does not compile. A private member is only accessible from within the scope of the class that defines the member. The private Iterator constructor is a member of Iterator, but it is being accessed from outside the Iterator class. On the other hand, Iterator is within the scope of List, so it can access private List members such as Node. Thus, a nested class can access private members of the outer class, but not vice versa.

Friend Declarations¶

The solution to the problem above is a friend declaration, in which a class gives an outside entity access to the class’s private members.

template <typename T>
class List {
public:
  ...
  class Iterator {
    friend class List;     // Friend declaration, which lets List access the private members of Iterator
  public:
    Iterator() : node_ptr(nullptr) { }
    ...
  private:
    Iterator(Node *np) : node_ptr(np) { }
    Node *node_ptr;
  };
  Iterator begin() { return Iterator(first); }     // List member functions, like begin(), canaccess the private constructor
  Iterator end() { return Iterator(); } 
  ...
private:
  Node *first;
  ...
};

We now have all the pieces to implement and use the traversal by iterator pattern.

 1     List<int> list;
 2     int arr[3] = { 1, 2, 3 };
 3     fillFromArray(list, arr, 3);
 4
 5     List<int>::Iterator end = list.end();
 6     for (List<int>::Iterator it = list.begin(); it != end; ++it) {
 7       cout << *it << endl;
 8     }

The typename Keyword

The following is a generic function of iterator traversal. The typename keyword is required here.

 1     template <typename T>
 2     void print_list(const List<T> list) {
 3       typename List<T>::Iterator end = list.end();
 4       for (typename List<T>::Iterator it = list.begin(); it != end; ++it) {
 5         cout << *it << endl;
 6       }
 7     }

Iterator Invalidation¶

Invalidated interators are like dangling pointers - it is no longer safe to dereference them and try to access the object they point to.
Seemingly innocuous operations on a container can result in iterator invalidation.
- For example, iterators pointing into a vector are invalidated if an operation causes a grow.
A function's documentation should specify which iterators, if any, it may invalidate.