What is deque, list, queue, stack, priority_queue in C++?

"Sequential containers and adaptors: deque for double-ended operations, list for stable iterators, queue/stack/priority_queue adaptors. Choose based on insertion pattern and iterator requirements."

Which C++ standard introduced deque, list, queue, stack, priority_queue?

deque, list, queue, stack, priority_queue was introduced in C++98.

What is the difficulty level of deque, list, queue, stack, priority_queue?

deque, list, queue, stack, priority_queue is considered Intermediate-level C++ material.

deque, list, queue, stack, priority_queue

Sequential Containerssince C++98

Containers optimized for different access patterns: deque for double-ended operations, list for stable iterators under insertion, and adaptors (queue, stack, priority_queue) that wrap an underlying container to provide specific interfaces.

Overview

When std::vector doesn't fit your access pattern, reach for these sequential containers. Each trades off something — random access, iterator stability, cache locality, or memory overhead — for specific strengths.

The big picture:

deque — Fast push/pop at both ends; chunked layout avoids full reallocation on growth
list / forward_list — Stable iterators; insert/erase anywhere in O(1) with an iterator; doubly vs singly linked
queue / stack — Lightweight adaptors imposing FIFO/LIFO semantics over deque/vector
priority_queue — Implicit heap; O(log n) push/pop; always-sorted top element

Container adaptors (C++98) do not own memory directly — they wrap an underlying container and expose a constrained interface. This lets you choose the backing container: std::stack<int, std::vector<int>> uses vector instead of the default deque.

std::deque

Double-ended queue: contiguous access at both ends without the reallocation penalty of vector::push_front. Internally chunked into fixed-size blocks; growth doesn't invalidate existing references.

cpp

Godbolt

#include <deque>

std::deque<int> dq = {2, 3, 4};
dq.push_front(1);      // O(1) amortized
dq.push_back(5);       // O(1) amortized
dq.pop_front();        // O(1)
dq.pop_back();         // O(1)

int x = dq[0];         // O(1) random access
dq.insert(dq.begin() + 1, 99);  // O(n) — linear in distance to nearer end
dq.erase(dq.begin());           // O(n)

// Iterator invalidation
auto it = dq.begin();
dq.push_back(100);     // safe — doesn't invalidate it
dq.push_front(0);      // safe — doesn't invalidate it
dq.insert(it, 50);     // invalidates iterators at/after it

When to use: BFS queues, sliding windows, any producer-consumer pattern where you add to one end and remove from the other. Superior to vector for push_front.

std::list

Doubly-linked list: O(1) insert/erase anywhere given an iterator. No random access. Critical property: iterators are stable — insertion/erasure never invalidates other iterators or references.

cpp

Godbolt

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};

// Iterator stability demonstration
auto it = std::ranges::find(lst, 3);
auto other_it = std::next(it);
lst.insert(it, 99);    // insert before 3; it and other_it remain valid
lst.erase(it);         // erase 3; other_it still valid

// List-specific operations (not in vector/deque)
lst.splice(lst.begin(), other_list);  // O(1) move elements from other_list
lst.sort();            // merge sort — O(n log n); stable
lst.unique();          // remove consecutive equal elements
lst.merge(other_list); // merge two sorted lists — O(n) if already sorted
lst.remove(99);        // erase all elements == 99; O(n)
lst.reverse();         // in-place — O(n)

// Cache-unfriendly iteration
for (const auto& elem : lst) {
  // Each dereference jumps to a different memory location
}

Iterator invalidation: Only the erased element's iterator is invalidated. Insert, erase elsewhere, move — all preserve other iterators.

When to use: Workloads requiring frequent insertion/deletion in the middle (not just ends) with stable iterator requirements. Graph algorithms, LRU caches (list + unordered_map). In practice, vector with occasional reallocation often beats list due to cache locality — measure.

std::forward_list

Singly-linked list. Half the pointer overhead of list (one prev/next pointer per node vs two). Only forward iteration.

cpp

Godbolt

#include <forward_list>

std::forward_list<int> fl = {1, 2, 3};
fl.push_front(0);
fl.insert_after(fl.begin(), 99);  // insert *after* iterator, not before
fl.erase_after(fl.begin());       // erase the element after iterator

// Stable iterators under insert_after / erase_after
for (auto it = fl.begin(); it != fl.end(); /* manual advance */) {
  if (*it == 2) {
    it = fl.erase_after(std::prev(it));  // erase and advance
  } else {
    ++it;
  }
}

// No size() — O(n) to compute!
// Splicing
std::forward_list<int> other = {10, 20};
fl.splice_after(fl.begin(), other);  // move all of other after begin

Rarely used — singly-linked list overhead seldom justifies the saved pointer. Use if memory is extremely constrained and you never need backward traversal.

std::queue

FIFO adaptor (backed by deque by default; can use list or vector).

cpp

Godbolt

#include <queue>

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);

int front_val = q.front();  // oldest element
int back_val = q.back();    // newest element
q.pop();                    // remove oldest
bool is_empty = q.empty();

// Custom underlying container
std::queue<int, std::vector<int>> vec_queue;
std::queue<int, std::list<int>> list_queue;

// No iterators — intentional. Queue enforces FIFO; don't peek in the middle

Default backing: deque balances memory efficiency and push/pop cost. Use vector if you call reserve() upfront; use list only if you're already paying the pointer cost elsewhere.

std::stack

LIFO adaptor (backed by deque by default; can use vector or list).

cpp

Godbolt

#include <stack>

std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);

int top = s.top();  // most recently pushed
s.pop();            // remove top
size_t sz = s.size();

// Custom backing — vector is often better (cache friendly)
std::stack<int, std::vector<int>> vec_stack;

// Practical: expression evaluation
struct Op { char op; int precedence; };
std::stack<Op, std::vector<Op>> op_stack;
op_stack.push({'+', 1});

std::priority_queue

Max-heap adaptor: top() always yields the largest element. Backed by vector by default.

cpp

Godbolt

#include <queue>

std::priority_queue<int> pq;  // max-heap
pq.push(3);
pq.push(1);
pq.push(4);

int max_elem = pq.top();  // 4 (largest)
pq.pop();                 // remove max
pq.top();                 // 3 (now largest)

// Min-heap — invert comparator (C++98)
auto cmp = [](int a, int b) { return a > b; };  // greater instead of less
std::priority_queue<int, std::vector<int>, decltype(cmp)> min_pq(cmp);

// Custom type
struct Task {
  int id;
  int priority;
  bool operator<(const Task& other) const {
    return priority < other.priority;  // reversed for max-heap
  }
};
std::priority_queue<Task> task_queue;
task_queue.push({1, 5});
task_queue.push({2, 3});
task_queue.top();  // Task with priority 5

// Direct heap construction — O(n) heapify
std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6};
std::priority_queue<int> pq(data.begin(), data.end());  // O(n)

Performance Characteristics

Operation	vector	deque	list	forward_list
push_back	O(1) amortized	O(1) amortized	O(1)	O(1)
pop_back	O(1)	O(1)	O(1)	O(n)
push_front	O(n)	O(1) amortized	O(1)	O(1)
pop_front	O(n)	O(1)	O(1)	O(n)
insert middle	O(n)	O(n)	O(1)	O(1)
erase middle	O(n)	O(n)	O(1)	O(n)†
random access	O(1)	O(1)	—	—
memory overhead	minimal	~3 ptrs per node block	2 ptrs/node	1 ptr/node
cache-friendly	✓	mostly	✗	✗

† forward_list erase_after is O(1), but forward iteration to find the element is O(n).

Iterator Invalidation Rules

deque:

push_back, push_front → may invalidate all iterators, but never invalidates references
insert/erase → invalidates all iterators; invalidates references only in erased range

list / forward_list:

insert, erase, splice → iterators and references stable everywhere except the erased element itself
Operations never invalidate anything unrelated to them

vector:

push_back → may invalidate all iterators if reallocation; references safe
insert/erase → invalidates all iterators at/after point of change; references in erased range invalidated

Best Practices

Default to vector. It's cache-efficient and simple. Only switch if profiling shows the problem.
Use deque for double-ended workloads (BFS, sliding windows, producer-consumer). Avoid vector + deque micro-optimization when vector suffices.
Use list only if you need stable iterators under insertion. Measure against vector; often vector is faster in practice even with occasional reallocations.
Prefer stack/queue adaptors over bare containers. They clarify intent and prevent accidental misuse (e.g., random access on a queue).
For priority_queue, define operator< correctly. Min-heap: return a > b (counterintuitive but standard).
Reserve capacity when size is known. vec.reserve(n) prevents reallocation; deque grows in chunks anyway.
Avoid modifying containers while iterating (except via erase/insert, which return updated iterators in C++11+).

Common Pitfalls

Expecting list to always be faster: Cache misses dominate; profile before choosing list over vector.
Forgetting that queue/stack have no iterators: They intentionally hide random access.
Invalidating iterators silently: Insert/erase in vector invalidates all subsequent iterators; in list, only the erased element.
Using priority_queue with wrong comparator: A lambda comparing a < b gives a max-heap; swap to > for min-heap.
Removing from forward_list incorrectly: Must call erase_after on the previous node, not the node itself.
Confusing splice with insert: splice moves nodes from another list in O(1); insert copies elements from any range in O(n).

std::list splice and merge

splice is O(1) and moves nodes without copying — it is list's killer feature. No element is constructed or destroyed; ownership transfers at the pointer level. merge assumes both lists are sorted and produces a single sorted list in O(n).

cpp

Godbolt

#include <list>

std::list<int> a = {1, 3, 5};
std::list<int> b = {2, 4, 6};

// splice: move all of b into a before position a.begin()
a.splice(a.begin(), b);   // a = {2, 4, 6, 1, 3, 5}, b = {}

// splice a single element
std::list<int> src = {10, 20, 30};
std::list<int> dst = {1, 2, 3};
auto it = std::next(src.begin());   // points at 20
dst.splice(dst.end(), src, it);     // dst = {1, 2, 3, 20}, src = {10, 30}

// splice a range
std::list<int> x = {1, 2, 3, 4, 5};
std::list<int> y = {};
auto first = std::next(x.begin());  // points at 2
auto last  = std::prev(x.end());    // points at 5 (exclusive range is [2,4])
y.splice(y.begin(), x, first, last);  // y = {2, 3, 4}, x = {1, 5}

// merge two sorted lists — O(n), stable
std::list<int> evens = {2, 4, 6};
std::list<int> odds  = {1, 3, 5};
evens.merge(odds);  // evens = {1, 2, 3, 4, 5, 6}, odds = {}

// merge with custom comparator (C++11)
std::list<std::string> words1 = {"apple", "cherry"};
std::list<std::string> words2 = {"banana", "date"};
words1.merge(words2, [](const std::string& a, const std::string& b) {
    return a < b;
});  // words1 = {"apple", "banana", "cherry", "date"}

Caveat: Both lists must be sorted before calling merge, or the result is undefined. After splice the source range/element is removed from the source list — its iterators remain valid but now point into the destination.

std::deque memory layout

deque stores elements in a map of fixed-size chunks, so growth never moves existing elements. Each chunk holds a platform-chosen number of elements (often 512 bytes per chunk). A central "map" array holds pointers to these chunks; only the map may reallocate, not the chunks themselves.

cpp

Godbolt

#include <deque>
#include <iostream>

std::deque<int> dq;

// References are stable across push_front / push_back
dq.push_back(1);
int& ref = dq[0];   // stable reference
dq.push_back(2);
dq.push_front(0);
// ref still valid — no reallocation of the chunk holding element 0

std::cout << ref;   // still 1 — chunk was not moved

// Memory layout insight: random access is O(1) but requires two pointer
// hops: map[chunk_index][offset_within_chunk]
// This is why deque random access is slightly slower than vector.

// push_front / push_back are O(1) amortized:
// - New elements go into the first/last chunk if space remains
// - A new chunk is allocated only when the boundary chunk is full
// - The map is reallocated (rarely) when it runs out of chunk-pointer slots

// insert/erase in the middle shifts elements toward the nearer end — O(n)
dq.insert(dq.begin() + 2, 99);  // shifts elements between pos and nearer end

Key implication: deque invalidates iterators (not references) on push_front/push_back because the map index might change. References and pointers to existing elements remain valid. This subtlety bites when storing deque::iterator values across mutations.

std::queue and std::stack as container adaptors

Adaptors restrict the underlying container's interface to enforce a single usage contract. std::queue exposes only FIFO operations; std::stack exposes only LIFO. This prevents accidental misuse like random-access into a queue.

cpp

Godbolt

#include <queue>
#include <stack>
#include <vector>
#include <list>

// --- queue ---
// Default backing: deque
std::queue<int> q;
q.push(10); q.push(20); q.push(30);
q.front();  // 10 — oldest
q.back();   // 30 — newest
q.pop();    // removes front (10)

// Backed by list — useful if you already hold list nodes elsewhere
std::queue<int, std::list<int>> list_q;

// Backed by vector — only valid if you never need pop_front efficiently;
// vector lacks pop_front so this will not compile for std::queue.
// Use deque (default) or list for queue.

// --- stack ---
// Default backing: deque; vector is often better (cache-friendly + reserve)
std::stack<int, std::vector<int>> vs;
vs.push(1); vs.push(2); vs.push(3);
vs.top();   // 3 — most recently pushed
vs.pop();   // removes top

// Accessing the underlying container (non-portable trick via inheritance)
// Not recommended — use adaptors as black boxes.

// Practical pattern: DFS with explicit stack
std::stack<int> dfs_stack;
dfs_stack.push(root_node_id);
while (!dfs_stack.empty()) {
    int node = dfs_stack.top();
    dfs_stack.pop();
    // process node, push children...
}

std::vector cannot back std::queue because queue requires pop_front which vector does not provide. Use deque (default) or list. For stack, vector is usually the best choice because it is cache-friendly and supports reserve.

std::priority_queue with custom comparators

priority_queue is a max-heap by default; flipping the comparator gives a min-heap. The comparator follows the same convention as std::sort: return true if the left argument should come before the right in the sorted order — but because the heap pops the largest element, using std::greater inverts priority.

cpp

Godbolt

#include <queue>
#include <vector>
#include <functional>

// Max-heap (default): largest element on top
std::priority_queue<int> max_pq;
max_pq.push(5); max_pq.push(1); max_pq.push(9);
max_pq.top();  // 9

// Min-heap: std::greater<int> as comparator (C++11)
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(5); min_pq.push(1); min_pq.push(9);
min_pq.top();  // 1

// Lambda comparator (C++11)
auto cmp = [](const std::pair<int,int>& a, const std::pair<int,int>& b) {
    return a.second > b.second;  // min-heap on second element
};
std::priority_queue<
    std::pair<int,int>,
    std::vector<std::pair<int,int>>,
    decltype(cmp)
> pq(cmp);

pq.push({1, 10});
pq.push({2,  3});
pq.push({3,  7});
pq.top();  // {2, 3} — lowest .second value

// C++20: use std::greater<> (transparent) for heterogeneous comparison
std::priority_queue<int, std::vector<int>, std::greater<>> min_pq2;  // C++20

// O(n) construction from existing range
std::vector<int> data = {3, 1, 4, 1, 5, 9};
std::priority_queue<int> heap(data.begin(), data.end());  // O(n) heapify

Watch out: priority_queue has no update or decrease_key operation. If you need to change a priority after insertion (e.g., Dijkstra's algorithm), use the lazy-deletion trick: push a new entry and mark old entries as stale when popped.

Choosing between deque, list, and vector

The default answer is vector; switch only when a specific weakness shows up in profiling. Each container excels at a narrow set of operations and pays in others.

cpp

Godbolt

// Decision guide — not real compilable code, just pseudocode
//
//  Need:                            Use:
//  ─────────────────────────────────────────────────────────────
//  Sequential storage, random       std::vector
//  access, occasional push_back
//
//  Push/pop at BOTH ends, still     std::deque
//  want random access (O(1))
//
//  Frequent insert/erase in         std::list
//  the *middle*, stable iterators
//  mandatory
//
//  Very memory-constrained,         std::forward_list
//  only forward traversal needed
//
//  BFS queue (add back, remove      std::queue (wraps deque)
//  front, no middle access)
//
//  DFS / undo stack                 std::stack<T, std::vector<T>>
//
//  Always-sorted top element,       std::priority_queue
//  heap semantics

// Concrete example: BFS vs DFS
#include <queue>
#include <stack>
#include <vector>
#include <unordered_set>

void bfs(int start, auto& graph) {
    std::queue<int> frontier;           // FIFO — deque backed
    std::unordered_set<int> visited;
    frontier.push(start);
    while (!frontier.empty()) {
        int node = frontier.front(); frontier.pop();
        if (visited.count(node)) continue;
        visited.insert(node);
        for (int nb : graph[node]) frontier.push(nb);
    }
}

void dfs(int start, auto& graph) {
    std::stack<int, std::vector<int>> stk;  // LIFO — vector backed
    std::unordered_set<int> visited;
    stk.push(start);
    while (!stk.empty()) {
        int node = stk.top(); stk.pop();
        if (visited.count(node)) continue;
        visited.insert(node);
        for (int nb : graph[node]) stk.push(nb);
    }
}

Rule of thumb: list is rarely faster than vector in practice because pointer-chasing defeats the CPU cache. Benchmark with realistic data sizes — the breakeven point is usually much larger than intuition suggests.

std::forward_list (singly-linked)

forward_list trades backward traversal for a halved per-node pointer cost. It stores only one next pointer per node versus list's two. There is no size() member function — computing it is O(n), and the committee chose not to incur the cost implicitly.

cpp

Godbolt

#include <forward_list>    // C++11

std::forward_list<int> fl = {1, 2, 3, 4, 5};  // C++11

// Push and insert
fl.push_front(0);                       // O(1)
fl.insert_after(fl.begin(), 99);        // insert after first element

// Erase — must supply the PREVIOUS iterator
auto it = fl.before_begin();            // sentinel before first element
for (auto next = fl.begin(); next != fl.end(); ) {
    if (*next % 2 == 0) {
        next = fl.erase_after(it);      // erase even numbers
    } else {
        it = next++;
    }
}

// Splice
std::forward_list<int> other = {10, 20, 30};
fl.splice_after(fl.begin(), other);     // move all of other after begin()
// other is now empty

// Sort and unique (member functions, like list)
fl.sort();
fl.unique();

// remove_if (C++11) — in-place filter
fl.remove_if([](int x) { return x > 5; });

// Count elements (no size() member)
auto n = std::distance(fl.begin(), fl.end());  // O(n)

before_begin() is the secret weapon: it returns a sentinel iterator that represents the position before the first element, enabling insert_after and erase_after at the very front of the list without special-casing.

list vs forward_list: when to use each

Choose forward_list only when memory is the dominant constraint and backward traversal is never needed. For every other use case, list is easier to work with because it supports bidirectional iteration and insert/erase directly on the target position.

cpp

Godbolt

#include <list>
#include <forward_list>

// list: can erase the element you have an iterator to
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = std::ranges::find(lst, 3);   // C++20
lst.erase(it);                          // direct — O(1)

// forward_list: must have the PREVIOUS iterator to erase
std::forward_list<int> fl = {1, 2, 3, 4, 5};
auto prev_it = fl.before_begin();
for (auto cur = fl.begin(); cur != fl.end(); ++cur) {
    if (*cur == 3) {
        fl.erase_after(prev_it);        // O(1) but requires extra bookkeeping
        break;
    }
    prev_it = cur;
}

// list: bidirectional — can iterate in reverse
std::list<int> l2 = {1, 2, 3};
for (auto rit = l2.rbegin(); rit != l2.rend(); ++rit) {
    // reverse traversal is natural
}

// forward_list: no rbegin/rend
// std::forward_list<int> fl2 = {1,2,3};
// fl2.rbegin();  // ERROR — not supported

// Memory comparison (illustrative; actual sizes are implementation-defined)
// list node:          value + prev* + next*   (~24 bytes for int on 64-bit)
// forward_list node:  value + next*            (~16 bytes for int on 64-bit)
// Savings matter only with millions of small nodes.

// Summary decision table:
// Need reverse iteration?               -> list
// Need to erase by iterator directly?   -> list
// Tight memory, millions of nodes,
//   forward-only traversal sufficient?  -> forward_list
// Neither constraint is acute?          -> vector (seriously)

forward_list has no push_back or back() — appending requires traversing to the end first. If you find yourself appending frequently, switch to list or deque.