In this video, we'll learn more about the stl list and
forward list containers.
These are both sequence containers and store their elements
in non-contiguous memory.
They don't provide direct access to elements via the .at method or
subscript operator, but they're very efficient when we need to
insert and delete elements in the list once an element is found.
Let's first talk about the list and then we'll talk
about the forward list after.
In order to use the list container, we have to include the list header file.
The list acts as a doubly linked list of elements, so we can go from
element to element in either direction.
Remember, lists do not support direct element access.
The list has a front and a back, and we can use all of the iterators,
but the iterators may become invalid when deleting elements.
So let's see what a doubly linked list looks like conceptually.
In this slide, we see a diagram of what a simple list looks like.
Notice that the elements are not contiguous in memory.
An element has a reference to the element after it and before it
if they exist, that's why it's referred to as a doubly linked list.
So there is some overhead involved with maintaining these links.
We declare l as a list of integers and initialize it to 1 2 and 3.
The list has a front and a back.
The front in this case is the element 1 and the back is the element 3.
With the list we can efficiently add and remove elements from the
front and the back, and we can also efficiently remove and insert
elements from anywhere in the list.
All we really have to do is remove or insert the element and then re-link the
links to the other elements around it.
Inserting and removing elements other than at the ends is very efficient,
but in order to do that, we need to have an iterator to the element that
we want to remove or insert before.
This is usually done with the find method, and it's done in linear time.
If you need a container where you will have lots of insertions and removals
from the container and you don't need direct access to the elements,
then the list is a good choice.
In the first example in this slide, I declared l as a list of integers
and initialized it to 1 2 3 and 4.
In the second example, I declared l1 as a list of integers and I'm
using an overloaded constructor to create 10 integers and
initialize them all to 100.
In the third example, I'm declaring stooges as a list of strings
and initializing them with std strings and c-style strings.
Like vectors stud arrays and decks, lists also support
assignment via initializer list.
So let's see some other common methods provided by the list.
Let's start with the size method.
This method returns the number of elements that are in the list.
And max size tells us what the maximum number of elements a list can contain.
Remember, lists do not allow direct access to elements so we can't use the
subscript operator or the .at method.
These are not available for lists.
The list also provides front and back methods that return references
to the element at the front and the element at the back of the list.
In this example, l.front refers to 1 and l.back refers to the 5.
The list allows for efficiently inserting elements at the
back and at the front.
This is done with the pushback method and the push front method.
We can also have pop back and pop front, which efficiently remove
elements from the back of the front.
In this slide, we have a list of person objects called l.
We can create a person p1 named Larry who is 18 years old, and
we can use the pushback method to insert p1 at the back of the list.
We can also remove it using pop back.
Similarly, we can add a person object to the front of the list with push
front and remove it with pop front.
The list container also supports in place front and in place back which
are efficient ways to create and initialize objects that we want to
store in the list right in place.
Inserting elements into a list works a little differently from what
we've seen with other containers.
We can insert an element before an existing element using the insert
method but the insert method expects an iterator that's referencing the
element we want to insert before.
In this example, l is a list events and I initialized l to 1 2 3 4 and 5.
Now I need an iterator to point to an element in the list.
We can do this lots of ways but let's use the find function.
We can call find with l.begin, l.n, and we're looking for the 3.
In this case, the iterator it now is referencing the element 3 in the list.
If we now call l.insert and pass in it which is the iterator and the
number we want to insert in this case 10, the 10 will be inserted
very efficiently before the 3.
The iterator will not be invalidated, it still references the 3.
Now if we call l.erase and pass in the iterator, the 3 will be
removed from the list and the iterator will become invalid now.
Lists also allow resizing.
We can resize l to a size of 2 in which case all the elements
after the second will be removed.
If we resize to a value larger than what we currently have, the list will
be expanded to that many elements and the default initializer for the
type of object the list contains will be called and those elements
stored in the newly created element.
So in this case, if we resize l to 5, we'll add 3 new elements to the list,
and they'll all be initialized to zero in this case because they're integers.
Finally, how do we traverse a list.
We can use a range based for loop or we can use iterators.
Since lists are bi-directional, we can iterate in both directions.
So in this case, we have a list l00 initialized to the ints 1 2 3
4 and 5 and we have an iterator it that will be referring to the 3.
When we de-reference i-t and display the element, we get a 003.
When we de-reference i-t and display the elem0ent, we get a 3.
Then we can increment the iterato00n the same way.
Finally, we can decrement the iterator and we get right back to the 3.
Now let's see what some of the differences are between
a list and a forward list.
The forward list was added to the stl in c++11.
In order to use the forward list, we must include the
forward list header file.
The forward list acts as a singly linked list, so the list can only
be traversed in one direction.
The forward list incurs less overhead than the list, but the downside is that
we can only use it in one direction.
But in many cases, this is exactly what we want.
Similar to the list, the forward list allows for rapid insertion and
deletion o1f elements once we have an iterator to one of the elements.
Also the forward list does not support direct element access.
As we'll see in a moment, the forward list has no
concept of back, only front.
It doesn't make much sense to get to the back of a list and
then not be able to traverse backwards, so it's not available.
Obviously, reverse iterators make no sense either so they're not supported.
So let's see what a forward list might look like.
In this slide, we see a diagram of what a simple forward list might look like.
We declare l as a forward list of integers and
initialize it to 1 2 and 3.
The forward list has only a front, no back.
The front in this case is the element 1.
With a forward list, we can officially add elements to
the front using push front.
You can see the pointers are going in only one direction.
So let's see some of the common methods used with forward lists.
Let's start with the size method.
It's not available.
There's an interesting discussion about why the decision was made
to not provide a size method.
If you're interested, let me know in the Q&A and we can talk about it.
The max size will tell us the maximum number of elements
the forward list can store.
Also notice that we have a front method but no back method.
In this case, the front method returns a reference to the element 1.
Since the forward list only uses front and not back, we have push front, pop
front and in place front available for quick insertion of elements
at the front of the forward list.
So since the forward list is a singly linked list, it makes sense
to insert elements into the forward list after an iterator reference.
So the forward list supports methods named explicitly like what they do.
In this example, l is a forward list of the integers 1 2 3 4 5.
And we have an iterator it that points to the 3.
We can now use l.insert after and pass in the iterator and
the object we want to insert.
In this case, the 10 will be inserted after the 3.
Notice that there are no insert and place, erase methods.
They're all called insert after and place after erase after.
The iterator doesn't invalidate in this case, it still points to the 3.
So we can also use and place after an erase after in the same way.
And the forward list allows resizing in the same way that the list does.
Okay, so let's head over to the IDE, and we'll see some examples
using a list and then we'll have a challenge exercise using a list.
Okay, so I'm back in the IDE.
I'm in the section 20 workspace, and I'm in the list project and
What I'd like to do here is do the same thing we've been
doing the previous videos.
Go over some examples of using the list container.
Now there's a couple of differences here.
One is I'm including this iterator header file here, and that's
for this advanced function.
I'll talk about that in a second.
It basically allows us to advance an iterator.
We can't really do a plus equals or minus equals on list
iterators, but we can advance some using the advanced function.
So I'll show you that when I get to it.
We have the person class that we've had before.
And in this case, the only difference from the person class that you've seen
before is the default constructor.
Before we just use the default, we let the compiler generate it for us.
Here I want the name to be unknown and I want the h to be
0 when nothing is provided and you'll see why in a little bit.
When we resize a list, it creates objects by using a default.
I want you to see those that word in that age so you can
actually see when that happens.
Other than that, it's exactly the same.
I've got the overloaded constructor here.
I am overloading the less than operator and equality operator.
Those are the 2 real important operators for the stl.
And I've got a friend insertion operator right
here for a stream insertion.
All right, I've got a template function right here that allows me
to display any list of any type.
So the template parameter is t that's being replaced.
Again, you've seen this before with decks and vectors.
So it's just another example here with a list.
So let's go through these examples.
I've got some tests here.
And I'll start with test one.
You can see the output over here.
As I said, I've already run this.
So the test is right there that's where we're at right now.
Here we're creating a list of integers.
And you can see the syntax is exactly as you would expect.
I hope that by now you're seeing these patterns, right.
And it's not like oh my goodness.
In order to use the list, I've got to learn all this new stuff.
The patterns are the same.
If you know how to use the deck you know how to use a vector you
know how to use the list, it's just a matter of going to the stl
documentation and see the nuances and the specifics for each container.
But the general patterns are the same.
So in this case, I'm creating l1 as one 2 3 4 5, and I'm displaying it.
You can see that being displayed right here.
And now I'm creating l2 as a list of std strings.
And what I'm doing is I'm pushing back to the back and front to
the front then I'm displaying.
And you can see exactly what you'd expect.
Remember, a list has a back and it's got a front.
So we're taking advantage of that.
It's very efficient inserting on both ends.
Here I'm creating l3 as a list of integers and I'm using the assignment
using the initializer list, just like we've done with the other containers.
And then I'm displaying l3.
And you can see it right there.
And then we're using the same constructor that we've used before.
And again, I know this is becoming old hat but I I'm doing this
there's a method to my madness, I'm doing this on purpose so
that you can see the consistency between all these containers.
So that's the constructor.
We've got 10 100's.
And then we're displaying l4, there are the 10 100s.
Okay, perfect, so let's move on to the second test.
And that's right here.
You can see the output right over here.
In this case, I've got l as a list of integers from 1
through 10, I'm initializing it.
I'm displaying it.
There's the display right there.
What's the list size.
Well, it's 10.
What's the front?
The front is the 1.
What's the back?
The back is the 10.
Remember, these are references we're getting to them so we can
actually change them if we like.
There's the size is 10, the front and the back.
We can clear the list.
That removes all the elements from it and display it again.
Now it's empty, and its size is 0, as you can see right there.
Okay, again, very, very consistent.
So let's look at -- let's take a look at test 3.
Now test 3 has a couple of things that are going to be different for a list.
Here's l, and we're displaying l which is 1 through 10.
You can see right here is test 3.
And right there is the 1 through the 10.
And now what we're saying is let's resize this to 5.
So what happens here.
Well, it's going to resize it to 5.
Basically, it's going to stop it right here, and all this is gone.
So at this point, if I display l, you can see 1 2 3 4 5 here in the output.
Now this is interesting.
If I resize it to 10, what's going to happen?
Well, it says -- remember, right now it's one 2 3 4 and 5.
So it's going to resize it to 5 new elements, 1 2 3 4 5.
But what's it gonna put in there?
Well, what it's gonna do it's gonna call the default initializer for each
one of those objects for integers and for primitive types it's 0.
So you're going to get something like that when I display it that's exactly
what we see 1 2 3 4 5 and 5 0s.
But when we have object types, it's a whole different story.
In this case, look what I'm doing.
I've created persons is a list of person objects, right.
Now it's empty.
But if I resize it to 5, now I've got 5 person objects, which
ones does it create, it uses the default constructor for them.
So if I display it, you can see those strings that I talked about
earlier in the person class, unknown age 0, unknown age 0.
It's exactly what's happening.
This is one of the things that I talked about i think at the
beginning of this section.
It's very important when we use the stl that we overload the less than, that
we overload the equality operator, that we overload the default constructor.
This is why.
This is a really important reason why.
If we provide an overloaded constructor and we don't provide the default
constructor, this will error out because the default constructor
wouldn't be provided for us.
So we've got to make sure that we we've got all our bases covered there.
Test 4.
Let's have a list here of integers 1 through 10 and display it.
You can see test 4 is right down here.
Actually, let me scroll that up just a little bit so
it's a little easier to see.
There we go.
So here's test 4.
Those are my integers, 1 through 10, that's where I'm at right here.
Now I've got an iterator.
And obviously, I'm using auto.
But obviously if I had to declare that the long way, it would
be std list int iterator it.
But in this case, the compiler is deducing it based on the
return value of the find.
So what am I doing, I'm finding that 5 in l from beginning to end.
So my iterator it is going to be pointing to 5.
Now I know it's there, but it's good practice to check.
So if it is not equal to the end, that means I found it.
And what I want to do is I want to call the insert method on the list
l, and I want to insert a 100, where.
I need the iterator.
That's the -- this is real important with lists, both list and forward list.
So what what do I do.
I need that iterator.
The iterator is pointing to the 5.
In the case of a list, it's going to insert the 100 before the iterator.
So it's going to stick to 100 right in there.
And then when I display the list, you can see right here that the
100 has been inserted between the 4 and the 5, right, to the left or
previous or before the iterator, whatever you want to think about it.
In this case, I've got l2, which is a list from 1000 2000 3000.
Now look what I'm doing, I'm inserting into l.
Remember, l is this guy right here.
Now it's -- l is 1 2 3 4 then a 100 and then 5 6 7 8 9 and 10.
That's l right here.
So what I'm doing is I'm -- remember, my iterator is still pointing
to the 5., it's not invalid because I haven't deleted it.
So my iterator is still pointing right here.
So what I want to do is I want to say I want to insert into l
starting at that iterator, right, here to the left of the iterator.
What do I want to insert?
I want to insert the entire list l2 from beginning to end.
So what do you think that's going to do?
Right in here, it's going to put in 1000 2000 3000, and it's going
to do that super efficiently.
Then when I display the list here again, you can see
what's happening 1 2 3 4.
There's your 1000, and then 1000 2000 3000 and then the 5.
Where's iterator pointing to now?
Still pointing to the 5, it's still valid.
Okay, let me clear this because there's a lot of stuff here.
And this is the advanced function that I was talking about.
This is in the iterator header file.
So what we can do here is we can advance any iterator,
positive or negative assuming it's a bi-directional iterator.
In this case, it is.
There's my iterator, and I want to advance it minus 4.
So remember, iterator was pointing to the 5, right.
So now the 5 is over here.
I want to move it 4 to the left 1 2 3 4.
It's going to be pointing to the 100.
That's what the advanced lets me do.
I can also do positive 4 obviously or positive 2 or anything I want.
So in this case, it's going to be pointing to the 100.
If I display what it's pointing to, there's the 100.
And then i can say l.erase it, what's that going to do, it's
going to erase the element that the iterator is pointing to.
Then I'm displaying it again.
You can see the 100 is gone.
At this point, my iterator becomes invalid.
I just deleted the element it was pointing to.
So don't use that iterator again.
If you need it, reset it.
Okay, test 4 is good.
Now let's take a look at test 5.
In test 5, we'll do a couple of things.
The test 5 just has a couple of pieces of input.
You'll see here it's actually waiting for me to type something
in, so we'll do that in a second.
In test 5, I've got stooges which is a list of person objects I'm
initializing it to Larry Moe and Curly.
And I'm displaying them.
Remember, the person class overloaded the stream insertion operator, so
that's what's happening here, and I'm displaying them that's what I've
got right here, Larry Moe and Curly.
Now I've got a couple of variables here, name and age.
And what I want to do is I want to ask the user to enter the name of the
next stooge and then enter their age.
And let's do that right now.
I'm going to type in -- right in here, I'm just going to type in James.
And let's say that james is 50 years old.
Now when I press enter, what's going to happen is we're coming right
in here on line 130 right here.
And I'm in placing back.
Remember, here I'm not creating an object here, I'm letting the
list create the object for me.
That's what the in place does.
So what's going to happen is James 50 is going to be passed into this method.
This method will create that stooge object and insert
it at the back for me.
So when I press enter, I'll display stooges, and I should
see James 50 at the back, right in here, right after Curly.
So let's do that.
Let me come over here.
I'll press enter.
And you can see now that we've got Larry Frank Moe Curly and James,
right at the back, super efficient.
And then the last thing we want to do here is we want
to insert Frank before Moe.
Okay, so where's Moe, I need to find it.
So I need an iterator that's going to point to Moe.
I'm going to search stooges from beginning to end, and
I'm looking for that object.
What's it going to use?
Operator, equality operator, which I've overloaded.
So it's going to look from Moe 25.
Moe 25 is right here.
I know it's there.
So my iterator, if it's not equal to stooge's n, I found it.
So what I'm going to do is I'm going to insert at that
iterator before the iterator.
Everything on the list happens before the iterator.
I'm going to insert Frank 18.
And then I'm going to display stooges again.
And you can see right here Frank 18 is right before the Moe,
which is exactly like I expected.
All right, and then the last test is test 6.
And this one's pretty cool.
All we're doing is sorting.
Real, real simple.
So in this case, I've got stooges is a list of persons.
And I've got Larry Moe and Curly.
I'm displaying stooges.
And you can see it right here Larry Moe and Curly.
Then I'm sorting it.
I'm saying stooges.sort and then I'm displaying it again.
And look what happened?
Curly Larry Moe.
What operator is being used here?
Operator less than.
We overloaded that.
And what we're doing in our operator less than.
Let me go back in case you didn't remember.
Look at our operator less than is comparing ages.
So here we've got 17 18 and 25.
That's how we decided that we were going to sort, right.
We're not sorting by name.
We could have.
We could have written this as name, but we decided -- well, let's sort by age.
So this is going to sort by that.
Okay, so that's it.
In the next video, we'll do a challenge where we'll simulate a music
player using a doubly linked list.