Hello again! In this video, we are going to look at list operations. With C++ lists, we can do most of
the operations that we can do on sequential containers.
We can use push_back() and push_front() for adding elements to the container.
We can use iterators to loop over some of the elements, or all the elements, in a list.
One important difference is that lists do not support random access.
With a vector or string,
we can jump straight to the sixth element, for example. With a list we have to start at the beginning
and iterate until we get there.
So this means that the functions in the header, which require random access, are not supported.
For example, if we try to call sort() with a list or a forward_list as argument, then that will not
compile.
Instead, this each member function we have to use, but that will work fine. And it is specialized to
be efficient when sorting lists.
Quite often, containers have member functions which have the same functionality as algorithms.
In the case of list, these can sometimes be much more efficient than using the generic versions. For
example, with remove(). We saw with the generic version with vector.
It does not actually delete the elements from the container, it just moves them to the back
of the container, and then you have to call erase(). The member function for list will actually delete the elements
straightaway.
So no messing around, and no call to erase(). And that just involves assigning a couple of pointers.
So obviously, that is going to be much faster than calling the generic version and moving list
elements arounf.
So let's have a look at this remove() member function. In fact, first of all, let's check whether we
can use the generic sort.
And no, we get one of those horrible template errors.
So let's go back to using the member function version.
So here is our list. And then we are going to call remove(), using the member function.
So this will remove the elements with value 3.
It will delete it straightaway.
So we do not need to call erase.
So there is our list. There is the sorted version of the list, and there is the list after removing the
element with value 3.
So in general, if you're going to be moving elements around, it's much better to use the list member function
than the generic algorithm.
So that applies to things like reverse(), remove(), which we just saw, remove_if() and unique().
There are also some functions which are specific to lists.
One of these is the merge() member function.
So this takes another list as argument, and it will move all the elements from that argument list into
the list that it was called on.
So the result is going to be the combination of all the elements in the two lists, and the second
list is going to be empty.
If we sort both the lists before calling this, then the result will be sorted as well.
So here we have two lists.
We are going to sort them, using the member function, of course, and then we call merge() on "list1".
So the elements from "list2" are going to be merged into "list1".
So list1 is going to contain all the elements from both the lists, and list2
is going to be empty.
And that is what we get.
So list1 has all the elements, and list2 is empty.
Another member function is splice(). This time,
we give it an iterator as the first arguments, so that is an iterator into the first list.
And this will insert all the elements from the second list just before that iteration.
So this is for the double linked list.
We will see in a minute that the forward_list works slightly differently.
And you can also provide a single iterator from the second list, which will just move one element. Or
you can provide an iterator range, which will move some of the elements from the second list.
So we have the same two lists again.
We are going to an iterator to the second element of list1.
Then we are going to pass that as the first argument to splice(), and then this will insert all the elements from
list2 just before the second element of list1.
So we expect to see 1, 9, 3, 14, 12 and so on.
And there we are, the elements from list2 have been inserted just before the second element
of list1.
With forward_list, it works slightly differently.
You will remember that, when we inserted into a forward_list, we had to use insert_after() instead of
just insert(). And that would insert the new element after the operator, instead of before it, which
all the other containers do.
And the same thing works with splice().
splice() is really just inserting a whole list instead of a single element.
So we have splice_after() instead of splice, and instead of inserting before an iterator, we insert after
the iterator.
So let's try this. So we have a forward_list with the same elements.
And then we call splice_after(), with the an iterator to the first element of list1.
And then we get the same results again.
The elements are inserted after the first element.
Okay, so that is it for this feature.
I will see you next time.
But until then, keep coding!