C++ Deque

In C++, the STL deque is a sequential container that provides the functionality of a double-ended queue data structure.

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 both the front and rear.

In a deque, we can insert and remove elements from both the front and rear.
Deque Data Structure

To learn more about deques, visit Deque Data Structure.


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> dq;

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

// create a deque of integer data type
deque<int> dq_integer;

// create a deque of string data type
deque<string> dq_string;

Initialize a Deque

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

// method 1: initializer list
deque<int> deque1 = {1, 2, 3, 4, 5};

// method 2: uniform initialization
deque<int> deque2 {1, 2, 3, 4, 5};

Here, both deque1 and deque2 are initialized with values 1, 2, 3, 4, 5.


Example: C++ Deque

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

// function prototype
void display_deque(deque<int>);

int main() {
 
// uniform initialization deque<int> deque1 {1, 2, 3, 4, 5};
cout << "deque1 = "; // display elements of deque1 for (int num : deque1) { cout << num << ", "; } return 0; }

Output

deque1 = 1, 2, 3, 4, 5, 

In the above example, we have declared and initialized a deque named deque1 using uniform initialization.

deque<int> deque1 {1, 2, 3, 4, 5};

Then, we have displayed the deque contents using a ranged for loop.

for (int num : deque1) {
  cout << num << ", ";
}

Other Ways to Create a C++ Deque

Create a deque using fill constructor.

Using the Fill Constructor Method, we can initialize a deque by specifying its size and element. For example,

// fill constructor
deque<int> deque1(5, 12);

Here, we have initialized a deque of size 5 with values 12.

This is equivalent to

deque<int> deque1 = {12, 12, 12, 12, 12};

Notice that all the elements have the same value.

We can also initialize a deque by copying elements from another deque. This is known as the range method.

Create a deque from another deque.

We can copy one deque to another using the range method initialization.

deque<int> deque1 = {1, 2, 3, 4, 5};

// copy all elemnts of deque1 to deque2
deque<int> deque2(deque1.begin(), deque1.end());

Here, we have first created a deque named deque1. Then, we created another deque called deque2 by copying all the elements of deque1.

We can also specify the range of elements we want to copy. For example,

// copy elements from index 1 to index 2 of deque1
deque<int> deque3(deque1.begin() + 1, deque1.begin() + 3);

Here, the start point is deque1.begin() + 1, which points to index 1 of deque1. The end point is deque1.begin() + 3, which points to index 3.

However, deque3 is going to be {2, 3} because the end point is exclusive i.e. the end point will not be copied.


C++ Deque Methods

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

Methods Description
push_back() inserts element at the back
push_front() inserts element at the front
pop_back() removes element from the back
pop_front() removes element from the front
front() returns the element at the front
back() returns the element at the back
at() sets/returns the element at specified index
size() returns the number of elements
empty() returns true if the deque is empty

Insert Elements to a Deque

We can use the following methods to insert elements:

  • push_back() - insert elements at the end
  • push_front() - insert elements at the beginning

For example,

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

int main() {

  deque<int> nums {2, 3};

  cout << "Initial Deque: ";
  for (const int& num : nums) {
    cout << num << ", ";
  }
  
// add integer 4 at the back nums.push_back(4);
// add integer 1 at the front nums.push_front(1);
cout << "\nFinal Deque: "; for (const int& num : nums) { cout << num << ", "; } return 0; }

Output

Initial Deque: 2, 3, 
Final Deque: 1, 2, 3, 4,

In the above example, we have initialized a deque of integers named nums with the elements 2 and 3.

Then, we inserted the integer 4 to the back of the nums.

// nums = {2, 3, 4}
nums.push_back(4);

Finally, we inserted 1 at the front of the deque.

// nums = {1, 2, 3, 4}
nums.push_front(1);

Note: We can also use the insert() and emplace() methods to add elements to the deque.


Access Elements from a Deque

We can use the following methods to access elements of the deque:

  • front() - returns element at the front
  • back() - returns element at the back
  • at() - returns element at the specified index

For example,

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

int main() {

  deque<int> nums {1, 2, 3};
  
  cout << "Front element: " << nums.front() << endl;
  cout << "Back element: " << nums.back() << endl;
  cout << "Element at index 1: " << nums.at(1) << endl;
  cout << "Element at index 0: " << nums[0];
  
  return 0;
}

Output

Front element: 1
Back element: 3
Element at index 1: 2
Element at index 0: 1

In the above example,

  • nums.front() - returns the element at the front of the deque i.e. 1
  • nums.back() - returns the element at the back of the deque i.e. 3
  • nums.at(1) - returns the element at index 1 i.e. 2
  • nums[0] - returns the element at index 0 i.e. 1

Note: While we can use the [] operator to access deque elements, it is preferable to use the at() method.

This is because at() throws an exception whenever the deque is out of bounds, while [] gives a garbage value.


Change Elements of a Deque

We can use the at() method to change the element of the deque. For example,

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

int main() {

  deque<int> nums = {1, 2};
  
  cout << "Initial Deque: ";

  for (const int& num : nums) {
    cout << num << ", ";
  }
  
// change elements at the index nums.at(0) = 3; nums.at(1) = 4;
cout << "\nUpdated Deque: "; for (const int& num : nums) { cout << num << ", "; } return 0; }

Output

Initial Deque: 1, 2,    
Updated Deque: 3, 4,  

In the above example, the initial contents of the nums deque are {1, 2}.

Then, we have used the at() method to change the elements at the specified indexes:

  • nums.at(0) = 2; - changes the value at index 0 changes to 3
  • nums.at(1) = 4; - changes the value at index 1 to 4

Remove Elements from a Deque

We can remove the elements of a deque using the following methods:

  • pop_back() - removes the element from the back
  • pop_front() - removes the element from the front

For example,

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

// function prototype for display_deque()
void display_deque(deque<int>);

int main() {

  deque<int> nums {1, 2, 3};
  
  cout << "Initial Deque: ";
  display_deque(nums);

// remove element from the back nums.pop_back();
cout << "\nDeque after pop_back(): "; display_deque(nums);
// remove element from the front nums.pop_front();
cout << "\nDeque after pop_front(): "; display_deque(nums); return 0; } // utility function to print deque elements void display_deque(deque<int> dq){ for (const int& num : dq) { cout << num << ", "; } }

Output

Initial Deque: 1,  2,  3,  
Deque after pop_back(): 1, 2, 
Deque after pop_front(): 2, 

In the above example, we have initialized an integer deque named nums with the elements {1, 2, 3}.

Then, we used pop_back() and pop_front() to remove elements from nums.

nums.pop_back(); // removes 3
names.pop_front(); // removes 1

So the final deque becomes {2}.


C++ Deque Iterators

Iterators can be used to point to the memory address of a deque element.

We can create a deque iterator using the following syntax:

deque<type>::iterator itertaor_name;

For example,

// iterator for int deque
deque<int>::iterator iter_int;

// iterator for double deque
deque<double>::iterator iter_double;

Access Elements Using Deque Iterators

We can access the elements in deque using iterators. For example,

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

int main() {

  deque<int> nums {1, 2, 3};
  
// declare an iterator to deque deque<int>::iterator dq_iter;
// make iterator point to first element dq_iter = nums.begin();
// print value pointed by itertor using * int first_element = *dq_iter; cout << "nums[0] = " << first_element << endl;
// make iterator point to element at index 1 dq_iter = nums.begin() + 1;
int element_index1 = *dq_iter; cout << "nums[1] = " << element_index1 << endl;
// make iterator point to last element dq_iter = nums.end() - 1;
int last_element = *dq_iter; cout << "nums[2] = " << last_element; return 0; }

Output

nums[0] = 1
nums[1] = 2
nums[2] = 3

In the above example, we have used iterators to access elements in the deque. Initially, we created an iterator that can point to a deque of integers:

deque<int>::iterator dq_iter;

Then, we have used the dq_iter iterator to point to the following elements:

1. The First Element

dq_iter = nums.begin();

Here, the begin() method returns an iterator that points to the first element.

2. Element at Index 1

dq_iter = nums.begin() + 1;

The code begin() + 1 returns an iterator that points to the element at index 1.

Note: To generalize, nums.begin() + i points to the element at index i.

3. The Last Element

dq_iter = nums.end() - 1;

Notice that we are using nums.end() - 1 instead of nums.end().

This is because the end() method iterator points to the iterator past the last element. So, in order to get the final element, we are subtracting 1.

4. Get the Element Value

After using dq_iter to point to a certain element, we use the indirection operator * to get the value of that element:

// point to the first element
dq_iter = nums.begin();

// returns 1
int first_element = *dq_iter;

Here, *dq_iter gives the value of the element pointed to by the dq_iter iterator.


Frequently Asked Questions

How to remove elements at the specified index?

We can remove the element at the specified index using the erase() method. For example,

deque<int> nums {1, 2, 3, 4, 5};

// removes element at index 1
// nums becomes {1, 3, 4, 5}
nums.erase(nums.begin() + 1);

The code above removes the element at index 1 from the nums deque.

So, we can delete the element at any index using:

nums.erase(nums.begin() + index);
How to remove elements in a certain index range?

We can use the erase() method here as well.

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

int main() {

  deque<int> nums {1, 2, 3, 4, 5};
  
// removes elements from index 1 to 2 nums.erase(nums.begin() + 1, nums.begin() + 3);
for(auto num: nums) { cout << num << ", "; } return 0; }

Output

1, 4, 5,

Initially, nums contains the elements {1, 2, 3, 4, 5}.

Then we remove the elements from index 1 to index 2 using,

nums.erase(nums.begin() + 1, nums.begin() + 3); 

Notice that the end point of the range is nums.begin() + 3, but the element at index 3 is not removed.

This is because the end point of the erase() function is exclusive.

How to remove all elements of the deque?

We can use the clear() method to erase all the elements of a deque.

deque<int> nums {1, 2, 3};

// clear all the elements
nums.clear();
How to determine the size of the deque?

We can use the size() method to find the number of elements in the deque.

deque<int> nums {1, 2};

// returns 2
cout << nums.size();

We can also determine if the deque is empty using the empty() method:

// returns false
cout << nums.empty();
Can we use auto to initialize a deque iterator?

Yes, we can use the auto keyword to initialize a deque iterator. However, we cannot use auto to simply declare an iterator without initializing it.

For example, suppose we have an int deque called nums. Then the following code

auto dq_iter = nums.begin();

is equivalent to

deque<int>::iterator dq_iter = nums.begin();

However, the following code is invalid:

auto dq_iter;  // invalid

This is because we haven't initialized dq_iter. As a result, C++ cannot infer its type, thus producing an error.

Did you find this article helpful?