Iterators give you the ability to navigate from one item to another in a collection. Why is this so special? Now that you know how to work with various collections, you know that they’re structured very differently. An array just needs to move a pointer to the next item. A list needs to follow wherever the next pointer leads. A binary tree needs to go up and down the tree. Iterators give you a common way to navigate no matter what kind of collection you’re using.
If you have a collection like this:
list<int> myNumbers;
Then you can access the first number in the list like this:
auto beginIter = myNumbers.begin();
And you can access the end iterator like this:
auto endIter = myNumbers.end();
Then you can create a for loop to process items in the list like this:
for (; beginIter != endIter; ++beginIter)
{
// Add your code here.
}
Listen to the full episode about iterators, or you can also read the full transcript below.
Transcript
Iterators in effect give you a way of not just navigating from one item to another but also of representing a specific location in a collection.
Since there are different kinds of collections, that means there are different kinds of iterators. So how do you know which iterator to use? The really nice thing is that you don’t have to worry about this. You just ask whatever collection you happen to be using for an iterator and let it figure out how to give you the correct iterator.
This way of thinking is something you grow into as you become more comfortable with object-oriented programming. Let the objects themselves determine how they behave and how they’re related to other types. This is why I urge you to learn an object oriented language first. It’s sort of like how you’re most comfortable with your first spoken language. It takes a lot of work to become as comfortable with another spoken language. The same thing applies to programming. If you learn a procedural language first such as the C language, then you’re naturally going to approach problems with that mindset.
Asking a collection for an iterator and not needing to worry about what type of iterator you get is just the beginning though. Let me give you an example.
Have you ever tried to count while somebody else was also counting out loud? Maybe the other person was just trying to confuse you and counting randomly or backwards. Many of us get our counting confused. At the very least we have to put extra concentration into our own counting, right?
The same thing happens with programming. Maybe you have two collections and one is a list while the other is a binary tree. You want to start processing one item at a time from each collection. Without iterators, this would be a chore because you’d have to write code to navigate two different structures and keep them separate. With iterators though, you just ask for an iterator from each collection and let each one track its own progress as you move from one item to the next.
But it gets even better than that. You don’t have to ask for just one iterator from a collection. Maybe you need to pause for a while at one item while continuing on at the same time. You can ask for two iterators and use each one to navigate items in the collection independently of the other iterator.
If you know about range-based for loops, then you might be wondering why you need iterators. A range-based for loop usually reads something like this:
◦ “for each object called inventory in the backpack collection perform this block of code”
Using a range-based for loop really is the preferred way to write your code if you want to run some code for every item in the collection. It establishes your intent better than a for loop and iterators. But if you don’t want to process all the items, or maybe you need to save an iterator to a particular item so you can come back to it later, then a range-based for loop no longer fits. A range-based for loop actually uses iterators itself but just simplifies your code when you want to process all the items.
I’ll explain some more capabilities and how you can use iterators right after this message from our sponsor.
( Message from Sponsor )
How do you ask for an iterator? This will be different for each language so I’ll explain how you work with iterators in C++ in order to be as specific as possible. The concepts should be similar if you’re using a different language.
You have two basic methods called begin() and end() that each return an iterator instance. All you need to do is assign the return value from these methods to a couple local variables of the correct type. Let’s call these beginIter and endIter. As long as they’re not equal, or in other words, as long as the begin doesn’t point to the end, then beginIter points to a valid item in the collection.
You can put these in a for loop and increment beginIter each time through the loop so it points to the next item. Eventually beginIter will be incremented to point to the same thing as endIter and you’re done.
It’s important that you realize something very ingenious about this system. You might think that your endIter points to the last item in the collection but it doesn’t. It actually points to a nonexistent item just past the end of the collection. That’s why you can keep incrementing beginIter and working with what it points to all the way until beginIter equals endIter. Once the two iterators are equal, then you’ve completed all the items in the collection. Notice how you don’t need to change the endIter variable. You just use this iterator as-is to test when you’ve reached the end.
You might be wondering about now why the end method returns an iterator that points to some imaginary item outside of the collection. This seems counter intuitive. Why not just work with beginIter right up to and including when it equals endIter? You could do this if the end method returned an iterator that represents the last item in the collection, right? Yes, and that would work. It would work just fine until one day you have a collection that’s empty. Now you’re in trouble. How can the end method return an iterator to the last item when there are no items in the collection and therefore there is no last item? This is the beauty of the C++ iterator system. By defining the end method to always return an iterator to an item that doesn’t exist, then it works in all cases. If you have a collection with no items in it and ask for iterators to the beginning and end, then they’ll both point to the same imaginary location outside of the collection and you can use the same code to know that you’ve reached the end. In all cases, you just keep working with items that your beginIter represents all the way until beginIter and endIter are equal. Then you’re done.
If you have a simple array of integers, then an int pointer works just fine as your iterator. You can increment your pointer to move forward and it knows how many bytes to adjust based on the size of the items in the array. You can also decrement your pointer to go backward through the array. And you can even jump around randomly by adding or subtracting various amounts to your pointer.
These three capabilities define the three basic categories of iterators. This is important because not all iterators will be able to do these things. Remember that a single linked list can only move forward. That means that a single linked list iterator is of type forward iterator.
A double linked list can go forward or backward. Iterators from a double linked list container are said to be bidirectional.
Both the single linked list and double linked list iterators have to follow items one at a time if you want them to move more than one item. They don’t have the ability to move around randomly.
An iterator from a vector though can move forward, backward, and instantly jump to another location. This makes iterators from a vector collection to be called random-access iterators.
An iterator that’s in the random-access category implies that it’s also bidirectional because if you can jump anywhere, then you can definitely jump one position forward or one position backward.
And a bidirectional iterator implies all the capabilities of a forward iterator because if you can go both directions, then you can definitely go forward.
The only category that doesn’t imply any other capabilities is the forward iterators. If you have a forward iterator, then all you know and all you can count on is the ability to move one item at a time in the forward direction.