Anatomy Of std::deque

Double-ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements.

At its core, std::deque is implemented as a sequence of fixed-size chunks, each acting like an array, linked together to form a dynamic structure. Unlike std::vector, which relies on a single contiguous block of memory, std::deque dynamically allocates and deallocates these chunks.

In a regular queue, elements are added from the rear and removed from the front. However, in a deque, we can insert and remove elements from the front and rear.

Create C++ STL Deque

In order to create a deque in C++, we first need to include the deque header file.

#include <deque>

Once we import this file, we can create a deque using the following syntax:

deque<type> myDQ;

Here, type indicates the data type we want to store in the deque, For example,

// Create a deque of integer data type
deque<int> dqInt;

// Create a deque of string data type
deque<string> dqStr;

Initializing a Deque

We can initialize a C++ deque in the following ways:

// Way 1
deque<int> deqOne = {1, 2, 3, 4 ,5};

// Way 2
deque<int> deqTwo {1, 2, 3, 4, 5};

// Way 3
deque<int> deqThree(5, 2); // deque with five elements, all initialized to 2.

// Way 4
deque<int> deqFour({1, 2, 3, 4, 5}); // deque initialized with array elements.

// Way 5 - Creation of new deque from copying old.
deque<int> oldDeq({1, 2, 3, 4, 5});
deque<int> newDeq(oldDeq); // new deque initialized with old deque elements.

Here, both deqOne and deqTwo are initialized with values 1, 2, 3, 4, 5.

Example :

#include <iostream>
#include <deque>
using namespace std;



int main() {
 
  // uniform initialization 
  deque<int> myDeque {11, 12, 13, 14, 15};

  cout << "myDeque = ";

  // display elements of deque1
  for (int num : myDeque) {
    cout << num << ", ";
  }

  return 0;
}

// Output
myDeque = 11, 12, 13, 14, 15, 

C++ Deque Methods

In C++, the deque class provides various methods to perform different operation on a deque.

1. Element Access Functions:

at(post):

Returns a reference to the element at position pos with bounds checking. Throws an exception if pos is out of range.

std::deque<int> numbers({1, 2, 3});
std::cout << numbers.at(1); // Output: 2

operator[](pos):

Returns a reference to the element at position pos without bounds checking. Unlike at(), it does not perform bounds checking. Developers need to ensure that the index is within a valid range to avoid undefined behavior.

2. Modifiers - Insertion Functions:

push_back(value):

Adds an element value to the end of the deque.

deque<int> numbers;
numbers.push_back(1);
numbers.push_back(2);

In this example, the deque numbers will contain two elements: 1 and 2.

push_front(value):

Adds an element value to the front of the deque.

std::deque<int> numbers;
numbers.push_front(1);
numbers.push_front(2);

Here, the numbers will containe two elements: 2 and 1, in that order. The last inserted element using push_front() will always be the first element of the deque.

emplace_back(args…):

Constructs and inserts an element at the end of the deque.

emplace_front(args…):

Constructs and inserts an element at the front of the deque.

insert(pos, value):

Inserts an element before the specified position. This function takes two parameter - an iterator to the point of insertion, and the value to insert.

std::deque<int> numbers({1, 2, 3});
numbers.insert(numbers.begin() + 1, 7);

In this example, numbers will now contain the elements: 1, 7, 2, 3. The 7 was inserted at the second positon.

insert(pos, count, value):

Inserts multiple copies of a element before the specified position.

3. Modifiers - Erasure Functions:

pop_back():

Removes the last element of the deque. It doesn't take any arguments and doesn't return any value.

std::deque<int> numbers({1, 2, 3});
numbers.pop_back();

After executing the pop_back() function, the numbers deque will only contains two elements: 1 and 2.

pop_front():

Removes the first element of the deque. Similar to pop_back(), it doesn't take any arguments or return any value.

std::deque<int> numbers({1, 2, 3, 4, 5});
numbers.pop_front();

In this case, numbers will contains: 2, 3, 4 and 5 after executing pop_front().

erase(pos):

Removes the element at the specified position. It takes one or two iterators as parameters pointing to the position(s) in the deque to be erased.

std::deque<int> numbers({1, 2, 3, 4, 5});
numbers.erase(numbers.begin() + 1);

After the erase() operation, numbers will contain four elements: 1, 3, and 4. The element 2 was removed from the second position.

erase(first, last):

Removes elements in the specified range.

4. Capacity Functions:

empty():

Checks if the deque is empty. Returns true if the deque is empty. It returns a boolean indicating whether the deque is empty or not.

std::deque<int> numbers({1, 2, 3});
std::cout << numbers.size(); // Output 3
std::cout << numbers.empty(); // Output 0 (False, deque is not empty)

size():

Returns the number of elements in the deque.

max_size():

Returns the maximum possible size of the deque.

resize(count):

Changes the size of the deque. If the new size is greater, elements are inserted. If smaller, elements are removed from the back.

resize(count, value):

Similar to resize(count), but the added elements are initialized with the specified value.

5. Element Access - Front and Back Functions:

front():

Returns a reference to the first element in the deque.

std::deque<int> numbers({1, 2, 3});
std::cout << numbers.front(); // Output: 1

back():

Returns a reference to the last element in the deque.

std::deque<int> numbers({1, 2, 3});
std::cout << numbers.back(); // Output: 3

6. Iterators Functions:

begin(), end():

Returns iterators pointing to the first and past-the-end elements, respectively.

rbegin(), rend():

Returns reverse iterators.

7. Miscellaneous Functions:

clear():

Removes all elements from the deque.

swap(other):

Swaps the content of the deque with another deque.

std::deque<int> numbers1({1, 2, 3});
std::deque<int> numbers2({4, 5, 6});
numbers1.swap(numbers2);

// numbers1 now contains 4, 5, 6

Advantages of std::deque:

1. Constant Time Complexity

Efficient for insertions and deletions at both ends with constant time complexity.

2. Random Access

Supports random access, allowing direct access to elements by position using iterators.

3. Dynamic Memory Allocation

Dynamically allocates and deallocates chunks of memory, providing flexible and memory-efficient structure.

Disadvantages of std::deque:

1. Memory Overhead

The segmented structure may lead to increased memory consumption compared to a single contiguous block, as seen in std::vector.

2. Complexity

The internal structure involving linked chunks introduces complexity potentially impacting performance in simpler scenarios.