In this video, we'll learn more about the stl deque container.
In order to use the deque, we must pound include the deque header file.
The deque acts like a double-ended queue.
The deque size is dynamic, and it's handled by the stl so
that's very much like a vector.
But unlike a vector, the elements in the deque are not
stored in contiguous memory.
The deque allows direct element access using the subscript
operator and the .at method.
But unlike a vector that allows efficient insertion and deletion
only at the back, the deque allows efficient insertion and deletion
at the back and at the front.
However, inserting elements into any other part of the deque other than the
front or back is not as efficient.
The deque supports all of the iterators and the iterators may
become invalid again especially when the deque changes size.
Let's first look at a few ways to initialize deques and then we'll
see some of its member methods.
In the first example in this slide, I declared d as a deque of integers
and initialized it to 1 2 3 4 and 5.
In the second example, I declare d1 as a deque of integers.
And I'm using an overloaded constructor to create 10 integers
and initialize them all to 100.
Of course, like all the stl containers, the deque supports
copy and move semantics for initialization and assignment.
In the third example, I'm declaring stooges as a deque of
std strings, and I'm initializing it to Larry Moe and Curly.
Now notice that Moe is a c-style string.
Like vectors and std arrays, deques also support assignment
via initializer list.
So let's see some common methods provided by the deque container.
In this slide, we'll see what a simple deque looks like.
We declare d as a deque of integers, and we initialize it to 1 2 3.
The deque has a front and a back.
The front in this case is the element 1 and the back is element 3.
With the deque, we can efficiently add elements and remove elements
from both the front and the back.
In a deque, the push back method works very much as it does in a vector.
The element to be added is pushed at the back of the deque.
And the push front method adds the element to be inserted
at the front of the deque.
Now let's see how the elements in the deque might be stored in memory.
Remember, the deque's elements are not in contiguous memory.
So usually a deque is implemented as a collection of memory blocks, and
these memory blocks contain elements that are in a contiguous memory.
But the blocks themselves are not in contiguous memory.
So a good way to think of a deque is as a linked list of vectors.
So when we add an element at the front, it adds it if there's space.
If not, it will allocate a new block, add the element to that
block and then link in the block.
The same happens when we add an element at the back.
Again, please refer to the c++ stl documentation for details on
all of the methods for the deque.
There's a lot there, and that's the place to go to.
The documentation is your friend.
Don't think programmers keep all these details in our heads, we don't.
We refer to the c++ docs very often.
Generally, it's open on a second monitor.
It's the same for java programmers.
Usually, they've got the java docs open in a second monitor.
And that's where all the good information is.
So let's see some of these methods.
Let's start with the size method.
This method returns the number of elements that are in the deque.
The max size we've already seen with vectors and std arrays, it's
a pretty big number that just says how many elements can i store.
Deques also allow individual access using either the subscript operator
or the .at method and the rules are the same here if you use the subscript
operator, no balance checking is done.
But if you use the .at method, balance checking will happen
and an exception will be thrown if you're out of bounce.
In this case, you can see that I'm using d.at0, that
refers to the 1 in the deque d, and d sub-1 refers to the 2.
The deque also provides front and back methods that return references
to the elements at the front of the deque and at the back of the deque.
So in this example, d.front refers to the 1 and d d.back refers to the 5.
As I previously mentioned, the deque allows for efficiently
inserting and removing elements at the front and at the back.
Inserting is done with the pushback method and the push front method.
We also have a pop back and a pop front which you officially remove
elements from the back of the front.
In this slide, we have a deque of person objects and called it d.
We can create a person p1 named Larry who is 18 years old.
And we can use the push back method to insert p1 at the back of the deque.
We can also remove it using pop back.
Similarly, we can add a person object to the front of the deque with push
front and remove it with pop front.
Remember, all container classes make copies of the elements they store.
The deque container also supports in place front and in place back,
which are super efficient ways to create initialize objects and store
them in the deque right in place.
So now let's head over to the IDE.
We'll see some examples.
And in the video after that we'll have some challenge
exercises that use deques.
Okay, so I'm in the IDE. I'm in the section 20 workspace
in the deque project.
And this is a really simple example.
The idea behind using a deque is that we're going to use the
front of it or the back of it.
We're not really going to be inserting things into the middle of it.
If you need to do that kind of thing, you're probably
better off using a list.
We'll talk about the list later.
So I'm not going to go into any of the fancy stuff where you can insert
things into the middle of a deque.
I'm just going to keep it really simple because that's
usually the way we use a deque.
So let's start with looking at what we've got here.
We're including a deque, a vector and an algorithm.
We're using the vector in a minute just to do a little simple example.
And here I've got my display function that will display any type of deque.
I'm only using deques of integers in this example, but it's nice
to have this template function.
You can play around with it and practice writing these actually.
This is a really, really easy one to write.
I went over this one in the previous video, the video for vectors.
Okay, so let's take a look at test 1.
I've already run the program.
The output is over here, on the right in the console.
And let's walk through these tests so you can understand
what's happening here.
So this is test 1 right here.
You can see the output of test 1 right up here.
First thing we're doing is we're declaring d as a deque of integers,
and we're putting 1 to 5 in there.
And then we're displaying the deque.
So there it is right here, just as we would expect.
Then I've got an assignment.
I'm using the initializer list to assign, which, again, is really handy.
So now d is 2 4 5 6, and I'm displaying that.
You can see 2 4 5 6 right here.
Now just like we did with the vector here, I'm creating 10
100s, and I'm putting them in the deque and displaying them.
You can see all 100s right here.
And the last thing is right here.
We're doing direct access to the deque.
You don't often do this with a deque.
Remember, the deque -- the whole point of a deque is
to be a doubly ended queue.
So you're going to work on the front, and you're going to work at the back.
That's the idea.
But it lets you have random access to the elements within it at in
constant time, which is cool.
So d sub-0 with the index operator is this is d now, so
it's going to put 100 in here.
And d at 1 we'll put 200 in there.
And when we display that, you can see right here the 100 and
the 200 replaced the 1 and the 2.
All right, so that's pretty straightforward.
Let's look at test 2.
Test 2 is the real workhorse here.
This is the way you typically use a deque.
We're using push back and push front and pop back and so forth.
So let's go over this one because these are the methods that you're
going to really use a lot with the deque.
So what I'm doing here is I'm creating a deque called d again
of integers, and it's 0 0 0.
And the reason I put 0 0 0 in there is just so we can have
these 3 0s in the center.
That way we can really understand how things are being pushed in.
And we're displaying it, you can see right there the 3 0s.
Now we're saying push back a 10, and then push back a 20.
That means at the back.
So first, I push back the 10 and then the 20.
Remember, they're being pushed back this way, and display them and you can
see what we've got 3 0s, 10 and a 20.
Now I want to push front.
So now I'm going to push these guys at the front 100 and then I push 200.
I'm pushing them this way, and I'm displaying it again.
And I've got right here 200 100 the 3 0s and then the 10 and the
20, of course, are still there.
We've got our front method which returns a reference to
the front element, which in this case is that guy right here.
I've got my back method, which returns a reference to the back
element which is the 20 right here and the size, which is 7.
So when we look at the output right here, you can see the front
is 200, the back is 20 and the size is 7, and we display it right
after we pop a few things off it.
So let's try that.
So first thing we do is we pop the back.
That guy's gone.
And then we pop the front, and that guy's gone, and we display it again.
So now we're going to display 100 0 0 0 10.
Notice how the 200 and the 20 are gone.
So this is really the way you're going to use the deque.
If you find yourself using a deque and fiddling around with the middle
elements and inserting things into the middle and doing all kinds of
stuff like that, maybe the deque is not what you should be using.
Consider using a list, and we'll talk about a list in the
next section of the course.
Okay, so that takes care of test 2.
Let's take a look at test 3.
And what I've got here in test 3.
This is what i wanna do.
I've got a vector of 10 integers right here, 1 through 10.
And I've got a deque d, which is empty.
And what I want to do is I want to insert all the even numbers
into the back of the deque and all the odd numbers into the front.
It's pretty easy to do.
I could just use a range-based for loop right here.
And I can iterate over that vector.
Remember, we're coming from a vector to a deque this time.
And if the element mod 2 is 0, that means it is even.
And if it's even, I'm pushing it onto the back, right.
So where we start.
We're starting with the number is even, we're pushing it in the back.
The number is odd, we're pushing it into the front.
So we're going to have the 1 the 2 the 3 the 4 the 5 the 6.
This is what's going to happen, the 8 the 9 and the 10.
That's the result right there.
And when we look at the display for test 3, right here,
that's exactly what we've got.
We've got all the odd numbers here and all the even numbers right there.
Now let's take a look at test 4.
Test 4 is simple but important.
It shows you the ordering of things.
When we push stuff on the front versus we push stuff on the back,
the ordering is obviously different, but this confuses people sometimes.
And I've seen a lot of little mistakes from programmers
that use deques this way and it comes up a lot in code reviews.
So let's take a look.
Here we've got a vector again, 1 through 10.
And what I'm doing is I'm going through the entire vector this time.
There's no if statement.
There's no odd even stuff.
That's all I'm doing is I'm going through that vector and
I'm grabbing each element and I'm pushing it in the front.
So we're starting at the 1.
So we're pushing it 1 2 3 4 5.
Remember, we're pushing things on the front.
So this is the result.
That's a 9 right there.
That's the result.
So when I display this -- and again, I'm in test 4.
You can see it's 10 9 8, all the way down to 1.
I'm gonna clear the deque here.
Then I'm going to do the same thing except now I'm going to push back.
This time we're pushing this way, right.
So we're going to have 1 2 3 4 5 6 7 8 9 and 10.
And when we display that, you can see that that's exactly what we get.
Obviously, the order is going to be different, right.
One's going to be going from 1 to 10, the other from 10 to
1, depending on whether we do a push front or a push back.
And as I said, this is -- sounds simple, but I've seen a lot of
little mistakes using this because somehow people get confused.
Let's take a look at the last test, test 5.
So what we're going to do now is we're going to do the same thing
we did in test 4 except we're going to use std copy to do it.
So what do we have.
We have the same vector, and we have a deque that's empty again.
And what we're going to do is we're simply going to copy everything
in the vector from begin to end.
And we're going to use the front inserter iterator to do
it, so one line of code handles this really, really easily.
So again, loop through the vector at the entire vector.
And for each element in that vector, insert it to the front of the deque d.
So this is test 5.
When we display that, this is what we get right here.
Notice it's the same as test 4 because we're inserting at the front.
And we can clear the deque and do it again.
So copy vec.begin to vec.n.
And this time we're going to do the back inserter.
We're inserting at the back this way.
And what we're going to get is the same thing we got with test 4.
So which should you use, I tend to like this, this is much more expressive.
Most programmers will understand this.
A lot of programmers are not real familiar with the stl algorithms.
So this kind of code right here is foreign to them, and they
could really mess things up, especially junior programmers.
Junior programmers -- the stl is a complicated beast, and a
lot of junior programmers just know the very basics of it.
So when you get a lot of algorithms put together with iterators and
inserters, it's likely a lot of the junior programmers haven't seen that.
So there you go.
That's it.
So that takes care of the deque.
In the next video, we'll do the first challenge for the deque.