Standard Template Library (STL)
std::deque
Double-ended queue with O(1) push/pop at both ends and random access
Interview: When you need efficient front and back operations — the underlying container for std::stack and std::queue by default
std::deque
std::deque (double-ended queue) stores elements in a series of fixed-size chunks, with an index map. This design gives O(1) amortized insertion at both the front and back (unlike vector which is O(n) at the front), and O(1) random access via subscript. The trade-off is slightly higher constant overhead compared to vector.
deque vs vector
Vector stores all elements in one contiguous block — perfect cache locality, but front insertion requires shifting everything O(n). Deque uses chunked storage — front and back insertions are O(1), but cache performance is slightly worse (elements may not be fully contiguous). Use deque when you need frequent front insertions or a sliding window over a data stream.
Iterator Invalidation
Inserting at the front or back invalidates all iterators but not references/pointers to existing elements. Inserting in the middle invalidates all iterators and references. Different from vector where only insertions past a reallocation invalidate.
Interview Corner
Q: Why is std::deque the default container for std::stack and std::queue?
A: std::stack and std::queue are container adaptors — they use an underlying container. deque is the default because it efficiently supports both push_back and pop_front (queue) or push_back and pop_back (stack). Vector could be used for stack (it supports push_back/pop_back efficiently) but not for queue (pop_front is O(n) for vector).
Common Pitfalls
- Assuming contiguous storage: Unlike vector, deque elements are not guaranteed contiguous. Do not pass
deque.data()to C APIs expecting a contiguous array. - Iterator invalidation on front/back insert: Iterators are invalidated on any insertion at front or back — don't cache iterators across mutations.
Best Practices
- Use deque when you need efficient push_front/pop_front alongside push_back/pop_back (e.g., BFS queue, sliding window algorithms).
- Prefer vector for most use cases — its contiguous storage and simpler iterator invalidation rules make it easier to reason about.