WEBVTT 00:00.180 --> 00:03.540 Hello again! In this video, we are going to look at write-only algorithms. 00:04.170 --> 00:08.700 These are algorithms which can write to an iterator range, but not read any elements. 00:09.240 --> 00:14.250 And these are intended for populating sequential containers, such as vector and string. 00:15.270 --> 00:17.940 The first algorithm we are going to look at is fill(). 00:18.600 --> 00:24.990 This takes an iterator range, and it assigns the third argument to every iterator in this range. 00:25.590 --> 00:31.560 So this call, we have a vector with 10 elements, and it is going to set every element to have the 00:31.560 --> 00:32.400 value 42. 00:34.200 --> 00:39.180 We could also write that as a loop in which we just assign every element to be 42. 00:41.320 --> 00:42.520 So let's try this out. 00:42.790 --> 00:45.280 So we have a vector with 10 elements. 00:45.940 --> 00:52.900 We have our call to fill(), which sets every element in the vector to 42 and then we have a handwritten 00:52.900 --> 00:54.250 loop, which does the same thing. 00:57.170 --> 01:01.610 And in both cases, we get a vector with 10 elements, which all have the value 42. 01:02.660 --> 01:09.080 There's another algorithm called fill_n(). This takes a single iterator, and a number, 01:09.860 --> 01:14.370 and this number represents the number of elements to assign to. 01:15.470 --> 01:17.510 So in this case, we have begin() and 5. 01:17.720 --> 01:21.500 So this will assign the first 5 elements in the vector. 01:22.370 --> 01:27.590 So these will all have the value 42. And this will return an iterator to the next element. 01:27.830 --> 01:31.940 So after it does 5, it will return an iterator to the sixth element. 01:33.230 --> 01:36.550 And then we could use that iterator as the start of another range. 01:37.250 --> 01:42.860 If we have the sixth element and end(), then this will assign all the remaining elements in the vector. 01:44.600 --> 01:50.690 So in this code, we said the first 5 elements to be 42 and we set the remainder to be 99. 01:52.160 --> 01:55.880 So here we have our call to fill_n() and fill() again. 01:56.840 --> 02:03.710 If we were using a handwritten loop, we would iterate over the first 5 elements and set them to 42. 02:04.730 --> 02:06.620 When this completes, "i" will be 5. 02:07.490 --> 02:13.720 Then we continue from that value of "i" until we reach the last element. And we set these elements to 02:13.730 --> 02:14.330 99. 02:18.670 --> 02:23.890 And there we are, we have the first five elements ar 42, and the remainder are 99. 02:25.450 --> 02:30.040 This is potentially dangerous because fill_n() assumes that you know what you are doing. 02:30.160 --> 02:32.920 It will assume that this vector has at least 5 elements. 02:33.820 --> 02:38.590 It does not check the size of the vector or whether it has reached the last element. 02:43.450 --> 02:46.270 To demonstrate the problem, let's use an empty vector. 02:47.530 --> 02:48.940 So what happens here? 02:51.930 --> 02:53.460 And we get a crash. 02:54.300 --> 02:59.400 So what happened is that the fill_n() algorithm tried to assign the first element. There are 02:59.400 --> 03:00.600 no elements in this vector. 03:00.960 --> 03:05.940 So fill_n() was writing to memory that does not belong to the vector and we get an error. 03:06.270 --> 03:07.860 There are various ways to attack this. 03:08.130 --> 03:12.120 The obvious one is to make sure that you only use a vector which has the right number of elements. 03:12.870 --> 03:13.800 And you can do that. 03:14.160 --> 03:15.600 Sometimes you may not have control. 03:15.750 --> 03:20.160 You may be given a vector by someone else, and you have no idea how many elements it has. 03:21.240 --> 03:23.190 So obviously you need to check. 03:23.670 --> 03:26.260 And one thing you can do is to resize the vector. 03:27.330 --> 03:28.830 So if the vector is too small, 03:28.830 --> 03:34.980 then you can create a new vector, which has the right number of elements. And then you can call the 03:34.980 --> 03:36.000 swap() member function. 03:37.170 --> 03:41.060 So we saw this with the string class. When we call swap, 03:41.100 --> 03:46.770 this will exchange the memory buffers of two strings, so the data moves from one string to the other. 03:47.430 --> 03:49.140 And this will also work with vectors. 03:49.560 --> 03:57.480 So this "new_vec", after the swap, will now have the memory buffer from "vec", of unknown size, and "vec" will now 03:57.480 --> 04:01.200 have the memory buffer of the right size that came from "new_vec". 04:01.890 --> 04:07.500 This "new_vec" is a local variable, so when it leaves the scope, it will be destroyed, and its memory 04:07.500 --> 04:08.910 buffer will be released. 04:09.120 --> 04:13.350 This is quite a useful trick to know, if you ever have a situation where you want to reduce the size 04:13.350 --> 04:14.070 of a vector. 04:15.330 --> 04:21.000 Vectors will always expand to add more elements, but they do not usually shrink when you remove elements. 04:21.810 --> 04:27.030 The reason for that is that memory operations are slow. And quite often, if you remove elements from a vector, 04:27.200 --> 04:29.160 you may want to add them back again later on. 04:30.300 --> 04:35.430 But there are some situations. If you have a vector with 1 million elements and you delete almost all of them 04:35.430 --> 04:41.130 and you only want to use 50 from then onwards, then you have all this memory that is being taken up, 04:41.130 --> 04:43.950 but not being used for any useful purpose. 04:44.460 --> 04:49.080 There are member functions which are supposed to shrink the size of a vector, so it just uses enough memory 04:49.080 --> 04:49.950 to store its data. 04:50.220 --> 04:53.040 But those member functions are not actually required to do anything! 04:53.610 --> 04:55.740 This code will always reduce the vector. 04:56.280 --> 05:00.660 Obviously, if you have important data, then you need to refine this a bit to make sure the data gets 05:00.660 --> 05:01.050 copied. 05:03.330 --> 05:08.760 So now we've made sure the vector has enough storage, we can call fill_n() and it will all work. 05:09.720 --> 05:10.680 So there we go. 05:13.450 --> 05:18.580 Another option is to use an insert iterator. So instead of having a positional iterator 05:18.580 --> 05:24.670 as the first arguments, we have an insert operator. So if we put back_inserter() for a vector, this 05:24.670 --> 05:29.380 will call push_back() every time that the fill_n() algorithm assigns to an element. 05:30.760 --> 05:34.390 So this is equivalent to a loop which calls push back with the argument, 05:34.390 --> 05:35.080 42. 05:38.020 --> 05:38.950 And again, that works. 05:43.240 --> 05:47.050 The other algorithm we're going to look at, or the other family, is generate(). 05:47.500 --> 05:54.340 So instead of having a fixed value, we use the return value from a function call. The function that 05:54.340 --> 05:55.870 we use takes no arguments. 05:56.410 --> 06:02.830 It returns a value of the element's type. And the idea is that this will return a different value each 06:02.830 --> 06:03.670 time it is called. 06:04.090 --> 06:05.590 Otherwise, you can just use fill(). 06:07.790 --> 06:09.800 You can use any callable object. 06:10.010 --> 06:12.050 And one possibility is a functor. 06:12.740 --> 06:15.770 So we have a private data member, to give it state. 06:16.040 --> 06:18.080 So initially this member "n" has the value 0. 06:18.590 --> 06:23.360 And then each time the functor is called, we increment this value "n" and return 06:23.360 --> 06:24.050 its square. 06:24.770 --> 06:30.380 So the first time, "n" will be incremented to 1 and we return the square of 1. The next time "n" is 2 06:30.500 --> 06:33.050 and we return 2 squared, 3, 3 squared, and so on. 06:34.670 --> 06:35.710 And then to call generate(), 06:35.720 --> 06:39.320 We pass the iterator range and an object of this functor class. 06:40.250 --> 06:46.520 And on every iteration through the vector, this generate() function will call the function call operator 06:46.520 --> 06:47.900 of this object. 06:52.140 --> 06:54.480 So here is that functor class. 06:55.980 --> 07:03.060 We have our vector and the generate() call. The equivalent is to write a loop which calls the 07:03.060 --> 07:08.100 funtor on every iteration, and assigns it to the current element in the iteration. 07:11.170 --> 07:13.660 And there we are, we have the first 10 square numbers. 07:14.080 --> 07:19.840 So each time the generate() function calls square(), we get the square of the next number. 07:22.430 --> 07:24.920 And there is also an _n version of generate(). 07:25.670 --> 07:28.010 Just like fill() has an _n version. 07:28.730 --> 07:34.190 So this will specify the number of elements that we want to assign, starting with the first argument. 07:35.810 --> 07:39.880 And again, this should be used with a back inserter, unless you know that for sure that the vector 07:39.920 --> 07:40.520 is big enough. 07:42.020 --> 07:43.130 So here is our code. 07:43.550 --> 07:44.480 Everything is the same. 07:44.690 --> 07:47.870 We are just using generate_n() with a back inserter this time. 07:52.240 --> 07:54.430 OK, so that it is for this video. 07:54.880 --> 07:55.780 I will see you next time. 07:56.020 --> 07:57.820 Until then, keep coding!