Hello again! In this video, we're going to look at iterator arithmetic and iterator ranges.
We have actually already done this, without really making a big fuss about it.
We've incremented iterators. And we can also do arithmetic operations similar to the ones we can
do on pointers.
(Where am I? :) so we can add to an iterator, and that will move it towards the back of the container.
So if we start with the return value from begin(), an iterator to the first element. And we add one to
it, we get the second element.
If we add four, we get the Fifth Element. And so on.
And then subtracting will go in the opposite way. It will move towards the front of the container.
So if we have the return value from end() and we subtract one, that will give us the last element.
So you are actually allowed to do this.
You cannot
dereference the iterator [safely], but you can do arithmetic with it.
So that will give - that will go from the last plus one iterator, it will move towards the last iterator in
the container. And also, end() minus begin() will always give the number of elements in the container.
So we can combine all this and we can calculate the position of the iterator to the middle of the container.
So we get the number of elements which is end() minus begin().
THen we halve that.
And then we add that to the iterator to the first element.
So if we have, say, 10 elements, then half that is five. Then we add to five to the first element, and
that will give us the sixth element, which is in the middle of 10.
And similarly for 11, we get the sixth element.
I suppose it depends how you define the middle, really.
If it's an even number, it should be the "five and halfth" element, but there's no such thing.
So let's try that out.
We have our string,
"hello."
(Original?)
(Yes?)
And we are going to print out the string.
We are going to printout
the number of elements, which end() minus begin().
We are going to get an iterator to the second element and print it out.
Then we are going to get this iterator to the last element. And print it out the last element.
And then we are going to get the one in the middle.
So, here we go!
So the string is "hello". It has five elements. Correct.
The second element is 'e', yep. Last element is 'o'. middle element is 'l'.
OK, maybe it is not the best example. But it is at least in the middle of the string. So it is presumably
that one.
Just in case you don't believe me.
Let's try something where it is a bit more obvious.
So the middle element is three.
Okay!
Having bare numbers exposed in code is generally not a good idea, as it is not always clear what they
mean. And they might get caught in a search and replace by mistake.
So there are actually functions you can use, which perform the same thing.
So if you call next() and then pass an iterator as the argument, it will add one to that iterator and
return the result.
So instead of saying begin() + 1, we can say next(begin()).
And there's also a prev() which goes in the other direction, so we can pass an iterator to prev(),
and this will return the iterator before that element.
So that's another way of writing end() minus one.
For subtraction, instead of having an explicit subtraction, we can write distance.
So distance() between the first iterator and the last plus one will give us the number of elements.
Also, there is an advance we can use to move an iterator by a number of positions. So we could take the
begin iterator and then add the number of elements, which we had before.
So advance(mid) and this distance computation. That will also give us the middle element iterator.
So let's try that again with our - actually, let's...
(Let's do that again)
Doing the same thing again, except we are using these functions, so instead of doing begin() minus end(),
we are doing distance. Instead of begin plus one, we're calling next.
In fact, we are going to be a bit extra cautious here.
We're going to use "belt and braces" as the expression is.
(Make sure our trousers don't fall down!)
In this example, it is obvious that second is going to be a valid iterator.
But in a lot of instances it will not be.
And in general, when working with iterators and manipulating them, it is always a good idea to check
that you have actually got a valid integer.
Otherwise, your program might blow up.
So to make sure it is valid, we just compare it to calling end() and then we can dereference it and we
know that is going to be safe.
And then we do prev() instead of doing end() minus one.
And then we do our calculation to get in the middl. So we do the distance(), to get the number of elements,
and we halve that. And then we add it to the first element.
The iterator to the first element.
And then again, we check it. And we can also work out the position of this element.
That will be the number of elements between the first iterator and the middle.
So again, we can use distance.
So we can subtract the number of elements.
So our string is one two three four five.
We have five elements. The second element is two.
That is from calling next(). The last element is five.
From calling prev or previous or whatever you want to call it.
The middle element is three.
And this calculation gave the index is two.
So there we are, zero, one, two.
So the index of three is two.
If you read up about iterators, you will often see the term mentioned, which is a half open range.
So let's find out what that is about.
Let's start off with a simpler example.
So imagine we are just doing traditional C++ or C code where it's iterating over, maybe, the elements
of an array, and we are using a loop to keep count of the elements.
So we have an array with 10 elements.
So we're going to iterate, from the index is zero, to the index being less than 10.
So in the body of the loop, i is only allowed to have a limited range of values. It can be zero, one, two,
up to nine, but it can't be ten. If i has any other value than zero to nine, than there is an error.
And in fact, some people will put asserts in this kind of code, just to make sure that the index stays
within range.
So this is known as a half open range from zero to 10.
And it's written as square package zero comma 10.
And then a round bracket.
So this means that i must be greater than or equal to zero.
And i must be less than 10.
i equals 10 is not allowed.
So that's the technical definition of a half-open range.
So how does this work with iterators?
The iterators returned by begin() and end() also define a range, of iterators.
So we have the same thing. We have from the begin()
return value, up to, but not including the return value from end().
So the allowed values in the body are begin(), begin() + 1, or if you prefer next(begin()), begin() plus two up
to but not including end.
So again, this is a half open range.
"it" must be greater than or equal to begin(), and it must be less than the return value from end().
But it cannot be equal to the return value from end().
Okay.
So that's it for this video.
I'll see you next time, but meanwhile, keep coding!