WEBVTT 00:00.120 --> 00:07.570 Hello again! In this video, we are going to look at the deque. A deque - or occasionally pronounced "deak", although personally 00:07.650 --> 00:08.280 I think it should be 00:08.490 --> 00:10.410 "de-queue", but no one seems to agree with me! 00:11.010 --> 00:12.900 So this is a double-ended queue. 00:13.740 --> 00:15.210 It is quite similar to a vector. 00:15.510 --> 00:16.710 The difference is, with a vector, 00:16.860 --> 00:20.430 you can efficiently add elements only at the back of the vector. 00:21.090 --> 00:25.290 With a deque, you can efficiently add elements, either at the front or the back. 00:25.800 --> 00:27.690 So that is why it is called "double-ended". 00:29.040 --> 00:32.550 There is a header for defining the C++ library deque 00:32.980 --> 00:36.750 class. This is implemented as a two-dimensional array. 00:36.750 --> 00:40.560 So this is an array whose members are, themselves, arrays. 00:41.550 --> 00:47.130 So comparing the three different types of sequential containers: a vector has one memory block, 00:47.130 --> 00:48.720 which stores all the elements. 00:49.980 --> 00:56.880 The list has a node which is in vector, a memory block for each element. And the deque has multiple 00:56.970 --> 00:59.910 memory blocks, each of which can store several elements. 01:02.580 --> 01:08.190 So, if you iterate over a deque, you start at the first element in the first memory block, and you carry on 01:08.190 --> 01:11.470 until you get to the last element in the last memory block. 01:12.450 --> 01:18.990 The interface is similar to vector, except that deque also has a push_front() member function, and this will 01:18.990 --> 01:21.540 insert an element before the front of the deque. 01:24.140 --> 01:29.150 The other main difference is on how they behave when they restructure themselves, when they run out of 01:29.150 --> 01:35.390 memory. With a vector, this will allocate a new block, copy all the data and release the old block. With a 01:35.390 --> 01:35.680 deque, 01:35.690 --> 01:40.700 it will just allocate a new block for the new data, and leave all the other memory blocks as they are. 01:41.090 --> 01:43.640 So there is no copying of data, and no releasing of blocks. 01:46.060 --> 01:51.430 Just to quickly remind ourselves what a vector looks like: it has a single memory block with all 01:51.430 --> 01:52.240 the data in it. 01:53.020 --> 01:56.350 The control block has one pointer, to this single memory block. 01:58.020 --> 02:06.000 With a deque (squeeze myself in!) A deque has multiple memory blocks, so the control block has a pointer 02:06.000 --> 02:07.290 to each memory block. 02:08.430 --> 02:12.900 We can add at the back or the front. If we are adding at the back, and we run out of memory. 02:13.290 --> 02:18.390 Then it just creates another memory block and puts the data in there, and leaves the other memory blocks 02:18.720 --> 02:19.320 as they are. 02:21.300 --> 02:26.160 And also, we can insert at the front as well. If it runs out of memory, it will add another memory block 02:26.160 --> 02:30.570 at the front, and leave the rest of the data structure untouched. 02:34.320 --> 02:36.800 So let's quickly see how to use a deque. 02:37.410 --> 02:44.700 We need to include the header. Then we can create a deque object. We can call push_back(). 02:45.420 --> 02:49.380 So push_back(4) will add 4 at the back, and push_back(2) will add 2 02:49.500 --> 02:53.400 after the 4. push_front(1) will add 1 at the front. 02:53.910 --> 02:59.610 So 1 goes before these elements. Then if we call push_front() again, that will go in front of the 1. 03:00.300 --> 03:06.510 So these go in the reverse order to the order they are called in, which sometimes confuses people. 03:09.060 --> 03:15.000 So there we are. So we get 3, 5, 1, which is the reverse order, and 4 and 2 go in the same 03:15.000 --> 03:15.270 order. 03:16.380 --> 03:19.020 So, we have three sequential containers to choose from. 03:19.380 --> 03:20.970 How do we decide which one to use? 03:21.990 --> 03:27.300 You might think that the deque would be faster, because it does less copying and it does not have to 03:27.300 --> 03:28.350 release any memory. 03:29.220 --> 03:33.120 In fact, if you do the tests - the ones I have seen anyway - 03:33.540 --> 03:38.580 deque is actually slightly slower than vector for most operations. And I think the reason for that is 03:38.580 --> 03:43.800 that everyone uses vector, so compiler writers do not put a lot of work to into optimizing deque. 03:44.820 --> 03:49.350 One area where deque is much faster is if you are adding and removing elements at the front of the container, 03:49.740 --> 03:52.200 and there you do get the benefits of the different structure. 03:54.420 --> 03:59.250 The obvious thing is that list is much slower than vector and deque for most operations. 03:59.790 --> 04:03.420 And it also uses more memory because you need the pointers for the notes. 04:03.960 --> 04:08.700 It is very good at one thing, which is adding and removing elements, if you have an iterator for 04:08.700 --> 04:11.190 the place where you want to add or remove the element. 04:12.000 --> 04:17.470 If you do not have that, and you need to search or jump to it, then lists are pretty bad at that. 04:18.270 --> 04:23.730 In fact, the time it takes to get to this point can actually outweigh the time that you save by having 04:23.730 --> 04:26.040 more efficient addition or removal. 04:26.670 --> 04:31.860 So, as with all optimizations, you need to test before you make any decisions. 04:33.090 --> 04:36.150 So the overall conclusion is to use vector as the default. 04:37.410 --> 04:42.840 And in fact, the main reason for that is that modern hardware is optimized for accessing contiguous 04:42.840 --> 04:49.170 blocks of memory, and data structures which are not contiguous, like deque and list, can lose out quite 04:49.170 --> 04:49.620 badly. 04:50.850 --> 04:56.790 The reason for this is that all the hardware benchmarks are based around arrays. They are either things like 04:56.790 --> 04:59.400 multimedia, or numerical processing. 04:59.940 --> 05:04.290 And if your processor is good at accessing arrays, then it will get better benchmark numbers. 05:04.620 --> 05:06.600 And that is what the processor manufacturers want. 05:06.630 --> 05:07.590 So that is what they do. 05:08.600 --> 05:09.980 OK, so that is it for this video. 05:10.430 --> 05:13.430 I will see you next time, but until then, keep coding!