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.
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
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.
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 endpush_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 frontback()
- returns element at the backat()
- 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. 1nums.back()
- returns the element at the back of the deque i.e. 3nums.at(1)
- returns the element at index 1 i.e. 2nums[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 3nums.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 backpop_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
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);
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.
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();
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();
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.