In this video, I'd like to go over the basics of iterators
in the standard template library.
Iterators allow us to think of a container as a sequence of elements,
it doesn't matter what the container is. For example,
we might have a vector or a set or a map,
they're all very different containers.
But iterators allow us to process sequence of elements from these containers
without worrying or even needing to know about how the container is implemented behind the scenes.
That gives us so much power.
Iterators are implemented as template classes,
so we create iterator objects and use them to iterate through our containers.
The syntax we use with iterators will remind you of pointers.
We can use the dereference operator, the increment and decrement operators and so forth.
This was done intentionally.
C++ programmers are comfortable with the pointer syntax,
and it's very easy to learn how to use iterators
without having to learn some other arbitrary syntax.
Most of the stl containers can be traversed with iterators.
There are a few exceptions, such as a stack and a queue, and we'll see them later.
So what do iterators look like and how do we use them.
An iterator must be declared based on the type of container type
that it will iterate over.
So if I have a vector of integers, then my iterator must know that when I create it.
The syntax is very straightforward. We provide the container type,
the scope resolution operator, the iterator type,
and then the name of our iterator object.
That sounds complicated, I know, but it's not.
Let's see some examples and you'll see.
In the following declarations, I'm declaring four iterator objects.
The first, it1, is an iterator that will iterate over
a vector of integers.
It can only be used on vectors of integers.
The second, it2, can iterate over a list of strings.
A list is a container in the stl, which we'll see later in this section.
The third, it3, can iterate over a map of string stream pairs.Maps are like dictionaries,
we'll also see them in this section.
Finally, it4 is an iterator that can iterate over sets of characters.
As you can see, we must be very specific when declaring iterators.
Now let's look at an example using a vector, so we can see how to initialize iterators.
In this example, we've created a vector of integers named vec
and initialized it to 1 2 and 3.
Remember, a vector is a container in the stl
that stores elements in contiguous memory
and can resize itself to accommodate elements dynamically.
How this is implemented in the stl doesn't really matter to us.
What we do need to know is that a container has a beginning and an end.
The stl defines the beginning as the first element in the container,
in this case, the 1.
And the stl defines the end as 1 after the last element in the container.
This is very important, and it's consistent throughout the stl.
The end is not the last element, it's 1 after the last element.
Almost all of the stl containers have begin and end methods.
When we call these methods, they return an iterator object
that's pointing to either the first element in the container
or one past the last element in the container.
In this, case vec.begin
we'll return an iterator that's pointing to the element one,
and vec.end will return an iterator
pointing one past the element 3 in this case.
When we write code we, use vect.end as the sentinel
so that we know when we're at the end of the list.
Now suppose we have a set.
A set may or may not be implemented in contiguous memory, it doesn't matter, and that's the point.
We don't need to know.
If we want to iterate over a set of characters name suits, in this case.
We know that suits.begin will return an iterator to the first element in the set.
And suits.n will return an iterator 1 past the last element in the set.
We can use this information to initialize our iterators.
For example, we can declare an iterator named it
that will iterate over a vector of integers
and then initialize it to point to the first element in that vector.
We do that by calling vec.begin.
In this case, it will point to the element 1 in the vector.
If the vector had been empty, then it would point to vec.end.
Now the syntax can get long when we do this.
So we can use auto to let the compiler deduce the type of the iterator.
This is really handy, and it's used very often.
So the compiler deduces the type of it as an iterator
to a vector of integers based on the result returned by vec.begin.
This is much more readable and much more writable and easier to debug.
There are a bunch of operations that we can use on iterators.
Most will feel very similar to using pointers.
In this table, we have a few of the most commonly used operations for iterators.
The first column is the operation,
the second column explains what it does,
and the third column shows what type of iterator supports the operation.
In this table, we'll assume that it is an iterator and i is an integer.
Notice the first two iterator operations,
pre-increment and post-increment.
When we increment an iterator,
we're asking it to point to the next element in the container.
How's that determined, it's up to the container we're using.
The third operation is assigning one iterator to another.
Of course, the types of the iterators must be the same.
These three operations are supported by all iterators.
The fourth operator is the dereference operator,
just like when we dereference a pointer.
When we dereference an iterator,
we get the element in the container that it's pointing to.
And we can also use the arrow operator
when we're pointing to objects and we want to access their attributes and methods.
Both input and output iterators support this,
and we're able to read and write elements to containers.
For the rest of the operators, you can pause the video and look at them on your own.
Notice that we have ways to compare iterators,
and we can also decrement operators.
Some containers support bi-directional iterators, which means that we can move forward and backwards
through the container, others support random access iterators,
like arrays and vectors.
So how can we use these operators to work with iterators.
Here's a really simple but common example.
First, we declare vec as a vector of integers
and we'll initialize it to 1 2 and 3.
What we want to do is use an iterator to iterate over the vector
and display the contents of the vector.
So we declare our iterator it
as an iterator over a vector of integers
and we initialize it to the first element of vec by calling vec.begin.
Now we simply iterate through the vector, while it is not equal to vec.end.
And at each iteration, we display the element
the iterator is pointing to by dereferencing the iterator,
then we move to the next element by incrementing the iterator. That's it,
simple as pi.
I know what you're thinking, why not just use a range-based for loop
or a counter controlled for loop?
We absolutely could and we often do.
We'll see in a bit that a range based for loop is converted
to an iterator-based loop behind the scenes by the compiler.
But the real answer is that in the case of a vector, we could do it a lot of different ways.
But other containers don't allow us to randomly access elements like a vector does.
So for those containers, iterators are necessary.
We can achieve the same result with a for loop instead of a while loop.
Here we declare it using auto.
This makes the code much more readable. We start at vec.begin.
We loop while it is not equal to vect.end,
and we display the element by dereferencing the iterator.
Then we increment the iterator and do it all over again.
This is exactly how range-based for loops work.
In fact, sometimes we might mess up the code in a range based for loop
that iterates over a container and the compiler gives us an error message
saying that something is wrong with the iterator.
This error is really confusing to beginning students but no more.
If you ever get an error like that, you'll know exactly what's going on.
Now let's iterate over a set of characters using an iterator.
Here we define suits to be a set of characters,
and we initialize it to the character C H S D.
We can also declare our iterator it as auto and let the compiler deduce its type
based on the result of suit stop begin.
Then we loop while it is not equal to suits.end and display the character.
Increment the iterator, and loop again. The pattern should look familiar.
Finally, let's wrap up these slides by looking at a reverse iterator.
A reverse iterator is exactly what you would expect, it works in reverse.
So the last element is the first and the first is the last.
And when we increment the iterator, we move backwards through the container in reverse.
When we decrement the iterator, we move forward.
Here's the same example with vec as a vector of the 3 integers 1 2 and 3.
We then declare it as a reverse iterator
and initialize it to vec.begin.
Since it's a reverse iterator, it will be pointing
to the last element in the list, not the first.
Now we can write code as we did before,
and this will display the vector elements in reverse, 3 2 1 in this case.
In addition to the reverse iterator, there's a few variants that are const iterators,
that are read-only iterators. Let's take a look at those really quickly.
So in this slide, we'll wrap up the iterators by learning about the const iterators.
These are methods in the appropriate container class that return specific
types of iterators.
You can see that we used begin and end for regular iterators.
We can also use cbegin and cend for const iterators.
Rbegan an rend for reverse iterators, as we saw in the previous slide
and crbegan and crend for const reverse iterators.
Okay. So that's a basic introduction to the stl iterators.
There's much, much more to learn,
but this foundation will let you use iterators with containers and algorithms
and solve a bunch of problems.
So let's head over to the IDE, and I'll go over some of these simple iterators in live code.