std::deque – Special Version of std::vector

So far, we have seen array-based and linked list-based containers. std::deque mixes both of them and combines each of their advantages to a certain extent. As we have seen, although vector is a variable-length array, some of its functions, such as push_front and pop_front, are very costly operations. std::deque can help us overcome that. Deque is short for double-ended queue.

The Structure of Deque

The C++ standard only defines the behavior of the containers and not the implementation. The containers we have seen so far are simple enough for us to predict their implementation. However, deque is slightly more complicated than that. Therefore, we'll first take a look at its requirements, and then we will try to dive into a little bit of implementation.

The C++ standard guarantees the following time complexities for different operations of deque:

• O(1) for push_front, pop_front, push_back, and pop_back
• O(1) for random access to all the elements
• Maximum of N/2 steps in the case of insertion or deletion in the middle, where N = the size of the deque

Looking at the requirements, we can say that the container should be able to grow in either direction very fast, and still be able to provide random access to all the elements. Thus, the structure has to be somewhat like a vector, but still expandable from the front as well as the back. The requirement for insertion and deletion gives a slight hint that we will be shifting the elements because we are only allowed to take up to N/2 steps. And that also validates our previous assumption regarding behavior that is similar to vector. Since the container can grow in either direction quickly, we don't necessarily have to shift the elements toward the right every time. Instead, we can shift the elements toward the nearest end. That will give us a time complexity of a maximum of N/2 steps, since the nearest end can't be more than N/2 nodes away from any insertion point inside the container.

Now, let's focus on random access and insertion at the front. The structure can't be stored in a single chunk of memory. Rather, we can have multiple chunks of memory of the same size. In this way, based on the index and size of the chunks (or the number of elements per chunk), we can decide which chunk's indexed element we want. That helps us to achieve random access in O(1) time only if we store pointers to all the memory chunks in a contiguous location. Hence, the structure can be assumed to be similar to a vector of arrays.

When we want to insert something at the front, and we don't have enough space in the first memory chunk, we have to allocate another chunk and insert its address in the vector of pointers at the front. That might require reallocation of the vector of pointers, but the actual data will not be moved. To optimize that reallocation, instead of starting from the first chunk, we can start the insertion from the middle chunk of the vector. In that way, we are safe up to a certain number of front insertions. We can follow the same while reallocating the vector of pointers.

Note

Since the deque is not as simple as the other containers discussed in this chapter, the actual implementation might differ or might have a lot more optimizations than we discussed, but the basic idea remains the same. And that is, we need multiple chunks of contiguous memory to implement such a container.

The functions and operations supported by deque are more of a combination of functions supported by vectors and lists; hence, we have push_front, push_back, insert, emplace_front, emplace_back, emplace, pop_front, pop_back, and erase, among others. We also have the vector's functions, such as shrink_to_fit, to optimize the capacity, but we don't have a function called capacity since this is highly dependent on the implementation, and is, therefore, not expected to be exposed. And, as you might expect, it provides random access iterators just like a vector.

Let's take a look at how we can use different insertion and deletion operations on deque:

std::deque<int> deq = {1, 2, 3, 4, 5};

deq.push_front(0);

// deque becomes {0, 1, 2, 3, 4, 5}

deq.push_back(6);

// deque becomes {0, 1, 2, 3, 4, 5, 6}

deq.insert(deq.begin() + 2, 10);

// deque becomes {0, 1, 10, 2, 3, 4, 5, 6}

deq.pop_back();

// deque becomes {0, 1, 10, 2, 3, 4, 5}

deq.pop_front();

// deque becomes {1, 10, 2, 3, 4, 5}

deq.erase(deq.begin() + 1);

// deque becomes {1, 2, 3, 4, 5}

deq.erase(deq.begin() + 3, deq.end());

// deque becomes {1, 2, 3}

Such a structure may be used in cases such as boarding queues for flights.

The only thing that differs among the containers is the performance and memory requirements. Deque will provide very good performance for both insertion and deletion at the front as well as the end. Insertion and deletion in the middle is also a bit faster than for a vector on average, although, asymptotically, it is the same as that of a vector.

Apart from that, deque also allows us to have customer allocators just like a vector. We can specify it as a second template parameter while initializing it. One thing to note here is that the allocator is part of the type and not part of the object. This means we can't compare two objects of two deques or two vectors where each has a different kind of allocator. Similarly, we can't have other operations, such as an assignment or copy constructor, with objects of different types of allocators.

As we saw, std::deque has a slightly more complex structure compared to other containers we examined before that. It is, in fact, the only container that provides efficient random access along with fast push_front and push_back functions. Deque is used as an underlying container for others, as we'll see in the upcoming section.