Iterators in C++

While most computing students are (hopefully) familiar with the concept of loops, they often don’t move past the most basic of loop patterns. For instance, suppose we have a vector called my_numbers. Code I frequently see follows this pattern:

Create an integer and set it to the first element’s index in the vector.
Iterate up to the size of the vector.
Add 1 to the integer keeping track of our index after each loop iteration.

For example, we might have

for(int i=0; i<my_numbers.size(); ++i){
	... do stuff ...
}

This pattern isn’t inherently wrong, and it will certainly loop over your collection. The problem with it though is one of longer-term code maintenance. This pattern will only work on data structures that are sequence types (and in this case only ones that have a size() method). A sequence type is a data structure for which each element it is storing has an integer index, and one index follows another. Common sequence types are arrays, vectors, and lists. Data types that are not sequence types exist too - consider dictionaries, sets, and heaps for instance. Most of us haved used dictionaries before; they are a data structure with an object (often a string) that is used as the index. Later on, if we decide that our vector isn’t the best data structure, we might choose to change the data structure declaration in our code from a vector to a dictionary. However, if we used this common for-loop pattern, we must also modify our loop code.

Why is that a problem? Well first, humans aren’t great at maintaining code. Anytime we attempt to change our code we run the risk of introducing new bugs. Second, it is extra work that doesn’t need to be done. It turns out that we can write a loop in such a way that it works regardless of the data type we choose. We call this way the Iterator Pattern. An iterator is simply an object that points to another object in a collection (like a list, array, set, etc.). To use it, we modify our pattern from before:

Create an iterator variable and set it equal to the object we want to point to first.
Iterate until we get to the object we want to point to last.
Change the pointer to the next object after each loop iteration.

For our vector, it might look like this:

for(auto it = my_numbers.begin(); it != my_numbers.end(); ++it){
	... do stuff ...
}

The two function calls - begin() and end() are defined by the data structure. The begin() function returns an object that points to the “first” object in our collection - however that is defined by the data structure. For our sequence types, that might be index 0. For a dictionary, it might be the object that was added to the dictionary first. Regardless, the data structure decides. The other method - end() simply tells us we are at the “last” element. The code ++it or it++ simply tells our iterator to point the the next item. Some iterators are bidirectional; for those you might be able to use --it to go to the prior object.

Some of you might be wondering what the auto keyword is doing. This is a C++ feature (from I think the 2011 and up standard) that automatically determines our data type for us. If we had a std::vector<int> for our my_numbers collection, this would return a std::vector<int>::iterator. But no one wants to type all that out each time :-P. Be careful using auto; it should only be used when its meaning is clear. We wouldn’t want to create an arbitrary int and use auto for it, as that wouldn’t tell people looking at our code what the intent of the variable was.

To recap, let’s look at some sample code. We might have originally had code that looked like this:

std::vector<int> my_numbers;

... code that filled up my_numbers ...

for(int i=0; i<my_numbers.size(); ++i){
	std::cout << my_numbers[i] << "\t";
}

If we had then changed my_number to a set (so that we wouldn’t keep duplicates of a number), our loop would no longer work as sets do not have an index. However, if we had written the code using the iterator pattern:

std::vector<int> my_numbers;

... code that filled up my_numbers ...

for(auto it=my_numbers.begin(); it != my_numbers.end(); ++it){
	std::cout << *it << "\t";
}

We could simply change our vector to a set:

std::set<int> my_numbers;

And the loop would continue to work as written.

Much of the C++ Standard Library expects you to use iterators. However, this is not a topic that is strictly the domain of C++. Most languages have iterators, though the syntax of using them may differ slightly. Regardless, they are an important tool that can “level-up” your coding.