deque, list, queue, stack, priority_queue

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.

#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.

#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.

#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).

#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).

#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.

#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

† 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

1. Default to vector. It's cache-efficient and simple. Only switch if profiling shows the problem.

2. Use deque for double-ended workloads (BFS, sliding windows, producer-consumer). Avoid vector + deque micro-optimization when vector suffices.

3. Use list only if you need stable iterators under insertion. Measure against vector; often vector is faster in practice even with occasional reallocations.

4. Prefer stack/queue adaptors over bare containers. They clarify intent and prevent accidental misuse (e.g., random access on a queue).

5. For priority_queue, define operator< correctly. Min-heap: return a > b (counterintuitive but standard).

6. Reserve capacity when size is known. vec.reserve(n) prevents reallocation; deque grows in chunks anyway.

7. 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).

See Also

• std::vector — default choice for most sequences
• std::array — fixed-size, stack-allocated
• std::set / std::map — ordered associative containers
• Algorithms: std::sort, std::make_heap, std::push_heap, std::pop_heap