Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::deque class

Reference for std::deque: constant-time push and pop at both ends, random access, insertion costs, iterator invalidation rules and how it differs from vector.

std::deque<T> ("double-ended queue", pronounced "deck") is a sequence container that supports fast insertion and removal at both ends and random access by index. It is usually implemented as a collection of fixed-size blocks plus an index of the blocks, so growing it never moves existing elements: references to elements stay valid when you push at either end (iterators do not).

The price is that the elements are not contiguous in memory. There is no data(), no capacity() or reserve(), and iteration is somewhat slower than for a std::vector. It is the default underlying container of std::queue and std::stack.

C++
#include <deque>
std::deque<int> d = {2, 3};
d.push_front(1);
d.push_back(4);        // 1 2 3 4

Try it

C++ Both ends and random access

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ A sliding window and reference stability

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template <class T, class Allocator = std::allocator<T>>
class deque;

// Access
T& operator[](size_type i);   T& at(size_type i);   T& front();   T& back();

// Modifiers
void push_back(const T&);   void push_front(const T&);
void pop_back();            void pop_front();
template <class... A> reference emplace_back(A&&...);
template <class... A> reference emplace_front(A&&...);
iterator insert(const_iterator pos, const T& v);   iterator erase(const_iterator pos);

// Capacity
size_type size() const noexcept;   bool empty() const noexcept;
void resize(size_type n);   void shrink_to_fit();
Name Description
i Zero-based index; operator[] is not checked, at() is.
pos Iterator before which to insert, or the element to erase.
n New size for resize.

Returns: access functions return references; insert/erase return an iterator to the inserted or following element; emplace_back/emplace_front return a reference to the new element (C++17).

Errors / undefined behavior: at() throws std::out_of_range; operator[] out of range, front()/back() and pop_front()/pop_back() on an empty deque are undefined. Allocation can throw std::bad_alloc.

Usage notes

  • Complexity: push_front, push_back, pop_front, pop_back and operator[] are O(1); inserting or erasing in the middle is O(n) (the nearer end is shifted).
  • Invalidation: inserting at either end invalidates all iterators but not references or pointers to existing elements. Insertion or erasure in the middle invalidates everything. Erasing at an end only invalidates the erased elements (and end()). See iterator invalidation.
  • Not contiguous: you cannot pass d.data() to a C API. If you need contiguity and only append, use a vector.
  • No reserve/capacity: growth is handled in blocks; shrink_to_fit() is a non-binding request.
  • Versus vector: use deque when you need fast removal from the front (queues, sliding windows, BFS), or when stable references while growing matter. For everything else a vector is faster.
  • Versus list: deque offers random access and better cache behavior but no stable iterators on insertion.
  • Memory: an empty deque in libstdc++ already allocates a small map and one block, so thousands of small deques cost real memory.
  • As an adapter base: std::queue<T> and std::stack<T> use it by default; std::priority_queue defaults to vector.
  • Algorithms work as for any random-access container (std::sort, std::find, ...).