The container deque

The characteristics of the container deque

Deque stands from (Double Ended QUEue). The container std::deque is similar to std::vector, except that we can also insert elements at its beginning, using its method push_front.

Also, unlike std::vector, there is not guarantee that the elements of a std::deque are stored, in memory, next to another. While the class std::vector use a single memory space that is reallocated when needed, the container std::deque may store its elements in multiple memory spaces. This has the advantage of making the dynamic growth (in size) of std::deque containers less expensive than with vectors (Unless the storage of the vector is reserved using the method reserve or resize). However, for that reason, we should never iterate through a container of type std::deque using pointers. We must use iterators.

The class std::deque possesses all the methods of the container std::vector, except for capacity and reserve. Additionally, it have the methods push_front (Like push_back, but inserts the element at the beginning), pop_front (Like pop_back, but removes the first element) and emplace_front (Like emplace_back, but constructs the element at the beginning of the container).

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <deque> #include <iostream> int main() { std::deque<int> deque; for(unsigned c = 0; c < 10; c++) deque.push_back(c); for(unsigned c = 1; c < 10; c++) deque.push_front(c); for(unsigned c = 0; c < deque.size(); c++) std::cout << deque[c] << ' '; std::cout << '\n'; return 0; }

Iterators

An example, using iterators:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <deque> #include <iostream> int main() { std::deque<int> deque; for(unsigned c = 0; c < 10; c++) deque.push_front(c); // We can NOT do the following: /* int *ptr = &deque[0]; while(ptr != &deque[9]) { std::cout << *ptr << std::endl; ptr++; } */ std::deque<int>::iterator it = deque.begin(); while(it != deque.end()) { std::cout << *it << ' '; it++; } std::cout << '\n'; return 0; }