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.
#include <deque> std::deque<int> d = {2, 3}; d.push_front(1); d.push_back(4); // 1 2 3 4
Try it
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.
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
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_backandoperator[]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: usedequewhen 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:dequeoffers 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>andstd::stack<T>use it by default;std::priority_queuedefaults tovector. - Algorithms work as for any random-access container (
std::sort,std::find, ...).