STL Containers Cheatsheet

Complexity table

Container	Access	Search	Insert	Erase	Ordered?	Notes
vector	$O(1)$	$O(n)$	$O(1)$ am. at end	$O(n)$	—	contiguous, cache-friendly
deque	$O(1)$	$O(n)$	$O(1)$ at both ends	$O(n)$	—	chunked; slower than vector
list	$O(n)$	$O(n)$	$O(1)$ at an iterator	$O(1)$	—	rarely worth it
set / map	—	$O(\log n)$	$O(\log n)$	$O(\log n)$	yes	red-black tree
multiset / multimap	—	$O(\log n)$	$O(\log n)$	$O(\log n)$	yes	duplicates allowed
unordered_set / _map	—	$O(1)$ avg	$O(1)$ avg	$O(1)$ avg	no	$O(n)$ worst; hackable
priority_queue	$O(1)$ top	—	$O(\log n)$	$O(\log n)$ pop	—	binary heap
array	$O(1)$	$O(n)$	—	—	—	fixed size, stack allocated
bitset	$O(1)$	$O(n/64)$	—	—	—	1 bit per element
PBDS tree	—	$O(\log n)$	$O(\log n)$	$O(\log n)$	yes	+ order statistics

Algorithms worth memorising

sort(a.begin(), a.end());
sort(a.begin(), a.end(), greater<int>());
sort(a.begin(), a.end(), [](const P& x, const P& y){ return x.second < y.second; });
stable_sort(a.begin(), a.end());                        // preserves ties
 
reverse(a.begin(), a.end());
rotate(a.begin(), a.begin() + k, a.end());              // left rotate by k
 
lower_bound(a.begin(), a.end(), x);                     // first >= x
upper_bound(a.begin(), a.end(), x);                     // first > x
binary_search(a.begin(), a.end(), x);                   // bool
equal_range(a.begin(), a.end(), x);                     // {lower, upper}
 
a.erase(unique(a.begin(), a.end()), a.end());           // dedupe a SORTED range
nth_element(a.begin(), a.begin() + k, a.end());         // O(n) k-th smallest
partial_sort(a.begin(), a.begin() + k, a.end());        // smallest k, sorted
 
next_permutation(a.begin(), a.end());                   // all permutations of a SORTED array
prev_permutation(a.begin(), a.end());
 
accumulate(a.begin(), a.end(), 0LL);                    // note the 0LL
iota(a.begin(), a.end(), 0);                            // fill with 0,1,2,...
count(a.begin(), a.end(), x);
max_element(a.begin(), a.end());                        // returns an ITERATOR
min_element(a.begin(), a.end());
minmax_element(a.begin(), a.end());
__gcd(a, b);

The classic traps

Six bugs everyone hits

1. accumulate(a.begin(), a.end(), 0) sums into an int and overflows. Use 0LL.
2. s.lower_bound(x) vs std::lower_bound(s.begin(), s.end(), x) — for set/map, the free function is $O(n)$. Always use the member function.
3. multiset.erase(value) removes all copies. Use erase(find(value)) for one.
4. Iterator invalidation. vector invalidates everything on reallocation; set/map invalidate only the erased element; deque invalidates iterators on any insertion.
5. unordered_map is hackable. The default hash<long long> is the identity, so an adversary can force $O(n)$ collisions. Use a randomised custom hash, or gp_hash_table, or just a sorted vector + binary search.
6. unique does not remove duplicates — it moves them to the end and returns the new logical end. You must erase the tail, and the range must be sorted first.

Anti-hash protection

struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};
unordered_map<long long, int, Hash> mp;
mp.reserve(1 << 20);
mp.max_load_factor(0.25);

reserve plus a low load factor typically doubles the speed on top of fixing the security issue.

Choosing

Need	Container
Sequence, indexed access	vector
Push/pop at both ends	deque
Ordered, unique, with predecessor/successor	set
Ordered with duplicates	multiset
Fast lookup, order irrelevant	unordered_map (with a custom hash) or gp_hash_table
Always need the minimum	priority_queue
$k$-th smallest / rank	PBDS `tree` or a BIT
Boolean array, huge, with bulk ops	bitset
Insert/erase in the middle with queries	implicit treap

vector<bool> is not a container of bool

It is a bit-packed specialisation: 8× smaller, but operator[] returns a proxy, not a reference, and you cannot take a pointer to an element. Use vector<char> when you want a real array of booleans, and bitset when you want the bit tricks.

See also: General Data Structures · Ordered Set / PBDS · Common Pitfalls