The Standard Template Library is three ideas that plug together: containers hold data, iterators walk it, algorithms process it — all generic, all zero-overhead.
Container → Iterators begin()/end() → Algorithm
#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
int main() {
std::vector<int> v{4, 1, 3};
std::list<int> l{4, 1, 3};
// The same algorithm works on any container through iterators:
std::cout << *std::max_element(v.begin(), v.end()) << ' '
<< *std::max_element(l.begin(), l.end()) << '\n';
std::cout << std::count(v.begin(), v.end(), 3) << '\n';
}4 4
1Container families
| Family | Containers | Organised by |
|---|---|---|
| Sequence | vector, deque, list, forward_list, array | Position (the order you insert) |
| Ordered associative | set, multiset, map, multimap | Sorted keys (red-black tree) |
| Unordered associative | unordered_set/_multiset, unordered_map/_multimap | Hash of the key |
| Adaptors | stack, queue, priority_queue | A restricted interface over another container |
| Views (non-owning) | string_view, span, ranges views | Refer to someone else's data |
Complexity cheat sheet
| Container | Access | Search | Insert/erase at end | Insert/erase in middle / front |
|---|---|---|---|---|
vector | O(1) random | O(n) | O(1) amortised | O(n) |
deque | O(1) random | O(n) | O(1) | O(1) at front, O(n) middle |
list | O(n) | O(n) | O(1) | O(1) given an iterator |
set / map | — | O(log n) | O(log n) | O(log n) |
unordered_set / unordered_map | — | O(1) avg, O(n) worst | O(1) avg | O(1) avg |
priority_queue | O(1) top | — | push/pop O(log n) | — |
Choosing a container
Default
std::vector— contiguous, cache-friendly, fastest for most workloads, even with some middle inserts.Need lookup by key?
std::unordered_map/unordered_setfor speed;std::map/setwhen you need sorted order or range queries (lower_bound).Push/pop at both ends?
std::deque.LIFO / FIFO / “always give me the max”?
std::stack/std::queue/std::priority_queue.Many inserts/erases in the middle with stable iterators?
std::list— rarely the right answer in practice.
Why is std::vector usually faster than std::list even for insertions?