Iterators give you the ability to navigate from one item to another in a collection and track a specific position within a collection. This episode is part two and continues describing even more advanced iterator topics.
With both part 1 and part 2 of the iterator episodes, you’ve learned about the following iterator categories:
- Input Iterator – input iterators advance forward anytime you read from them and can only read each item once. You can compare an input iterator with another iterator that represents a end-of-input. This lets you know when you’ve read everything there is to read.
- Output Iterator – output iterators usually advance forward anytime you write a value to wherever the iterator is currently pointing to. You have no way to compare output iterators with another iterator. This means that you can’t compare an output iterator with an end or anything like that. All you can do is write and it’s up to you to figure out when to stop writing.
- Forward Iterator – forward iterators are like input iterators where you have control over when to advance to the next item. You can also write to some if not most forward iterators. And you can compare a forward iterator with another forward iterator and they’ll be equal if they both represent the same item.
- Bidirectional Iterator – bidirectional iterators are like forward iterators with the additional ability to advance forward or move backward. This gives you the ability to backtrack and process items as many times as you need.
- Random-Access Iterator – random-access iterators provide all the capabilities of bidirectional iterators plus the ability to move forward or backward to any item. This means they support pointer arithmetic. Random-access iterators give you the ability to calculate differences between iterators and determine if one iterator is less than or greater than another.
And in addition to the iterator categories, you also now know about iterator adapters. this episode discusses the following iterator adapters:
- Reverse Iterator – reverse iterators are usually available from collections that support at least bidirectional iterators. The reverse iterators start at the end of the collection and advance backwards.
- Move Iterator – move iterators convert an iterator so that the items it refers to can be moved to another collection instead of being copied.
- Insert Iterator – insert iterators come in three varieties, back inserters, front inserters, and general inserters. Insert iterators don’t really advance at all. They just keep adding new items to a collection anytime you write to the iterator.
- Stream Iterator – stream iterators can wrap up input or output streams so you can work with the information in a stream as if it was items in a collection.
Listen to the full episode or read the full transcript below.
Transcript
The first thing to understand is that iterators are a concept. They’re an idea and because of this, anything that behaves like an iterator is an iterator. The previous episode mentioned how you can work with raw pointers in a basic array as if they are iterators. Pointers are iterators because they can be advanced forward or backward and know how to move the appropriate number of bytes. They can move from one item to the next without you needing to worry about how they do this. And they remember what item they currently point to. That’s all it takes for anything to be an iterator.
This means that you can create iterators that look like they follow these rules but actually do very different things. These are still iterators and this is why I decided to talk about these in a second episode. Be ready to think about things in a very different way. Here we go.
The first topic I’ll explain is called reverse iterators. How is a reverse iterator any different than just going backward through a bidirectional iterator? Well going backward means that you have to be decrementing your iterator and that’s an operation that’s not available in forward iterators. So if you have code that only expects to work with forward iterators, then there’s no way for that code to go backward because it will have been written to only go forward. That is unless you trick it by giving the code a reverse iterator. Now your code thinks it’s going forward when in fact, it’s going backward.
Why would you ever want to do this? Doesn’t this seem like just some unnecessary complications? If you know how to drive a car, then you’ll know that turning the steering wheel to the right will cause your car to move toward the right and it doesn’t matter if you’re going forward or backward. You’re going to move toward the right anytime you turn the steering wheel to the right. but what if you have a trailer attached to your car or truck? Going forward doesn’t change anything. But backing up with a trailer takes some getting used to. This is because turning the steering wheel to the right when backing up will cause the trailer to go to the left. It’s backwards and our internal programming needs to adapt.
If this was a computer program though, you could leave the code fairly unchanged by giving it something that behaves in the opposite direction. the code thinks it’s turning the steering wheel to the right and the trailer moves to the right. Problem solved. It worked because turning the steering wheel to the right actually caused it to turn to the left.
Code that works with iterators can be adapted in the same way. The code thinks it’s moving forward when in fact, it’s moving backward. This works because when you increment a reverse iterator, the position that iterator points to becomes the previous position and not the next. So by going forward, you actually end up going backward.
For collection types that expose bidirectional iterators, you can get reverse iterators by calling the rbegin() and rend() methods. These iterators have been adapted to work in reverse and that includes how the end iterator points to an imaginary item outside of the collection. The difference with reverse iterators is that the rbegin method returns an iterator pointing to the last item and the rend method returns an iterator pointing to an item before the collection. This is opposite of how the begin and end methods work. Just something to be aware of.
In addition to explaining reverse iterators, I’ll explain two additional iterator categories and four types of iterator adapters right after this message from our sponsor.
( Message from Sponsor )
You know about forward, bidirectional, and random-access iterator categories from the previous episode. There are two more categories that you can use.
The first category is called input iterators. With these types of iterators, your iterator moves forward as you read or process items. The input stream iterators that I’m about to explain are an example. Input iterators only allow you to read or process an item once because that’s how they advance to the next item.
The second category is called output iterators. This type of iterator advances as you write data. The output stream iterators and inserters that I’m about to explain are examples of output iterators. You might sometimes be able to write multiple values to the same location but this is not guaranteed and normally writing a value will cause the iterator to advance.
As for iterator adapters, well, I snuck one in already. Reverse iterators are considered an iterator adapter because they change the direction that the iterator advances.
I’ll explain the second type, move iterator adapters, quickly. Normally when you work with iterators to specify a range of values to work with, then the values are copied. You can sometimes get better performance by moving values instead of copying them. Move iterator adapters allow you to move items. I’ll explain the concept called move semantics in a future episode. For a real life example of this, just think about what you do when you move to a new house. Do you throw away all your furniture, clothes, and possessions and buy new stuff for your new house. Most of us don’t do that. We normally move our stuff instead of trying to recreate everything.
The third type of iterator adapter is called an insert iterator. This is an example of an output iterator because when you write a value to an insert iterator, it doesn’t overwrite the current position. Instead, it inserts the value that you write. There are three types of insert iterators.
◦ Back inserters append new items to the end of a collection.
◦ Front inserters insert new items to the beginning of a collection. You can only use this type of insert iterator with collection types that allow efficient insert operations to the beginning. This means that you can’t use a front inserter with a vector because vectors use arrays and inserting items in an array is a Big-O of N operation. This is not efficient so it’s not allowed.
◦ General inserters insert new items right before the item that was used to construct the general inserter adapter. The general inserters do this by calling a method on a collection called insert. Now here’s an interesting aspect to this. General inserters are the only type of insert adapter that you can use for associative and unordered containers. But these types of containers are not what you might expect to have an insert method, right? I mean, for a set or map, insert doesn’t make sense because they use binary trees where the order depends on the value and not on where you want something to be inserted. And for unordered sets and unordered maps, they use a hash table where there’s no concept of order at all. Why would these containers provide an insert method? They actually use it as a hint for where to start looking and are otherwise free to completely ignore where you want something inserted.
Insert iterators provide no means for you to advance them. Trying to advance an insert iterator adapter will have no effect. This makes sense if you think about it. Take the back inserter for example. It’s defined to always insert at the end of a collection. Advancing past the end should not cause it to start inserting somewhere else. So it just ignore any attempt to advance the iterator and just keep on inserting a new item at the end of a collection anytime you write a value to the iterator.
The last type of iterator adapter I’ll explain are the stream iterator adapters. A real life stream with water flowing over rocks is actually a very good example to understand streams. That might actually be where the name came from. Think of the water flowing as if it was information flowing by. If you catch some of the water, look at it and let it back, it’s gone. You can also pour more water into a stream and it just joins up with the other water and moves on as well. How long will the stream of water last? Some streams can go on for a long time. Others might dry up a few hours after the rain stops.
For programming, a stream is a flow of information. If you open a file and start reading information out of the file, this is a stream. You can also open a file to write information. This is also a stream. Usually streams are classified as either input or output but they can be both too sometimes. If you need to open a file to read some information and write some other information, then this is an input and output stream. Streams can also be more than just files. Think of your keyboard. A keyboard is a source of information that comes from you as you press the keys. This information continues as long as you keep pressing keys. This is an input stream because the information is flowing into the computer.
For modern computers, we don’t normally think of the display as a stream anymore. It’s all graphical now. But older computers had displays that could only display text and this text was organized in lines and columns. A program could send text to the display and once it was sent and appeared on the display, then it was done. This is an output stream.
You can adapt streams in the form of iterators that allow you to advance the iterator when reading, that’s an input stream iterator, or advance the iterator when writing, that’s an output stream iterator.
With stream iterator adapters, you can use them to read or write values to a stream instead of a collection that exists only in the computer’s memory. This could be a file on disk, a keyboard, a text display, or some other stream. Maybe your computer has a source of true random numbers that just keep flowing. You could read these numbers with a stream iterator adapter.