C++ Containers Index

1 minute read

Published: July 18, 2026

This is the central index for the C++ containers series. The goal is to keep the overview short and link to focused notes for each container family.

Core Sequence Containers

Need	Container
Dynamic array, index access	`vector`
Text manipulation	`string`
Key-value lookup, sorted keys	`map`
Key-value lookup, average `O(1)`	`unordered_map`
Unique values, sorted order	`set`
Sorted values with duplicates	`multiset`
Unique values, average `O(1)`	`unordered_set`
Stable iterators, node movement	`list`
FIFO processing	`queue`
LIFO processing	`stack`
Max/min element access	`priority_queue`
Push/pop from both ends	`deque`

Container	Access	Insert	Delete	Lookup
`vector`	`O(1)` by index	`O(1)` end, `O(n)` middle	`O(1)` end, `O(n)` middle	`O(n)`
`string`	`O(1)` by index	`O(1)` end, `O(n)` middle	`O(1)` end, `O(n)` middle	`O(n)`
`map`	-	`O(log n)`	`O(log n)`	`O(log n)`
`unordered_map`	-	`O(1)` average	`O(1)` average	`O(1)` average
`set`	-	`O(log n)`	`O(log n)`	`O(log n)`
`multiset`	-	`O(log n)`	`O(log n)`	`O(log n)`
`unordered_set`	-	`O(1)` average	`O(1)` average	`O(1)` average
`list`	`O(n)` by traversal	`O(1)` with iterator	`O(1)` with iterator	`O(n)`
`queue`	front/back only	`O(1)`	`O(1)`	-
`stack`	top only	`O(1)`	`O(1)`	-
`priority_queue`	top only	`O(log n)`	`O(log n)`	-
`deque`	`O(1)` by index	`O(1)` ends	`O(1)` ends	`O(n)`

Use vector when index access and traversal are central.
Use unordered_map or unordered_set when fast lookup is central and order does not matter.
Use map, set, or multiset when sorted order or range queries matter.
Use queue for BFS and stack for iterative DFS or nested parsing.
Use priority_queue for repeated best/min/max extraction.
Use deque for sliding-window and monotonic-queue patterns.
Use list only when stable iterators or node movement matter.
Be careful: map[key] and unordered_map[key] insert default values when the key is missing.
Be careful: vector reallocation invalidates existing pointers, references, and iterators.