Hello again! In this video, we are going to look at write-only algorithms.
These are algorithms which can write to an iterator range, but not read any elements.
And these are intended for populating sequential containers, such as vector and string.
The first algorithm we are going to look at is fill().
This takes an iterator range, and it assigns the third argument to every iterator in this range.
So this call, we have a vector with 10 elements, and it is going to set every element to have the
value 42.
We could also write that as a loop in which we just assign every element to be 42.
So let's try this out.
So we have a vector with 10 elements.
We have our call to fill(), which sets every element in the vector to 42 and then we have a handwritten
loop, which does the same thing.
And in both cases, we get a vector with 10 elements, which all have the value 42.
There's another algorithm called fill_n(). This takes a single iterator, and a number,
and this number represents the number of elements to assign to.
So in this case, we have begin() and 5.
So this will assign the first 5 elements in the vector.
So these will all have the value 42. And this will return an iterator to the next element.
So after it does 5, it will return an iterator to the sixth element.
And then we could use that iterator as the start of another range.
If we have the sixth element and end(), then this will assign all the remaining elements in the vector.
So in this code, we said the first 5 elements to be 42 and we set the remainder to be 99.
So here we have our call to fill_n() and fill() again.
If we were using a handwritten loop, we would iterate over the first 5 elements and set them to 42.
When this completes, "i" will be 5.
Then we continue from that value of "i" until we reach the last element. And we set these elements to
99.
And there we are, we have the first five elements ar 42, and the remainder are 99.
This is potentially dangerous because fill_n() assumes that you know what you are doing.
It will assume that this vector has at least 5 elements.
It does not check the size of the vector or whether it has reached the last element.
To demonstrate the problem, let's use an empty vector.
So what happens here?
And we get a crash.
So what happened is that the fill_n() algorithm tried to assign the first element. There are
no elements in this vector.
So fill_n() was writing to memory that does not belong to the vector and we get an error.
There are various ways to attack this.
The obvious one is to make sure that you only use a vector which has the right number of elements.
And you can do that.
Sometimes you may not have control.
You may be given a vector by someone else, and you have no idea how many elements it has.
So obviously you need to check.
And one thing you can do is to resize the vector.
So if the vector is too small,
then you can create a new vector, which has the right number of elements. And then you can call the
swap() member function.
So we saw this with the string class. When we call swap,
this will exchange the memory buffers of two strings, so the data moves from one string to the other.
And this will also work with vectors.
So this "new_vec", after the swap, will now have the memory buffer from "vec", of unknown size, and "vec" will now
have the memory buffer of the right size that came from "new_vec".
This "new_vec" is a local variable, so when it leaves the scope, it will be destroyed, and its memory
buffer will be released.
This is quite a useful trick to know, if you ever have a situation where you want to reduce the size
of a vector.
Vectors will always expand to add more elements, but they do not usually shrink when you remove elements.
The reason for that is that memory operations are slow. And quite often, if you remove elements from a vector,
you may want to add them back again later on.
But there are some situations. If you have a vector with 1 million elements and you delete almost all of them
and you only want to use 50 from then onwards, then you have all this memory that is being taken up,
but not being used for any useful purpose.
There are member functions which are supposed to shrink the size of a vector, so it just uses enough memory
to store its data.
But those member functions are not actually required to do anything!
This code will always reduce the vector.
Obviously, if you have important data, then you need to refine this a bit to make sure the data gets
copied.
So now we've made sure the vector has enough storage, we can call fill_n() and it will all work.
So there we go.
Another option is to use an insert iterator. So instead of having a positional iterator
as the first arguments, we have an insert operator. So if we put back_inserter() for a vector, this
will call push_back() every time that the fill_n() algorithm assigns to an element.
So this is equivalent to a loop which calls push back with the argument,
42.
And again, that works.
The other algorithm we're going to look at, or the other family, is generate().
So instead of having a fixed value, we use the return value from a function call. The function that
we use takes no arguments.
It returns a value of the element's type. And the idea is that this will return a different value each
time it is called.
Otherwise, you can just use fill().
You can use any callable object.
And one possibility is a functor.
So we have a private data member, to give it state.
So initially this member "n" has the value 0.
And then each time the functor is called, we increment this value "n" and return
its square.
So the first time, "n" will be incremented to 1 and we return the square of 1. The next time "n" is 2
and we return 2 squared, 3, 3 squared, and so on.
And then to call generate(),
We pass the iterator range and an object of this functor class.
And on every iteration through the vector, this generate() function will call the function call operator
of this object.
So here is that functor class.
We have our vector and the generate() call. The equivalent is to write a loop which calls the
funtor on every iteration, and assigns it to the current element in the iteration.
And there we are, we have the first 10 square numbers.
So each time the generate() function calls square(), we get the square of the next number.
And there is also an _n version of generate().
Just like fill() has an _n version.
So this will specify the number of elements that we want to assign, starting with the first argument.
And again, this should be used with a back inserter, unless you know that for sure that the vector
is big enough.
So here is our code.
Everything is the same.
We are just using generate_n() with a back inserter this time.
OK, so that it is for this video.
I will see you next time.
Until then, keep coding!