Question

Explain how a deque works internally by providing a thorough explanation of how the item insertion happens. C++

Answer 1

• In this article we will discuss what is a deque and how it works internally.

Deque is a double ended queue container that provides insertion and deletion at both ends i.e. front and back with
high performance unlike vector that provides high performance insertion at end i.e. back only.

Also it provides random access to elements just like a vector. Although one can insert an element in between other elements in dequeue with insert() function, but its performance will not be good just like vector.

Header File required,

#include <deque>

Inserting an element in front of deque,

dequeObj.push_front(4);

dequeObj.push_front(3);

Inserting an element in back/end of deque,

dequeObj.push_back(5);

dequeObj.push_back(6);

Now Deque will contain elements in following order,
3, 4, 5, 6

Deleting element from front of deque,

dequeObj.pop_front();

Now Deque will contain elements in following order,
4, 5, 6

Deleting element from back of deque,

dequeObj.pop_back();

Now Deque will contain elements in following order,
4, 5

How std::deque works internally

Now a question rises how high deque is able to give good performance for insertion and deletion at both ends?
To know the answer we need to know little internal implementation of dequeue.

A deque is generally implemented as a collection of memory blocks. These memory blocks contains the elements at contiguous locations.

When we create a deque object it internally allocates a memory block to store the elements at contigious location.

• When we insert an element in end it stores that in allocated memory block untill it gets filled and when this memory block gets filled with elements then it allocates a new memory block and links it with the end of previous memory block. Now further inserted elements in the back are stored in this new memory block.
• When we insert an element in front it allocates a new memory block and links it with the front of previous memory block. Now further inserted elements in the front are stored in this new memory block unless it gets filled.
• Consider deque as a linked list of vectors i.e. each node of this linked list is a memory block that store elements at contiguous memory location and each of the memory block node is linked with its previous and next memory block node.

Therefore, insertion at front is fast as compared to vector because it doesn’t need the elements to shift by 1 in current memory block to make space at front. It just checks if any space is left at left of first element in current memory block, if not then allocates a new memory block.

Complete deque example is as follows,

#include <iostream>

#include <deque>

int main()

{

std::deque<int> dequeObj;

dequeObj.push_back(5);

dequeObj.push_back(6);

for(int i = 0; i< dequeObj.size(); i++)

std::cout<<dequeObj[i]<<" ";

std::cout<<std::endl;

dequeObj.push_front(4);

dequeObj.push_front(3);

for(int i = 0; i< dequeObj.size(); i++)

std::cout<<dequeObj[i]<<" ";

std::cout<<std::endl;

dequeObj.pop_back();

for(int i = 0; i< dequeObj.size(); i++)

std::cout<<dequeObj[i]<<" ";

std::cout<<std::endl;

dequeObj.pop_front();

for(int i = 0; i< dequeObj.size(); i++)

std::cout<<dequeObj[i]<<" ";

std::cout<<std::endl;

return 0;

}

Output is as follows,

5 6
3 4 5 6
3 4 5
4 5