Home | Projects | Notes > C++ Programming > Sequence Container - std::deque

Sequence Container - std::deque

std::deque

• Declared in the <deque> header file.

• Acts like a double-ended queue.

• Dynamic size

  • Can expand and contract as needed which is handled automatically by the STL.

  • Elements are NOT stored in continguous memory.

    • Usually, a deque is implemented as a collection of memory blocks, and these memory blocks and these memory blocks contain elements that are in a contiguous memory. However, the blocks themselves are not in contiguous memory.

    • A good way to think of a deque is as a linked list of vectors. So when adding an element at the front, it adds it if there's a space. If not, it will allocate a new block, add the element to that block and then link in the block. (The same happens when adding an element at the back.)

• Direct element access - Constant time: O(1)

• Rapid insertion and deletion at the front and back - Constant time: O(1)

• Insertion or deletion of elements (elsewhere) - Linear time: O(n)

• All iterators are available but may become invalid.

  • Iterator invalidation can occur when a std::deque changes size.

Initialization and Assignment

13
1
// Initialization
2
std::deque<int> d1{1, 2, 3, 4, 5};
3
std::deque<int> d2(10, 100);    // ten 100s
4

5
// Initialization
6
std::deque<std::string> d3{
7
    std::string{"Kyungjae"},
8
    "Sunny",    // C-style string will be converted to a std::string.
9
    std::string{"Yena"}
10
};
11

12
// Assignment via initializer list
13
d1 = {2, 4, 6, 8, 10};

Common Methods

For more information, see cppreference.com.

21
1
std::deque<int> d1{1, 2, 3, 4, 5};
2
std::deque<int> d2{10, 20, 30, 40, 50};
3

4
std::cout << d1.size();     // 5
5
std::cout << d1.max_size(); // A very large number
6
std::cout << d1.at(0);      // 1 (Supports out-of-bounds check)
7
std::cout << d1[1];         // 2 (Does not support out-of-bounds check)
8
std::cout << d1.front();    // 1 (Returns reference to the first element)
9
std::cout << d1.back();     // 5 (Returns reference to the last element)
10
std::cout << d1.empty();    // 0 (false)
11

12
std::sort(d1.begin(), d1.end());
13

14
auto it = std::find(d1.begin(), d1.end(), 3);
15
d1.insert(it, 10);          // 1, 2, 10, 3, 4, 5
16

17
it = std::find(d1.begin(), d1.end(), 4);
18
d1.insert(it, d2.begin(), d2.end());
19
    // 1, 2, 10, 3, 10, 20, 30, 40, 50, 4, 5
20

21
d1.swap(d2);                // Swaps the two deques

max_size(): Returns the maximum number of elements a vector can theoretically hold on the current

system. This is typically a very large number and depends on system and implementation limits.

9
1
person p{"Kyungjae", 30};
2
std::deque<person> d;
3

4
d.push_back(p);                 // Add p to the back (copy is made)
5
d.pop_back();                   // Remove the last element (p in this case)
6
d.push_front(person{"Sunny", 20});
7
d.pop_front();                  // Remove element from the front
8
d.emplace_front("Yena", 5);     // Construct the object in-place. Very efficient!
9
d.emplace_back("Sunny", 20);    // Construct the object in-place. Very efficient!

L4: Remember, all standard container classes store copies of the elements they hold. So in this case, a copy of p is made.

L6: Creates a temporary (unnamed) person object and adds it to the deque using move semantics.

L8: Constructs the person object directly in place using the constructor. Very efficient - no moves, no copies. It’s built exactly where it needs to be. Use this!

Project: Usage of std::deque

std::deque is ideal when you need fast insertions or deletions at both the front and back of the container. It is not optimized for frequent insertions or removals in the middle. If your use case involves modifying elements in the middle, consider using std::list instead.

x
1
#include <iostream>
2
#include <deque>
3
#include <vector>
4
#include <algorithm>
5

6
// Template function to print elements of any deque.
7
template <typename T>
8
void print(const std::deque<T> &d)
9
{
10
    std::cout << "[ ";
11
    for (const auto &elem : d)
12
    {
13
        std::cout << elem << " ";
14
    }
15
    std::cout << "]" << std::endl;
16
}
17

18
// [], at()
19
void test1(void)
20
{
21
    std::cout << "\nTEST1" << std::endl;
22

23
    std::deque<int> d{1, 2, 3, 4, 5};
24
    print(d);
25

26
    d = {2, 4, 5, 6};
27
    print(d);
28

29
    std::deque<int> d1(10, 0);    // ten 0s in the deque
30
    print(d1);
31

32
    // We use deques for operations at the front and the back, but they also
33
    // allow random access to the elements in constant time.
34
    d1[0] = 100;
35
    d1.at(1) = 200;
36
    print(d1);
37
}
38

39
// push_front(), pop_front(), push_back(), pop_back(), front(), back(), size()
40
void test2(void)
41
{
42
    std::cout << "\nTEST2" << std::endl;
43

44
    std::deque<int> d{0, 0, 0};
45
    print(d);
46

47
    d.push_back(5);
48
    d.push_back(8);
49
    print(d);
50

51
    d.push_front(2);
52
    d.push_front(1);
53
    print(d);
54

55
    std::cout << "Front: " << d.front() << std::endl;
56
    std::cout << "Back: " << d.back() << std::endl;
57
    std::cout << "Size: " << d.size() << std::endl;
58

59
    d.pop_back();
60
    d.pop_front();
61
    print(d);
62
}
63

64
// push_front(), push_back()
65
void test3(void)
66
{
67
    std::cout << "\nTEST3" << std::endl;
68

69
    // Insert all even numbers into the back of a deque and all odd numbers into
70
    // the front.
71
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
72
    std::deque<int> d;
73

74
    for (const auto &elem : v)
75
    {
76
        if (elem % 2 == 0)
77
        {
78
            d.push_back(elem);
79
        }
80
        else
81
        {
82
            d.push_front(elem);
83
        }
84
    }
85

86
    print(d);
87
}
88

89
// push_front(), push_back(), clear()
90
void test4(void)
91
{
92
    std::cout << "\nTEST4" << std::endl;
93

94
    // push_front() vs. push_back ordering.
95
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
96
    std::deque<int> d;
97

98
    for (const auto &elem : v)
99
    {
100
        d.push_front(elem);
101
    }
102
    print(d);
103
    d.clear();
104

105
    for (const auto &elem : v)
106
    {
107
        d.push_back(elem);
108
    }
109
    print(d);
110
}
111

112
// std::copy(), std::front_inserter(), std::back_inserter()
113
void test5(void)
114
{
115
    std::cout << "\nTEST5" << std::endl;
116

117
    // Same as test4(), but using std::copy.
118
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
119
    std::deque<int> d;
120

121
    
122
    // Same effect as the push_front().
123
    std::copy(v.begin(), v.end(), std::front_inserter(d));
124
    print(d);
125

126
    d.clear();
127

128
    // Same effect as the push_back().
129
    std::copy(v.begin(), v.end(), std::back_inserter(d));
130
    print(d);
131
}
132

133
int main(int argc, char *argv[])
134
{
135
    test1();
136
    test2();
137
    test3();
138
    test4();
139
    test5();
140
    return 0;
141
}

26
1

2
TEST1
3
[ 1 2 3 4 5 ]
4
[ 2 4 5 6 ]
5
[ 0 0 0 0 0 0 0 0 0 0 ]
6
[ 100 200 0 0 0 0 0 0 0 0 ]
7

8
TEST2
9
[ 0 0 0 ]
10
[ 0 0 0 5 8 ]
11
[ 1 2 0 0 0 5 8 ]
12
Front: 1
13
Back: 8
14
Size: 7
15
[ 2 0 0 0 5 ]
16

17
TEST3
18
[ 9 7 5 3 1 2 4 6 8 10 ]
19

20
TEST4
21
[ 10 9 8 7 6 5 4 3 2 1 ]
22
[ 1 2 3 4 5 6 7 8 9 10 ]
23

24
TEST5
25
[ 10 9 8 7 6 5 4 3 2 1 ]
26
[ 1 2 3 4 5 6 7 8 9 10 ]