WEBVTT 00:02.020 --> 00:06.990 Hello again! In this video, we're going to look at iterator arithmetic and iterator ranges. 00:08.320 --> 00:12.830 We have actually already done this, without really making a big fuss about it. 00:12.850 --> 00:19.600 We've incremented iterators. And we can also do arithmetic operations similar to the ones we can 00:19.600 --> 00:20.620 do on pointers. 00:26.000 --> 00:31.580 (Where am I? :) so we can add to an iterator, and that will move it towards the back of the container. 00:32.090 --> 00:38.450 So if we start with the return value from begin(), an iterator to the first element. And we add one to 00:38.460 --> 00:39.830 it, we get the second element. 00:40.610 --> 00:44.330 If we add four, we get the Fifth Element. And so on. 00:47.040 --> 00:51.660 And then subtracting will go in the opposite way. It will move towards the front of the container. 00:52.410 --> 00:58.080 So if we have the return value from end() and we subtract one, that will give us the last element. 00:58.650 --> 01:00.360 So you are actually allowed to do this. 01:00.690 --> 01:01.220 You cannot 01:01.290 --> 01:04.260 dereference the iterator [safely], but you can do arithmetic with it. 01:06.430 --> 01:12.610 So that will give - that will go from the last plus one iterator, it will move towards the last iterator in 01:12.610 --> 01:18.910 the container. And also, end() minus begin() will always give the number of elements in the container. 01:20.440 --> 01:26.590 So we can combine all this and we can calculate the position of the iterator to the middle of the container. 01:27.160 --> 01:30.100 So we get the number of elements which is end() minus begin(). 01:32.790 --> 01:33.780 THen we halve that. 01:35.890 --> 01:39.340 And then we add that to the iterator to the first element. 01:39.910 --> 01:46.840 So if we have, say, 10 elements, then half that is five. Then we add to five to the first element, and 01:46.840 --> 01:49.570 that will give us the sixth element, which is in the middle of 10. 01:50.770 --> 01:53.530 And similarly for 11, we get the sixth element. 01:53.860 --> 01:55.390 I suppose it depends how you define the middle, really. 01:56.470 --> 02:00.430 If it's an even number, it should be the "five and halfth" element, but there's no such thing. 02:01.330 --> 02:02.590 So let's try that out. 02:02.590 --> 02:03.670 We have our string, 02:03.850 --> 02:04.290 "hello." 02:05.470 --> 02:05.980 (Original?) 02:06.010 --> 02:06.360 (Yes?) 02:07.450 --> 02:08.650 And we are going to print out the string. 02:08.650 --> 02:09.670 We are going to printout 02:09.670 --> 02:12.460 the number of elements, which end() minus begin(). 02:13.370 --> 02:18.120 We are going to get an iterator to the second element and print it out. 02:18.580 --> 02:24.610 Then we are going to get this iterator to the last element. And print it out the last element. 02:25.300 --> 02:26.830 And then we are going to get the one in the middle. 02:27.250 --> 02:28.330 So, here we go! 02:30.520 --> 02:34.150 So the string is "hello". It has five elements. Correct. 02:34.720 --> 02:40.390 The second element is 'e', yep. Last element is 'o'. middle element is 'l'. 02:41.140 --> 02:46.390 OK, maybe it is not the best example. But it is at least in the middle of the string. So it is presumably 02:46.480 --> 02:46.900 that one. 02:51.960 --> 02:53.170 Just in case you don't believe me. 02:53.960 --> 02:55.590 Let's try something where it is a bit more obvious. 02:55.600 --> 02:57.430 So the middle element is three. 02:58.210 --> 02:58.600 Okay! 03:05.130 --> 03:09.930 Having bare numbers exposed in code is generally not a good idea, as it is not always clear what they 03:09.930 --> 03:13.470 mean. And they might get caught in a search and replace by mistake. 03:14.580 --> 03:18.240 So there are actually functions you can use, which perform the same thing. 03:18.960 --> 03:25.510 So if you call next() and then pass an iterator as the argument, it will add one to that iterator and 03:25.510 --> 03:26.310 return the result. 03:26.910 --> 03:30.870 So instead of saying begin() + 1, we can say next(begin()). 03:32.040 --> 03:39.090 And there's also a prev() which goes in the other direction, so we can pass an iterator to prev(), 03:39.090 --> 03:41.910 and this will return the iterator before that element. 03:43.140 --> 03:45.510 So that's another way of writing end() minus one. 03:49.810 --> 03:54.520 For subtraction, instead of having an explicit subtraction, we can write distance. 03:55.470 --> 04:01.590 So distance() between the first iterator and the last plus one will give us the number of elements. 04:03.300 --> 04:11.400 Also, there is an advance we can use to move an iterator by a number of positions. So we could take the 04:11.400 --> 04:17.000 begin iterator and then add the number of elements, which we had before. 04:17.940 --> 04:23.850 So advance(mid) and this distance computation. That will also give us the middle element iterator. 04:29.140 --> 04:31.450 So let's try that again with our - actually, let's... 04:35.530 --> 04:36.280 (Let's do that again) 04:36.760 --> 04:40.930 Doing the same thing again, except we are using these functions, so instead of doing begin() minus end(), 04:40.930 --> 04:44.830 we are doing distance. Instead of begin plus one, we're calling next. 04:46.580 --> 04:49.120 In fact, we are going to be a bit extra cautious here. 04:49.130 --> 04:52.190 We're going to use "belt and braces" as the expression is. 04:53.660 --> 04:55.250 (Make sure our trousers don't fall down!) 04:56.810 --> 05:00.920 In this example, it is obvious that second is going to be a valid iterator. 05:01.400 --> 05:04.490 But in a lot of instances it will not be. 05:04.760 --> 05:09.290 And in general, when working with iterators and manipulating them, it is always a good idea to check 05:09.290 --> 05:10.940 that you have actually got a valid integer. 05:11.570 --> 05:13.790 Otherwise, your program might blow up. 05:15.110 --> 05:21.800 So to make sure it is valid, we just compare it to calling end() and then we can dereference it and we 05:21.800 --> 05:22.940 know that is going to be safe. 05:24.150 --> 05:26.640 And then we do prev() instead of doing end() minus one. 05:29.850 --> 05:36.840 And then we do our calculation to get in the middl. So we do the distance(), to get the number of elements, 05:36.840 --> 05:42.390 and we halve that. And then we add it to the first element. 05:42.600 --> 05:44.070 The iterator to the first element. 05:45.030 --> 05:49.920 And then again, we check it. And we can also work out the position of this element. 05:51.800 --> 05:55.590 That will be the number of elements between the first iterator and the middle. 05:55.650 --> 05:57.140 So again, we can use distance. 05:58.170 --> 06:00.450 So we can subtract the number of elements. 06:06.830 --> 06:08.640 So our string is one two three four five. 06:08.660 --> 06:11.510 We have five elements. The second element is two. 06:11.540 --> 06:14.720 That is from calling next(). The last element is five. 06:14.780 --> 06:19.130 From calling prev or previous or whatever you want to call it. 06:19.970 --> 06:21.710 The middle element is three. 06:22.580 --> 06:25.760 And this calculation gave the index is two. 06:30.780 --> 06:32.850 So there we are, zero, one, two. 06:32.880 --> 06:34.710 So the index of three is two. 06:37.300 --> 06:42.160 If you read up about iterators, you will often see the term mentioned, which is a half open range. 06:42.790 --> 06:44.350 So let's find out what that is about. 06:45.280 --> 06:46.930 Let's start off with a simpler example. 06:47.110 --> 06:53.680 So imagine we are just doing traditional C++ or C code where it's iterating over, maybe, the elements 06:53.680 --> 06:57.490 of an array, and we are using a loop to keep count of the elements. 06:57.910 --> 06:59.850 So we have an array with 10 elements. 06:59.860 --> 07:05.920 So we're going to iterate, from the index is zero, to the index being less than 10. 07:07.570 --> 07:14.250 So in the body of the loop, i is only allowed to have a limited range of values. It can be zero, one, two, 07:14.890 --> 07:21.850 up to nine, but it can't be ten. If i has any other value than zero to nine, than there is an error. 07:22.060 --> 07:27.250 And in fact, some people will put asserts in this kind of code, just to make sure that the index stays 07:27.250 --> 07:27.910 within range. 07:30.140 --> 07:33.500 So this is known as a half open range from zero to 10. 07:34.130 --> 07:38.350 And it's written as square package zero comma 10. 07:38.830 --> 07:40.340 And then a round bracket. 07:41.090 --> 07:44.360 So this means that i must be greater than or equal to zero. 07:45.110 --> 07:46.700 And i must be less than 10. 07:48.390 --> 07:50.570 i equals 10 is not allowed. 07:52.880 --> 07:55.790 So that's the technical definition of a half-open range. 07:56.270 --> 07:57.980 So how does this work with iterators? 08:00.150 --> 08:04.740 The iterators returned by begin() and end() also define a range, of iterators. 08:05.250 --> 08:08.910 So we have the same thing. We have from the begin() 08:09.260 --> 08:12.660 return value, up to, but not including the return value from end(). 08:13.560 --> 08:21.900 So the allowed values in the body are begin(), begin() + 1, or if you prefer next(begin()), begin() plus two up 08:21.900 --> 08:23.400 to but not including end. 08:24.360 --> 08:26.370 So again, this is a half open range. 08:27.300 --> 08:33.600 "it" must be greater than or equal to begin(), and it must be less than the return value from end(). 08:34.110 --> 08:36.330 But it cannot be equal to the return value from end(). 08:38.760 --> 08:39.090 Okay. 08:39.300 --> 08:40.830 So that's it for this video. 08:41.280 --> 08:44.370 I'll see you next time, but meanwhile, keep coding!