Double-Ended Queues using std::deque

In this lesson, we’ll introduce double-ended queues, commonly called deques. As we might expect, a double-ended queue is a queue where we can efficiently manipulate either end, typically called the "back" and the "front" of the queue.

The C++ standard library’s implementation of a deque is std::deque, and goes far beyond these basic capabilities. It has a full suite of features, effectively replicating the abilities of dynamic arrays, such as a std::vector.

For example, we can iterate through all the elements of a std::deque, and can directly access elements in any position using the [] operator.

We’ll explore all of these capabilities, and see how std::deque compares to other containers throughout this lesson.

Creating a std::deque

The standard library’s implementation of a deque is std::deque. available in the <deque> header.

We can create them in a similar way to other containers, by passing the type of data we’re storing as a template argument. In this case, we create a std::deque for storing int objects:

1#include <deque>
2
3int main(){
4  std::deque<int> Deque;
5}

We can provide an initial list of values for our std::deque:

1#include <deque>
2
3int main(){
4  std::deque<int> Deque{1, 2, 3, 4, 5};
5}

As we’re used to, class template argument deduction (CTAD) is supported. So, we can omit the template argument in scenarios where the compiler can infer it:

1#include <deque>
2
3int main(){
4  std::deque Deque{1, 2, 3, 4, 5};
5}

We can also provide a pair of iterators to specify a series of objects with which to initialize our deque.

We cover iterators in more detail later in the course, but the basic example below shows how we can initialize a deque with every value from another container:

1#include <deque>
2#include <vector>
3
4int main(){
5  std::vector Numbers{1, 2, 3, 4, 5};
6  std::deque Deque{
7    Numbers.begin(), Numbers.end()
8  };
9}

As of C++23, we can initialize a std::deque using a range. A range is a recent addition to the language, which we cover in more detail later in the course.

For now, we can note that most of the containers we’ve been working with so far are ranges, so we can initialize a std::deque using their values like this:

1#include <deque>
2#include <vector>
3
4int main(){
5  std::vector Numbers{1, 2, 3, 4, 5};
6  std::deque Deque{std::from_range, Numbers};
7}

Iterating over a Deque

The simplest way of iterating over a deque is using a range-based for loop. We cover these in more detail later in the course, but a basic example looks like this:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Values: ";
8  for (auto i : Deque) {
9    std::cout << i << ", ";
10  }
11}

1Values: 1, 2, 3,

Accessing Front and Back Elements

As we might expect, the main use of a deque focuses on accessing and manipulating elements at either end of the collection.

front()

The front() method returns a reference to the first element in the deque:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::cout << "Front: " << Deque.front();
7}

1Front: 1

back()

The back() method returns a reference to the last element in the deque:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::cout << "Back: " << Deque.back();
7}

1Back: 3

Adding Objects to the Front and Back

Similar to other containers, std::deque gives us the ability to "emplace" and "push" objects, adding them to the collection. Given the container is double-ended, we can add elements either to the front or the back.

emplace_front()

The most efficient way of adding an object to a deque is by emplacing it. This constructs the object directly into the queue, removing the need to move or copy it into place. Any arguments we pass to an emplace function get forwarded to the constructor for the type our deque is storing.

The emplace_front() function constructs our object at the start of the collection:

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
25
26int main(){
27  std::deque<Character> Deque;
28  Deque.emplace_front("Roderick"); 
29  std::cout
30    << "\nFront: "
31    << Deque.front().Name;
32}

1Constructing Roderick
2Front: Roderick

push_front()

When we want to add an object that already exists to our deque, we can use push_back(). This lets us move or copy it into our collection:

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
25
26int main(){
27  std::deque<Character> Deque;
28
29  Character Player1{"Roderick"};
30  Deque.push_front(Player1); 
31  std::cout
32    << "\nFront: "
33    << Deque.front().Name;
34
35  std::cout << "\n\n";
36
37  Character Player2{"Anna"};
38  Deque.push_front(std::move(Player2)); 
39  std::cout
40    << "\nFront: "
41    << Deque.front().Name;
42}

1Constructing Roderick
2Copying Roderick
3Front: Roderick
4
5Constructing Anna
6Moving Anna
7Front: Anna

We covered the mechanics of moving and copying earlier in our course, in our lessons on memory management:

Copy Semantics and Return Value Optimization

Learn how to control exactly how our objects get copied, and take advantage of copy elision and return value optimization (RVO)

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

emplace_back()

We can also construct objects into the back of our collection using emplace_back():

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
25
26int main(){
27  std::deque<Character> Deque;
28  Deque.emplace_back("Roderick"); 
29  std::cout << "\nBack: " << Deque.back().Name;
30}

1Constructing Roderick
2Back: Roderick

push_back()

And we can push existing objects to the back of our collection using push_back():

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
25
26int main(){
27  std::deque<Character> Deque;
28
29  Character Player1{"Roderick"};
30  Deque.push_back(Player1); 
31  std::cout << "\nBack: " << Deque.back().Name;
32
33  std::cout << "\n\n";
34
35  Character Player2{"Anna"};
36  Deque.push_back(std::move(Player2)); 
37  std::cout << "\nBack: " << Deque.back().Name;
38}

1Constructing Roderick
2Copying Roderick
3Back: Roderick
4
5Constructing Anna
6Moving Anna
7Back: Anna

Prepending and Appending Ranges

As of C++23, we can now add entire ranges to the front or back of our deque. We cover ranges in more detail later, but most of the sequential containers we’ve seen so far are valid ranges. This includes deques.

The following examples show how we can push all of the content of such a container into our deque.

append_range()

The append_range() method pushes the contents of a range to the back of our deque:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::deque ExtraNumbers{4, 5, 6};
7
8  Deque.append_range(ExtraNumbers);
9
10  std::cout << "Values: ";
11  for (auto i : Deque) {
12    std::cout << i << ", ";
13  }
14}

1Values: 1, 2, 3, 4, 5, 6,

prepend_range()

The prepend_range() method pushes the contents of a range to the front of our deque:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::deque ExtraNumbers{-2, -1, 0};
7
8  Deque.prepend_range(ExtraNumbers);
9
10  std::cout << "Values: ";
11  for (auto i : Deque) {
12    std::cout << i << ", ";
13  }
14}

1Values: -2, -1, 0, 1, 2, 3,

Removing the First and Last Elements

Similar to regular queues, we can "pop" objects, removing them. Naturally, with double-ended queues, we can pop elements from either end.

pop_front()

The pop_front() method removes the element that is first in the queue:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Front: " << Deque.front();
8  Deque.pop_front();
9  std::cout << "\nFront: " << Deque.front();
10  Deque.pop_front();
11  std::cout << "\nFront: " << Deque.front();
12}

1Front: 1
2Front: 2
3Front: 3

pop_back()

The pop_back() method removes the element that is last in the queue:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Back: " << Deque.back();
8  Deque.pop_back();
9  std::cout << "\nBack: " << Deque.back();
10  Deque.pop_back();
11  std::cout << "\nBack: " << Deque.back();
12}

1Back: 3
2Back: 2
3Back: 1

Deque Size

There are two main ways we can check how many elements are in our deque

size()

The size() method returns a size_t, representing how many objects are in the collection:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Size: " << Deque.size();
8  Deque.pop_front();
9  std::cout << "\nSize: " << Deque.size();
10  Deque.emplace_front(1);
11  std::cout << "\nSize: " << Deque.size();
12}

1Size: 3
2Size: 2
3Size: 3

empty()

If we want to know whether the collection is empty - that is, if its size() == 0 we can use the more descriptive empty() method:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1};
6
7  if (!Deque.empty()) {
8    std::cout << "The deque is not empty\n";
9  }
10
11  Deque.pop_front();
12
13  if (Deque.empty()) {
14    std::cout << "But now it is";
15  }
16}

1The deque is not empty
2But now it is

Accessing Arbitrary Elements

Similar to arrays like std::array and std::vector, the std::deque container provides access to arbitrary elements in any position.

The [] operator

We can get a reference to an element in any position by passing the position index to the [] operator. As usual, the indexing is zero-based, that is, the element in the first position is at index 0:

Therefore, [0] is equivalent to accessing the front() element, and [1] accesses the second element. The last element, equivalent to the back() method is at index size() - 1:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  // Equivalent to Deque.front()
8  std::cout << "First: " << Deque[0];
9
10  std::cout << "\nSecond: " << Deque[1];
11
12  // Equivalent to Deque.back()
13  std::cout
14    << "\nLast: "
15    << Deque[Deque.size() - 1];
16}

1First: 1
2Second: 2
3Last: 3

The at() method

The at() method also gives us access to arbitrary elements, by passing its index as an argument. The at() method performs an additional check to ensure the index we pass is within a valid range, given the size of our deque.

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "First: " << Deque.at(0);
8  std::cout << "\nSecond: " << Deque.at(1);
9  std::cout << "\nThird: " << Deque.at(2);
10}

1First: 1
2Second: 2
3Third: 3

The key difference between [] and at() is that If the index passed to at() is not within the bounds of our collection, an exception will be created.

We cover exceptions in more detail later in the course - for now, we can just note that they’re a way we can detect and handle error states in our programs:

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  try { Deque.at(100); }
8  catch (...) {
9    std::cout << "Something went wrong...\n";
10  }
11  std::cout << "but we caught it and recovered";
12}

1Something went wrong...
2but we caught it and recovered

Erasing Arbitrary Elements

We can erase one or more elements from our collection using the erase() method.

Erasing a Single Element

The erase() method requires an iterator that points to the element in the deque to erase. We cover iterators in detail later in the course, but we can effectively get an iterator to the index we want by using the begin() method, alongside the + operator to get to any index we want.

The following example creates iterators for index 0, 1, and 2:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  auto Iterator0 { Deque.begin() };
8  auto Iterator1 { Deque.begin() + 1 };
9  auto Iterator2 { Deque.begin() + 2 };
10}

In this example, we apply this technique to erase the element at index 2 of our deque:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3, 4, 5};
6
7  Deque.erase(Deque.begin() + 2);
8
9  std::cout << "Values: ";
10  for (auto i : Deque) {
11    std::cout << i << ", ";
12  }
13}

1Values: 1, 2, 4, 5,

Erasing Multiple Elements

An alternative form of the erase() method accepts a pair of iterators. Everything from the first iterator to the second iterator will be erased. The following example erases the middle three elements of our collection:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3, 4, 5};
6
7  Deque.erase(Deque.begin() + 1,
8              Deque.end() - 1);
9
10  std::cout << "Values: ";
11  for (auto i : Deque) {
12    std::cout << i << ", ";
13  }
14}

1Values: 1, 5,

Inserting Elements in any Position

We are not restricted to inserting elements just at the beginning or end of a deque. We have several options for inserting elements into any part of the deque.

emplace()

The emplace() method constructs objects in place. Where this is possible, it is the preferred method, as it minimizes the performance overhead of moving or copying objects.

The first argument to emplace() is an iterator denoting where we want the object to be constructed. Any remaining arguments are forwarded to the constructor of the type our deque is storing.

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{100, 300};
6
7  Deque.emplace(Deque.begin() + 1, 200);
8
9  std::cout << "Values: ";
10  for (int x : Deque) {
11    std::cout << x << ", ";
12  }
13}

1Values: 100, 200, 300,

Below, we have a more complex example, where we’re constructing an object of a custom type:

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
19
20int main(){
21  std::deque<Character> Deque;
22
23  Deque.emplace_back("Player 1");
24  Deque.emplace_back("Player 3");
25
26  Deque.emplace(Deque.begin() + 1, "Player 2");
27
28  std::cout << "Values: ";
29  for (const Character& C : Deque) {
30    std::cout << C.Name << ", ";
31  }
32}

1Values: Player 1, Player 2, Player 3,

insert() a single object

When we want to add an object that already exists to our deque, we can use the insert() method. The first argument will be an iterator pointing to where we want the object to be inserted. The second argument will be the object we want to copy or move.

In the following example, we use the insert() method to copy one object into our deque, and to move another.

1#include <deque>
2#include <iostream>
3
Character Class|Show
4class Character {/*...*/};
22
23int main(){
24  std::deque<Character> Deque;
25
26  Deque.emplace_back("Player 1");
27  Deque.emplace_back("Player 4");
28
29  // Copying a Character into the deque
30  Character Player2{"Player 2"};
31  Deque.insert(Deque.begin() + 1, Player2);
32
33  // Moving a Character into the deque
34  Character Player3{"Player 3"};
35  Deque.insert(Deque.begin() + 2,
36               std::move(Player3));
37
38  std::cout << "Values:\n";
39  for (const Character& C : Deque) {
40    std::cout << C.Name << '\n';
41  }
42}

1Values:
2Player 1
3Player 2
4Player 3
5Player 4

insert() multiple copies of an object

Another form of the insert() method allows us to insert multiple copies of an object. It uses three arguments:

1. An iterator to the position we want to insert the object
2. An integer representing the number of copies we want to insert
3. The object we want to copy

In the following example, we insert 2 copies of the 10 object, starting from index 1 of our deque:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  Deque.insert(Deque.begin() + 1, 2, 10);
8
9  std::cout << "Values: ";
10  for (int x : Deque) {
11    std::cout << x << ", ";
12  }
13}

1Values: 1, 10, 10, 2, 3,

insert() multiple objects

The insert() method also allows us to pass two additional iterators as the second and third arguments. Objects from the second iterator to the third iterator will be inserted into our deque.

Below, we select the middle three elements of our Extra collection, and insert them into our Deque collection, starting at index 1:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 5, 6};
6  std::deque Extra{1, 2, 3, 4, 5};
7
8  Deque.insert(Deque.begin() + 1,
9               Extra.begin() + 1,
10               Extra.end() - 1);
11
12  std::cout << "Values: ";
13  for (int x : Deque) {
14    std::cout << x << ", ";
15  }
16}

1Values: 1, 2, 3, 4, 5, 6,

insert_range()

As of C++23, we can insert a range into our deque, using the insert_range() method. The first argument is an iterator denoting where we want the range to be inserted, and the second argument is the range we want to insert.

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 5, 6};
6  std::deque Extra{2, 3, 4};
7
8  Deque.insert_range(Deque.begin() + 1, Extra);
9
10  std::cout << "Values: ";
11  for (int x : Deque) {
12    std::cout << x << ", ";
13  }
14}

1Values: 1, 2, 3, 4, 5, 6,

Replacing Contents

We have a few options that let us replace the entire contents of our deque with a new set of objects.

assign()

We can replace the contents in our std::deque by passing a list of new objects to the assign() method:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  Deque.assign({4, 5, 6});
8
9  std::cout << "Values: ";
10  for (int x : Deque) {
11    std::cout << x << ", ";
12  }
13}

1Values: 4, 5, 6,

An alternative form of the assign() method accepts two arguments - a quantity and an object. Our deque will then be updated to contain that quantity of copies of the object. In the following example, we set our deque to contain 5 copies of the 2 object:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  Deque.assign(5, 2);
8
9  std::cout << "Values: ";
10  for (int x : Deque) {
11    std::cout << x << ", ";
12  }
13}

1Values: 2, 2, 2, 2, 2,

The assign method can also receive a pair of iterators, replacing the deque contents with everything from the first iterator until the second iterator.

Below, we update our Deque to contain the middle 3 objects from the Replacements collection:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::deque Replacements{1, 2, 3, 4, 5};
7
8  Deque.assign(Replacements.begin() + 1,
9               Replacements.end() - 1);
10
11  std::cout << "Values: ";
12  for (int x : Deque) {
13    std::cout << x << ", ";
14  }
15}

1Values: 2, 3, 4,

assign_range()

As of C++23, we can replace the contents of a deque with the contents of any range, using the assign_range() method:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::deque Replacements{4, 5, 6};
7
8  Deque.assign_range(Replacements);
9
10  std::cout << "Values: ";
11  for (int x : Deque) {
12    std::cout << x << ", ";
13  }
14}

1Values: 4, 5, 6,

clear()

Everything in our deque can be removed using the clear() method:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  Deque.clear();
8
9  if (Deque.empty()) {
10    std::cout << "The deque is empty";
11  }
12}

1The deque is empty

swap()

The swap() method switches the content within two deque objects. This is highly performant, and one of the most efficient ways of moving a std::deque.

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque A{1, 2, 3};
6  std::deque B{4, 5, 6};
7
8  A.swap(B);
9
10  std::cout << "A Values: ";
11  for (int x : A) { std::cout << x << ", "; }
12
13  std::cout << "\nB Values: ";
14  for (int x : B) { std::cout << x << ", "; }
15}

1A Values: 4, 5, 6,
2B Values: 1, 2, 3,

Memory Management

Similar to std::vector, the std::deque container includes some additional methods to provide some high-level memory management.

resize()

The resize() method changes the number of objects our deque is holding. If we resize() the container to be smaller than its current size, we are effectively pruning elements from the end of the container:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Size: " << Deque.size();
8  Deque.resize(1); 
9  std::cout << "\nNew Size: " << Deque.size();
10  std::cout << "\nValue: " << Deque.front();
11}

1Size: 3
2New Size: 1
3Value: 1

If we’re resizing the deque to be bigger than its current size, the excess space will be filled with default-constructed objects of the type our deque is holding.

We can customize this by passing a second argument to the resize() function, passing a different value to be used instead.

Below, we resize our deque from 3 to 5, and use the value 10 to fill the additional two spaces:

1#include <deque>
2#include <iostream>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6
7  std::cout << "Size: " << Deque.size();
8
9  Deque.resize(5, 10); 
10
11  std::cout << "\nNew Size: " << Deque.size();
12
13  std::cout << "\nValues: ";
14  for (int x : Deque) {
15    std::cout << x << ", ";
16  }
17}

1Size: 3
2New Size: 5
3Values: 1, 2, 3, 10, 10,

1#include <algorithm>
2#include <deque>
3
4int main(){
5  std::deque Source{1, 2, 3, 4, 5};
6  std::deque<int> Dest;
7
8  Dest.resize(Source.size());
9  std::ranges::copy(Source, Dest.begin());
10}

max_size()

The max_size() method returns a size_t representing the maximum number of objects our std::deque can hold in the current environment.

In most scenarios, this is likely to be a very big number and not something we need to worry about. But, in some environments or use cases, it’s worth remembering that constraints like this do exist.

1#include <iostream>
2#include <deque>
3
4int main(){
5  std::deque Deque{1, 2, 3};
6  std::cout << "Max Size: " << Deque.max_size();
7}

1Max Size: 4611686018427387903

shrink_to_fit()

Finally, we have the shrink_to_fit() method. This requests that the std::deque free any memory it is not using.

In general, this is almost never required. Behind the scenes, deques are much more proactive about managing their memory than other containers such as std::vector. As such, they rarely get into a state where they’re holding significantly more memory than they need.

But, in memory-constrained environments, we still have the option to manually intervene if needed:

1#include <deque>
2
3int main(){
4  std::deque<int> Deque;
5  for (int i{0}; i < 1'000; ++i) {
6    Deque.push_back(i);
7  }
8
9  for (int i{0}; i < 900; ++i) {
10    Deque.pop_back();
11  }
12
13  Deque.shrink_to_fit();
14}

Summary

In this lesson, we've explored the std::deque container in C++, which provides a double-ended queue. We've seen how to create deques, manipulate elements at both ends, and access elements at arbitrary positions. Key takeaways:

• std::deque is a container adapter that provides efficient insertion and deletion at both ends
• Elements in a std::deque are not stored contiguously in memory
• Elements can be inserted at the front using push_front() and emplace_front(), and at the back using push_back() and emplace_back()
• Entire ranges can be inserted at the front using prepend_range() and at the back using append_range()
• Elements can be removed from the front using pop_front() and from the back using pop_back()
• The size of a std::deque can be checked using size() and empty()
• Random access to elements is provided through the [] operator and the at() method
• Elements can be erased at arbitrary positions using erase()
• Elements can be inserted at arbitrary positions using insert() and emplace()
• The contents of a std::deque can be replaced using assign(), assign_range(), or clear()
• The size of a std::deque can be changed using resize(), and its capacity can be optimized using shrink_to_fit()
• The maximum size of a std::deque is given by max_size(), which depends on the system's memory constraints

Next Lesson

First Class Functions

Learn about first-class functions in C++: a feature that lets you store functions in variables, pass them to other functions, and return them, opening up new design possibilities

ContinueView Course