std::deque in C++: what it is and when to use it

std::deque, the double-ended queue from the header <deque>, is a sequence container that adds and removes elements at both the front and the back in constant time, and reaches any element by index like a vector. Its elements are not in one contiguous block, so a push at either end never moves the elements already there.

The smallest program: a line of people at a desk, where Ana joins at the front and Dee at the back.

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> line{"Ben", "Cy"};
    line.push_front("Ana");                 // Ana Ben Cy
    line.push_back("Dee");                  // Ana Ben Cy Dee

    std::cout << "front: " << line.front() << '\n';    // Ana
    std::cout << "back:  " << line.back() << '\n';     // Dee
    std::cout << "[1]:   " << line[1] << '\n';         // Ben
    std::cout << "size:  " << line.size() << '\n';     // 4

    line.pop_front();                       // Ana is served
    for (const std::string& name : line)
        std::cout << name << '\n';          // Ben, Cy, Dee
}

It printed:

front: Ana
back:  Dee
[1]:   Ben
size:  4
Ben
Cy
Dee

The samples are C++17, built with MSVC 19.44, Clang 19.1 (MSVC STL), GCC 16.2 and Clang 23.1 (libc++), and all four printed the same unless a sentence says otherwise. Nothing on this page needs a newer standard; Since When lists what each one added.

How do you use a std::deque?

Add with push_front() and push_back(), remove with pop_front() and pop_back(), and read with front(), back(), [] or at(); size() counts the elements and empty() says whether there are none. The traps are in indexing and in an empty deque:

• at(i) checks, and throws std::out_of_range when i is not less than size().
• [] is not required to check: an index past the end is undefined behavior, which means the standard sets no requirement on what happens; built without optimization, GCC 16.2’s library stopped the program with Assertion '__n < this->size()' failed., while Clang with libc++ read past the end and went on.
• front(), back() and a pop on an empty deque are undefined behavior too, so test empty() first.

std::cout << line[2] << '\n';           // Cy: [] need not check
std::cout << line.at(3) << '\n';        // Dee: at() checks

try {
    std::cout << line.at(10) << '\n';   // only 4 people
} catch (const std::out_of_range&) {
    std::cout << "no one at position 10\n";
}

while (!line.empty()) {                 // test before every pop
    std::cout << "serving " << line.front() << '\n';
    line.pop_front();
}
std::cout << "size now: " << line.size() << '\n';  // 0

On a line of Ana, Ben, Cy and Dee, all four printed Cy, Dee and no one at position 10, served the four in order and ended on size now: 0.

How is a deque stored?

In separate blocks. Typical implementations keep the elements in a series of fixed-size arrays, each allocated on its own, plus a small index of those blocks, instead of one contiguous array.

A push at either end fills a free slot in the first or last block, or adds a block, and the standard promises the result: pointers and references to the elements already there stay valid. A pointer to Ben, taken before 2,000 pushes:

std::cout << std::boolalpha;

std::deque<std::string> line{"Ben", "Cy"};
const std::string* first = &line[0];    // points at Ben

for (int i = 0; i < 1000; ++i)
    line.push_back("Guest");            // 1,000 at the back
for (int i = 0; i < 1000; ++i)
    line.push_front("Guest");           // 1,000 at the front

// Ben is now at index 1000
std::cout << (*first == "Ben") << '\n';         // true
std::cout << (&line[1000] == first) << '\n';    // true: not moved

On all three standard libraries the pointer still read Ben, at the same address as line[1000]. A std::vector filled to its capacity and given one more push_back moved its first element to a new block on all three.

The cost of the blocks: a deque has no data(), capacity() or reserve(), so you cannot hand it to a function that takes a pointer and a length.

std::string* first = line.data();   // error: a deque has no data()

Clang with libc++ said:

error: no member named 'data' in 'std::deque<std::string>'

reserve() and capacity() were rejected the same way by all four compilers.

std::deque vs std::vector: which should you use?

Use a std::vector by default, and a deque when you add or remove elements at the front.

Adding at the front is what decides. Putting 1,000 elements at the front, the deque moved none of the elements already inside, on all three libraries; a vector, adding each with insert() at begin(), moved elements already inside 499,500 times, because every insert at the front shifts all of them. For how a vector grows and what its growth invalidates, see std::vector size, capacity and reallocation.

Deque vs queue: what is the difference?

std::deque is a container you can use from both ends, index and loop over. std::queue is a container adaptor, a thin wrapper around a container that lets you push only at the back and pop only at the front, and by default that container is a std::deque. std::stack uses one too:

static_assert(std::is_same_v<std::queue<int>::container_type,
                             std::deque<int>>);
static_assert(std::is_same_v<std::stack<int>::container_type,
                             std::deque<int>>);
// ...
std::queue<int> desk;
std::deque<int> line;
for (int ticket : {1, 2, 3}) {
    desk.push(ticket);                  // queue: in at the back
    line.push_back(ticket);             // deque: the same, by name
}
desk.pop();                             // out at the front
line.pop_front();

Both static_asserts passed on all three libraries, and the two containers ended the same: 2 at the front, 3 at the back.

Use a C++ queue when first in, first out is all you need: the type says so and allows nothing else. Use the deque when you also need the other end, an index or a loop over the elements. A C++ stack is the same choice for last in, first out.

What do insert and erase cost, and what do they invalidate?

In the middle, linear time, as in a vector: elements shift to open or close the gap. Here print writes the names on one line:

line.insert(line.begin() + 2, "Bo");    // before Cy
print(line);                            // Ana Ben Bo Cy Dee

line.erase(line.begin() + 1);           // Ben leaves
print(line);                            // Ana Bo Cy Dee

All four printed those two lines. Changes can also invalidate iterators, the position markers begin() hands out, and pointers and references to elements; reading through one afterwards is undefined behavior. The rules from the standard ([deque]):

To hold on to an element across pushes, keep a pointer or a reference, not an iterator. An index stays right across push_back but not push_front, which shifts every position: Ben went from index 0 to index 1000 above.

When should you use a deque?

When items arrive at one end and leave from the other while you still read all of them: a sliding window that keeps the last few, or a work list fed at both ends. The last three temperature readings and their average:

std::cout << std::fixed << std::setprecision(1);

std::deque<int> window;                 // the last 3 readings
for (int reading : {18, 21, 19, 24, 22}) {
    window.push_back(reading);
    if (window.size() > 3)
        window.pop_front();             // drop the oldest

    double sum = 0;
    for (int r : window) {
        std::cout << r << ' ';
        sum += r;
    }
    std::cout << "-> " << sum / window.size() << '\n';
}

Once the fourth reading came in, the oldest left: all four printed 18 21 19 -> 19.3, then 21 19 24 -> 21.3. A std::queue would not do here, because the average loops over the elements.

Skip the deque when you need the elements in one block of memory, or when you mostly append and index: that is a vector’s work.

Which container: deque, vector, queue or list?

The other containers and the rest of the library are in Standard library.