xi. Data Structure Catalog

The base list of data structures: what each stores, what every operation costs, how much memory it takes, and when to reach for it. Algorithms with their time and space are in 🐬 Complexity Cheat Sheet; the decision map “query pattern $\to$ structure” is in Containers, Hashing and Choosing a Structure.

Memory figures were measured on 64-bit libstdc++ (GCC) by counting operator new requests for $2^{20}$ elements; node-based containers pay another 8–16 bytes of malloc bookkeeping per node on top. Costs: $O(1{)}^{\ast }$ = amortized, $O(1{)}^{†}$ = expected.

Linear structures

Structure	Access $i$-th	Push / pop back	Push / pop front	Insert / erase middle	Search	Memory per int	Iterators stable?	Use when
static array, std::array	$O(1)$	—	—	$O(n)$	$O(n)$, $O(\log n)$ sorted	4 B	yes	size known at compile time; fastest
vector	$O(1)$	$O(1{)}^{\ast }$	$O(n)$	$O(n)$	$O(n)$ / $O(\log n)$	4 B (up to 8 B before shrinking: capacity doubles)	no (reallocation)	default container
deque	$O(1)$ (two indirections)	$O(1)$	$O(1)$	$O(n)$	$O(n)$	~4.2 B (512-byte blocks + map)	references yes at the ends, iterators no	both ends, or stable references while pushing
list (doubly linked)	$O(n)$	$O(1)$	$O(1)$	$O(1)$ with an iterator; splice $O(1)$	$O(n)$	24 B + malloc	yes	many erasures/splices at known positions (rare in contests)
forward_list	$O(n)$	—	$O(1)$	$O(1)$ after an iterator	$O(n)$	16 B + malloc	yes	memory-tight singly linked lists
index-based linked list (prv/nxt arrays)	$O(n)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$	8 B	indices never move	”delete element, find live neighbour” simulations; below
stack / queue (adapters on deque)	top / front only	$O(1)$	$O(1)$ (queue pop)	—	—	as deque	—	LIFO / FIFO; use vector as a stack for speed
ring buffer (circular array)	$O(1)$	$O(1)$	$O(1)$	$O(n)$	$O(n)$	4 B, fixed capacity	indices relative to head	BFS queues, sliding windows with a known bound; below
monotonic stack / deque	top / ends	$O(1{)}^{\ast }$	$O(1{)}^{\ast }$	—	—	4 B	—	next greater element, sliding window min/max: Monotonic Stack
min-stack, min-queue (two stacks)	—	$O(1)$ / $O(1{)}^{\ast }$	—	—	min in $O(1)$	8 B	—	queue with min/max/gcd of contents; below
bitset<N>	$O(1)$	—	—	—	word-parallel $O(N/64)$ ops	1 bit	—	boolean DP, sets over a small universe: Bitset
vector<bool>	$O(1)$ (bit proxy)	$O(1{)}^{\ast }$	—	$O(n)$	—	1 bit	no	large boolean arrays; not a real container of bool
string	$O(1)$	$O(1{)}^{\ast }$	$O(n)$	$O(n)$	find $O(nm)$ worst	1 B per char (15 chars inline: SSO)	no	text; hashing and automata in chapter 18

Associative structures

Structure	Insert / erase / find	Ordered queries (lower_bound, min, next)	$k$-th / rank	Memory per int key	Use when
sorted vector + binary search	$O(n)$ insert, $O(\log n)$ find	$O(\log n)$	$O(1)$	4 B	static set: build once, query many
set / map (red-black tree)	$O(\log n)$	$O(\log n)$	— ($O(n)$ distance)	40 B (map<int,int> 40 B, map<ll,ll> 48 B)	dynamic ordered set; default
multiset / multimap	$O(\log n)$	$O(\log n)$	—	40 B	duplicates; erase one copy with erase(find(x))
unordered_set / unordered_map (chaining)	$O(1{)}^{†}$, $O(n)$ worst	no	no	27 B (<int,int>), 35 B (<ll,ll>)	exact lookups; add a randomized hash against anti-hash tests
gp_hash_table (open addressing, pb_ds)	$O(1{)}^{†}$, faster in practice	no	no	~48 B at default load	hot lookups; PBDS
pb_ds tree (order statistics)	$O(\log n)$	$O(\log n)$	find_by_order / order_of_key $O(\log n)$	48 B	rank queries on a dynamic set
treap / implicit treap	$O(\log n{)}^{†}$	$O(\log n)$	$O(\log n)$	~24 B (arrays)	split/merge, sequence operations, reversals: Treaps
splay tree	$O(\log n{)}^{\ast }$	$O(\log n{)}^{\ast }$	$O(\log n{)}^{\ast }$	~16–24 B	link-cut trees, access locality
AVL tree	$O(\log n)$ worst	$O(\log n)$	with sizes	~24 B	strict height $\le 1.44{\log }_{2}n$; rarely hand-written
skip list	$O(\log n{)}^{†}$	$O(\log n{)}^{†}$	with widths	~2 pointers per key on average	simple concurrent-friendly ordered set; below
B-tree (order $t$)	$O({\log }_{t}n)$ node visits	yes	with counts	compact, $\ge t-1$ keys per node	external memory and cache-friendly ordered sets (databases, file systems)
trie	$O(L)$ per string	lexicographic order	with counts	one node per distinct prefix	prefixes, autocomplete, XOR queries: Trie, Binary Trie
radix tree (compressed trie)	$O(L)$	yes	with counts	one node per branching point	long strings with shared prefixes; suffix trees
64-ary bit tree (“fast set”)	$O({\log }_{64}U)$	next / prev $O({\log }_{64}U)$	—	$\approx U/63$ words	integer keys in $[0,U)$: Fast Set
van Emde Boas tree	$O(\log \log U)$	$O(\log \log U)$	—	$O(U)$	theory; the 64-ary tree is the practical version
Chtholly tree (interval map)	amortized by assignments	$O(\log n)$	—	one node per run	random “assign range” operations: Chtholly Tree

Priority structures

Structure	Push	Pop min	Decrease key	Meld	Notes
binary heap (priority_queue)	$O(\log n)$	$O(\log n)$	lazy deletion	$O(n)$	4 B per int; default
$d$-ary heap	$O({\log }_{d}n)$	$O(d{\log }_{d}n)$	$O({\log }_{d}n)$	$O(n)$	$d=4$ is often faster (cache)
leftist / skew heap	$O(\log n)$ (${}^{\ast }$ for skew)	$O(\log n)$	—	$O(\log n)$	mergeable heaps in a few lines
randomized meldable heap	$O(\log n{)}^{†}$	$O(\log n{)}^{†}$	—	$O(\log n{)}^{†}$	shortest mergeable heap code
pairing heap	$O(1)$	$O(\log n{)}^{\ast }$	$o(\log n{)}^{\ast }$	$O(1)$	fast in practice; pb_ds pairing_heap_tag
binomial heap	$O(1{)}^{\ast }$	$O(\log n)$	$O(\log n)$	$O(\log n)$	forest of binomial trees
Fibonacci heap	$O(1)$	$O(\log n{)}^{\ast }$	$O(1{)}^{\ast }$	$O(1)$	best bounds, poor constants; Heaps
radix heap	$O(1)$	$O(\log C{)}^{\ast }$	—	—	monotone integer keys (Dijkstra)
two heaps (median), heap with global add	$O(\log n)$	$O(\log n)$	—	—	running median, offset tricks

Range and tree structures (index into chapters 7, 8, 12)

Structure	Build	Query	Update	Memory	Note
prefix sums / difference array	$O(n)$	$O(1)$ range sum	$O(n)$ (offline: $O(1)$ range add)	$n$	Prefix Sums
sparse table	$O(n\log n)$	$O(1)$ idempotent (min, gcd)	static	$n\log n$	Sparse Table
Fenwick tree	$O(n)$	$O(\log n)$ prefix sums, $k$-th by descent	$O(\log n)$ point	$n$	Fenwick Tree
segment tree	$O(n)$	$O(\log n)$ any monoid	$O(\log n)$ point	$2n$–$4n$	Segment Tree
lazy segment tree	$O(n)$	$O(\log n)$	$O(\log n)$ range	$4n$	Lazy Propagation
dynamic / persistent segment tree	—	$O(\log U)$	$O(\log U)$ new nodes	$O(q\log U)$	Dynamic and Persistent Segment Trees
segment tree beats	$O(n)$	$O(\log n)$	chmin / chmax amortized $O({\log }^{2}n)$	$4n$	Segment Tree Beats
Li Chao tree	—	$O(\log C)$ min of lines	$O(\log C)$ add line	$O(\text{lines})$	Li Chao Tree
sqrt decomposition	$O(n)$	$O(\sqrt{n})$	$O(1)$–$O(\sqrt{n})$	$n$	anything with cheap block summaries
merge sort tree / wavelet tree	$O(n\log n)$	$O({\log }^{2}n)$ / $O(\log \sigma )$ $k$-th, rank	static	$n\log n$ / $n\log \sigma$ bits	8. Range Queries
DSU (union by size + path compression)	$O(n)$	find $O(\alpha (n){)}^{\ast }$	union $O(\alpha (n){)}^{\ast }$	$n$	DSU; with rollback $O(\log n)$
binary lifting / LCA	$O(n\log n)$	$O(\log n)$ ($O(1)$ with Euler tour + RMQ)	static	$n\log n$	LCA
heavy-light decomposition	$O(n)$	path query $O({\log }^{2}n)$	$O({\log }^{2}n)$	$n$	12. Trees
link-cut tree / Euler-tour tree	—	$O(\log n{)}^{\ast }$ path / subtree	link, cut $O(\log n{)}^{\ast }$	$n$	dynamic forests: Euler Tour Tree
centroid decomposition	$O(n\log n)$	path counting $O(\log n)$ per vertex	—	$n\log n$	12. Trees
KD-tree	$O(n\log n)$	2D orthogonal range $O(\sqrt{n}+k)$ worst case; nearest neighbour fast on typical data	insert with periodic rebuilding	$n$	KD-Tree
persistent array / treap / segment tree	—	$O(\log n)$ any version	$O(\log n)$ new nodes	$O(\log n)$ per update	Persistence

Four small structures worth having

// Doubly linked list over fixed indices 0..n-1 (sentinel n): O(1) erase and neighbour queries, no allocation.
struct IndexList {
    int n; vector<int> prv, nxt;
    IndexList(int n) : n(n), prv(n + 1), nxt(n + 1) {         // starts as 0, 1, ..., n-1
        for (int i = 0; i <= n; i++) prv[i] = (i + n) % (n + 1), nxt[i] = (i + 1) % (n + 1);
    }
    void erase(int x) { nxt[prv[x]] = nxt[x]; prv[nxt[x]] = prv[x]; }
    void insertAfter(int p, int x) { prv[x] = p; nxt[x] = nxt[p]; prv[nxt[p]] = x; nxt[p] = x; }   // p = n: front
    int front() const { return nxt[n]; }                        // n means "empty" / "end"
    int next(int x) const { return nxt[x]; }
    int prev(int x) const { return prv[x]; }
};
 
template<class T> struct RingBuffer {                           // fixed capacity (power of two), O(1) at both ends
    vector<T> a; int head = 0, len = 0, mask;
    RingBuffer(int capPow2) : a(capPow2), mask(capPow2 - 1) {}
    void push_back(const T& x) { a[(head + len++) & mask] = x; }
    void push_front(const T& x) { head = (head - 1) & mask; a[head] = x; len++; }
    T pop_front() { T x = a[head]; head = (head + 1) & mask; len--; return x; }
    T pop_back() { return a[(head + --len) & mask]; }
    T& operator[](int i) { return a[(head + i) & mask]; }
    int size() const { return len; }
};
 
struct MinQueue {                                               // queue with O(1) amortized min
    vector<pair<ll, ll>> in, out;                               // (value, min of this stack up to here)
    void push(ll x) { in.push_back({x, in.empty() ? x : min(x, in.back().second)}); }
    void pop() {
        if (out.empty()) while (!in.empty()) { ll x = in.back().first; in.pop_back(); out.push_back({x, out.empty() ? x : min(x, out.back().second)}); }
        out.pop_back();
    }
    ll getMin() const {
        if (in.empty()) return out.back().second;
        if (out.empty()) return in.back().second;
        return min(in.back().second, out.back().second);
    }
    int size() const { return sz(in) + sz(out); }
};
 
struct SkipList {                                               // ordered set of ints > INT_MIN, expected O(log n)
    static const int MAXL = 24;
    vector<int> key; vector<vector<int>> nxt; int lvl = 1; mt19937 rng{20240601};
    SkipList() { key.push_back(INT_MIN); nxt.push_back(vector<int>(MAXL, -1)); }   // node 0 = head
    void findPrev(int k, int* upd) {
        int x = 0;
        for (int i = lvl - 1; i >= 0; i--) { while (nxt[x][i] != -1 && key[nxt[x][i]] < k) x = nxt[x][i]; upd[i] = x; }
    }
    bool insert(int k) {
        int upd[MAXL]; findPrev(k, upd); int y = nxt[upd[0]][0];
        if (y != -1 && key[y] == k) return false;
        int l = 1; while (l < MAXL && (rng() & 1)) l++;           // height: geometric with p = 1/2
        for (int i = lvl; i < l; i++) upd[i] = 0;
        lvl = max(lvl, l);
        int id = sz(key); key.push_back(k); nxt.push_back(vector<int>(l));
        for (int i = 0; i < l; i++) { nxt[id][i] = nxt[upd[i]][i]; nxt[upd[i]][i] = id; }
        return true;
    }
    bool erase(int k) {                                         // the node's memory is not reused
        int upd[MAXL]; findPrev(k, upd); int y = nxt[upd[0]][0];
        if (y == -1 || key[y] != k) return false;
        for (int i = 0; i < sz(nxt[y]); i++) nxt[upd[i]][i] = nxt[y][i];
        return true;
    }
    optional<int> lowerBound(int k) { int upd[MAXL]; findPrev(k, upd); int y = nxt[upd[0]][0]; if (y == -1) return nullopt; return key[y]; }
};

Proof: amortized vector growth and the two-stack queue

Vector. With capacity doubling, the $k$-th reallocation copies $2^{k-1}$ elements, and after $n$ pushes the copies total $1+2+4+\cdots +2^{\lceil {\log }_{2}n\rceil -1}<2n$. So $n$ pushes cost $O(n)$: $O(1)$ amortized. (libstdc++ doubles; MSVC grows by $1.5\times$, the same argument with ratio $1.5$ gives $<3n$.) The capacity is between $n$ and $2n$, hence between 4 and 8 bytes per int.

Two-stack queue. The queue is out (top = front) followed by in reversed. A pop with empty out moves all of in to out, reversing the order, so the oldest element becomes the top of out. Each element is pushed onto in once, moved to out at most once and popped once: $O(1)$ amortized per operation. Each stack entry stores the minimum of its stack from the bottom up to it, so the minimum of the queue is the smaller of the two tops.

Ring buffer and index list. Positions are taken modulo the capacity, so head + i addresses the $i$-th element for $0\le i<$ len as long as len stays at most the capacity. In the index list, erase and insertAfter change exactly the links of $x$ and its two neighbours, preserving the invariant nxt[prv[v]] == v for all live $v$ (the sentinel $n$ closes the cycle). Tested against std::list and std::deque with random operations.

Proof: hash tables, skip lists and B-trees

Chaining. With $m$ buckets, $n$ keys and a hash function that sends each key to a uniformly random bucket independently, the expected number of other keys in the bucket of a given key is $(n-1)/m<\alpha =n/m$; an operation scans one bucket, so it costs $O(1+\alpha {)}^{†}$. Rehashing to keep $\alpha \le 1$ doubles the table, $O(1)$ amortized by the vector argument. Real hash functions are not random: a fixed std::hash<int> (the identity) lets an adversary put every key in one bucket, which is why contests need a randomized hash (see the containers note).

Skip list. Each node has height $\ge h$ with probability $2^{-(h-1)}$, independently. The expected number of nodes at level $\ge h$ is $n{2}^{-(h-1)}$, so levels above ${\log }_{2}n+c$ are empty except with probability $2^{-c+1}$, and the expected maximum level is ${\log }_{2}n+O(1)$. Search cost, read backwards from the found position: at each step the path either goes up one level (if the current node is tall enough, probability $\frac{1}{2}$) or left one node. The expected number of left moves before each up move is at most 1, so climbing ${\log }_{2}n$ levels costs about $2{\log }_{2}n$ expected steps, plus $O(1)$ expected above level ${\log }_{2}n$. Insert and erase do one search and $O(\text{height})$ pointer updates, expected $O(1)$ for the height. Expected memory: ${\sum }_h{2}^{-(h-1)}=2$ pointers per key.

B-tree. Every node except the root has at least $t-1$ keys and $t$ children, so level $d\ge 1$ has at least $2t^{d-1}$ nodes and the tree with height $h$ holds $n\ge 1+2(t-1){\sum }_{d=1}^h{t}^{d-1}=2t^h-1$ keys. Hence $h\le {\log }_t\frac{n+1}{2}$: with $t=100$, a billion keys need at most 5 node reads, which is why disks and databases use B-trees. Tested: the skip list against std::set with $10^6$ random operations.

Related notes

• Containers, Hashing and Choosing a Structure
• Heaps
• STL and Libraries Reference
• 🐬 Complexity Cheat Sheet