Introduction to Iterators

General Concept

In libraries of standard data structure containers, like the C++ STL, iterator classes are provided for easy navigation through containers.

The point of an iterator is to provide a consistent syntax for a user (of these libraries) to navigate through any container, without having to know how the container's internal storage is set up. The same syntax can be used to navigate or walk through any type of container.

A motivational example

Suppose we have templated classes for both Vector and Linked List containers, with appropriate features allowing us to declare objects (populated with data) in the following way:

  Vector<int> V = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30};
  LinkeList<int> L = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30};

Question 1: How do we walk through these containers of data?

Suppose we wanted to print out all of the data in each container.

From inside of the vector class, we might write code like this:

  for (int i = 0; i < size; i++)
     cout << array[i] << ' ';

And from inside of the linked list class, we might write code like this:

  T* tempptr = firstPtr;
  while (tempptr != nullptr)
  {
     cout << tempptr->data << ' ';
     tempptr = tempptr->nextPtr;	// walkthrough step
  }

Note that the way we walk through an array and the way we walk through a linked list are different, in code.

Walking through a vector (array) involves using an integer index variable, along with the standard array random-access feature
Walking through a linked list involves using a pointer, which is updated inside a loop with the walkthrough step, as illustrated above

Question 2: How should the USER of these objects walk through the containers?

This question is a little different, because we are not talking about the internals of the container class. The user of such objects would not know the internal private data -- only the provided public interface. What do we want their experience to be like?

GOAL: -- Ideally, we would like the user to have a consistent way to walk through ANY container, regardless of internal storage.

Would the following solution work?

One feature already provided in the standard vector class library is the operator[] overload, along with a size function, so we could walk through a vector object like this:

  for (int i = 0; i < V.size(); i++)
     cout << V[i] << ' ';

So what if we provided an operator[] overload and a size function for the linked list class, as well? Would this syntax work?

  for (int i = 0; i < L.size(); i++)
     cout << L[i] << ' ';

If we had the appropriate overload, this would work syntactically. But, this would not be a good idea for run-time efficiency. Think about how such an operator[] would have to do its job.

Linked lists do not have random-access in the internal storage
Such an operator would always have to start at the beginning and walk through to the correct element, on each call
So to print L[100], the walkthrough would take 100 steps just for that element.
Then for the next item L[101], we have another 101 steps to reach it
This will be very inefficient for large data collections

Ideally, we want the walkthrough of either container to take the same amount of time. To print N things, this should take roughly N steps, no matter the type of container.

Iterators

A more ideal solution is to use an iterator class. This is a class that keeps track of what item we are currently at in a container, along with a technique of how to reach the next one. (Some iterators can also move backwards, allowing us to reach the previous item from "where we currently are").

Iterator Goals

Give users a consistent syntactic way to walk through any type of container
Make it efficient (e.g. printing N things should take roughly N steps)

Note that different languages and/or libraries may use different iterator syntax, but within any one specific library, the goal is to be syntactically consistent for that library's containers. Sample iterator style This sample style is similar to iterators in the Java collection libraries (and is the basis for HW 1 iterators):

  VectorIterator<int> itr = V.GetIterator();

  cout << itr.GetData() << ' ';
  while (itr.HasNext())
  {
    itr = itr.Next();
    cout << itr.GetData() << ' ';
  }

Important elements of the above code:

A GetIterator() function that retrieves an appropriate iterator object from the object itself, so that the iterator is tied to that object
HasNext() function to let us know if there is another piece of data left in the object
Next() function to move the iterator to the next piece of data in the object
GetData() function to retrieve the data at the current iterator position
Iterators may also have a means to move bidirectionally -- which in this case would involve functions Previous() and hasPrevious()

This same syntax could also be set up with an iterator for the LinkedList class in this example, so that this code would work:

  LinkedListIterator<int> itr = L.GetIterator();

  cout << itr.GetData() << ' ';
  while (itr.HasNext())
  {
    itr = itr.Next();
    cout << itr.GetData() << ' ';
  }

Note that this is the same walkthrough code as with the vector.

Iterators in C++ STL

The iterators in the C++ STL libraries will be different than the syntax above. In the STL, operator overloads are used, and iterators are classes that are nested inside the main classes, which we will see in the future. A sample of iterator usage in a C++ STL library:

  for (std::vector<int>::iterator itr = v.begin(); itr != v.end(); itr++)
     cout << *itr << ' ';

We'll delve into this style in future lessons.