Hello again! In this video, we are going to look at the deque. A deque - or occasionally pronounced "deak", although personally
I think it should be
"de-queue", but no one seems to agree with me!
So this is a double-ended queue.
It is quite similar to a vector.
The difference is, with a vector,
you can efficiently add elements only at the back of the vector.
With a deque, you can efficiently add elements, either at the front or the back.
So that is why it is called "double-ended".
There is a header for defining the C++ library deque
class. This is implemented as a two-dimensional array.
So this is an array whose members are, themselves, arrays.
So comparing the three different types of sequential containers: a vector has one memory block,
which stores all the elements.
The list has a node which is in vector, a memory block for each element. And the deque has multiple
memory blocks, each of which can store several elements.
So, if you iterate over a deque, you start at the first element in the first memory block, and you carry on
until you get to the last element in the last memory block.
The interface is similar to vector, except that deque also has a push_front() member function, and this will
insert an element before the front of the deque.
The other main difference is on how they behave when they restructure themselves, when they run out of
memory. With a vector, this will allocate a new block, copy all the data and release the old block. With a
deque,
it will just allocate a new block for the new data, and leave all the other memory blocks as they are.
So there is no copying of data, and no releasing of blocks.
Just to quickly remind ourselves what a vector looks like: it has a single memory block with all
the data in it.
The control block has one pointer, to this single memory block.
With a deque (squeeze myself in!) A deque has multiple memory blocks, so the control block has a pointer
to each memory block.
We can add at the back or the front. If we are adding at the back, and we run out of memory.
Then it just creates another memory block and puts the data in there, and leaves the other memory blocks
as they are.
And also, we can insert at the front as well. If it runs out of memory, it will add another memory block
at the front, and leave the rest of the data structure untouched.
So let's quickly see how to use a deque.
We need to include the header. Then we can create a deque object. We can call push_back().
So push_back(4) will add 4 at the back, and push_back(2) will add 2
after the 4. push_front(1) will add 1 at the front.
So 1 goes before these elements. Then if we call push_front() again, that will go in front of the 1.
So these go in the reverse order to the order they are called in, which sometimes confuses people.
So there we are. So we get 3, 5, 1, which is the reverse order, and 4 and 2 go in the same
order.
So, we have three sequential containers to choose from.
How do we decide which one to use?
You might think that the deque would be faster, because it does less copying and it does not have to
release any memory.
In fact, if you do the tests - the ones I have seen anyway -
deque is actually slightly slower than vector for most operations. And I think the reason for that is
that everyone uses vector, so compiler writers do not put a lot of work to into optimizing deque.
One area where deque is much faster is if you are adding and removing elements at the front of the container,
and there you do get the benefits of the different structure.
The obvious thing is that list is much slower than vector and deque for most operations.
And it also uses more memory because you need the pointers for the notes.
It is very good at one thing, which is adding and removing elements, if you have an iterator for
the place where you want to add or remove the element.
If you do not have that, and you need to search or jump to it, then lists are pretty bad at that.
In fact, the time it takes to get to this point can actually outweigh the time that you save by having
more efficient addition or removal.
So, as with all optimizations, you need to test before you make any decisions.
So the overall conclusion is to use vector as the default.
And in fact, the main reason for that is that modern hardware is optimized for accessing contiguous
blocks of memory, and data structures which are not contiguous, like deque and list, can lose out quite
badly.
The reason for this is that all the hardware benchmarks are based around arrays. They are either things like
multimedia, or numerical processing.
And if your processor is good at accessing arrays, then it will get better benchmark numbers.
And that is what the processor manufacturers want.
So that is what they do.
OK, so that is it for this video.
I will see you next time, but until then, keep coding!