// T-OLIMPIANS · ARKUSZ REFERENCYJNY

Struktury
danych
w C++

Metody, złożoności czasowe i praktyczne wskazówki
na konkursy informatyczne — OIJ, OI, IOI.
vectorpairdequequeuestackpriority_queuesetunordered_setmapunordered_mapbitsetordered_set (pbds)
T-Olimpians · Team Poland · t-olimpians.com
01vector — tablica dynamiczna
Używany jako: tablica, stos, bufor. Operacje na końcu są szybkie — na początku i w środku wolne.
W tabeli all(v) to skrót na v.begin(), v.end() (#define all(v) v.begin(), v.end()).
OperacjaKodZłożoność
Deklaracja z rozmiaremvector<int> v(n, 0);O(n)
Indeksowaniev[i]O(1)
Ustawienie elementuv[i] = x;O(1)
Dodanie na koniecv.push_back(x), v.emplace_back(x)O(1)*
Usunięcie z końcav.pop_back()O(1)
Dodanie na początek/środekv.insert(v.begin() + i, x)O(n)
Usunięcie z początku/środkav.erase(v.begin() + i)O(n)
Pierwszy / ostatniv.front(), v.back()O(1)
Rozmiar / czy pustyv.size(), v.empty()O(1)
Zmiana rozmiaruv.resize(k)O(|k-n|)
Czyszczeniev.clear()O(n)
Sortowaniesort(all(v))O(n log n)
Odwróceniereverse(all(v))O(n)
Wyszukanie wartościfind(all(v), x)O(n)
Wyszukanie binarne (posortowany)binary_search(all(v), x)O(log n)
Pierwszy ≥ x / pierwszy > xlower_bound(all(v), x), upper_bound(all(v), x)O(log n)
Suma elementówaccumulate(all(v), 0LL)O(n)
Minimum / maksimum*min_element(all(v)), *max_element(all(v))O(n)
Usunięcie duplikatów (po sort)v.erase(unique(all(v)), v.end())O(n)
Dwa wymiary: vector<vector<int>> dp(n, vector<int>(m, 0)); to tablica n×m wypełniona zerami.
Graf jako listy sąsiedztwa: vector<vector<int>> g(n + 1);, a potem g[a].push_back(b);.
* Amortyzowane — co jakiś czas push_back przepisuje całą tablicę, ale średnio wychodzi O(1).
Pułapka konkursowa: v[i] nie sprawdza zakresu — wyjście poza rozmiar to UB, zwykle zła odpowiedź zamiast błędu. Do funkcji przekazuj wektor jako const vector<int>& — bez & kopiujesz go w O(n).
t-olimpians.com — ściąga struktur danych C++ — str. 2
02pair / tuple — para i krotka
Sklejają kilka wartości w jedną. Porównywane leksykograficznie — dlatego świetnie sortują się w vector i działają jako klucz w map / set.
OperacjaKodZłożoność
Utworzenie parypair<int, int> p = {a, b}; lub make_pair(a, b)O(1)
Dostęp do pólp.first, p.secondO(1)
Rozpakowanie (C++17)auto [a, b] = p;O(1)
Porównanie (leksykograficzne)p1 < p2O(1)
Wektor parvector<pair<int, int>> v;O(1)
Dodanie pary do wektorav.emplace_back(a, b);O(1)*
Sortowanie parsort(all(v))O(n log n)
Krotka 3+ wartoścituple<int, int, int> t = {a, b, c};O(1)
Dostęp w krotceget<0>(t), auto [a, b, c] = t;O(1)
Pułapka konkursowa: sort na vector<pair> porządkuje po first, a przy remisie po second. Potrzebujesz innej kolejności — wstaw do first to, po czym sortujesz (np. -waga, by uzyskać malejąco), albo podaj własny komparator.
03deque — kolejka dwustronna
Szybka na obu końcach, a przy tym pozwala na indeksowanie w O(1) (inaczej niż list czy deque z Pythona). Baza kolejki monotonicznej.
OperacjaKodZłożoność
Dodanie na koniecdq.push_back(x)O(1)
Dodanie na początekdq.push_front(x)O(1)
Usunięcie z końcadq.pop_back()O(1)
Usunięcie z początkudq.pop_front()O(1)
Indeksowaniedq[i]O(1)
Pierwszy / ostatnidq.front(), dq.back()O(1)
Rozmiar / czy pustadq.size(), dq.empty()O(1)
Wstawienie w środkudq.insert(dq.begin() + i, x)O(n)
Iteracjafor (int x : dq)O(n)
Trik: minimum w oknie przesuwnym w O(n) — w deque trzymaj indeksy o rosnących wartościach: z przodu zdejmuj te, które wypadły z okna, z tyłu te, które są większe od nowego elementu.
t-olimpians.com — ściąga struktur danych C++ — str. 3
04queue / stack — kolejka i stos
Nakładki na deque. queue: pierwszy wszedł — pierwszy wychodzi (BFS). stack: ostatni wszedł — pierwszy wychodzi (DFS, nawiasy). Obie mają tylko po kilka metod.
OperacjaqueuestackZłożoność
Deklaracjaqueue<int> q;stack<int> st;O(1)
Dodanieq.push(x)st.push(x)O(1)
Dodanie w miejscuq.emplace(x)st.emplace(x)O(1)
Odczyt następnegoq.front()st.top()O(1)
Odczyt ostatniegoq.back()—O(1)
Usunięcieq.pop()st.pop()O(1)
Rozmiar / czy pustaq.size(), q.empty()st.size(), st.empty()O(1)
Pułapka konkursowa: pop() niczego nie zwraca — najpierw int x = q.front();, dopiero potem q.pop();. Odczyt z pustej struktury to UB, więc zawsze while (!q.empty()).
Do czego stos: sprawdzanie nawiasów, ONP, DFS bez rekurencji oraz najbliższy większy element (stos monotoniczny, O(n)).
05priority_queue — kopiec
Domyślnie kopiec MAKSYMALNY — na górze największy element.
OperacjaKodZłożoność
Kopiec maksymalnypriority_queue<int> pq;O(1)
Kopiec minimalnypriority_queue<int, vector<int>, greater<int>> pq;O(1)
Wstawieniepq.push(x), pq.emplace(x)O(log n)
Podgląd szczytupq.top()O(1)
Usunięcie szczytupq.pop()O(log n)
Rozmiar / czy pustapq.size(), pq.empty()O(1)
Budowa z wektorapriority_queue<int> pq(all(v));O(n)
Pułapka konkursowa: nie da się usunąć elementu ze środka ani przejrzeć kopca. W Dijkstrze trzymaj pary {dystans, wierzchołek} w kopcu minimalnym i pomijaj nieaktualne wpisy (if (d > dist[v]) continue;). Potrzebujesz usuwania dowolnego elementu → użyj set.
t-olimpians.com — ściąga struktur danych C++ — str. 4
06set / multiset — zbiór posortowany
Drzewo czerwono-czarne: elementy są zawsze posortowane. set trzyma unikalne, multiset dopuszcza duplikaty.
OperacjaKodZłożoność
Wstawienies.insert(x)O(log n)
Usunięcie po wartościs.erase(x)O(log n)
Usunięcie po iteratorzes.erase(it)O(1) am.
Czy zawieras.count(x), s.contains(x) (C++20)O(log n)
Znalezienie elementus.find(x)O(log n)
Najmniejszy*s.begin()O(1)
Największy*s.rbegin()O(1)
Pierwszy ≥ xs.lower_bound(x)O(log n)
Pierwszy > xs.upper_bound(x)O(log n)
Rozmiar / czy pustys.size(), s.empty()O(1)
Iteracja (rosnąco)for (int x : s)O(n)
Pułapka konkursowa: zawsze s.lower_bound(x), nigdy lower_bound(all(s), x) — ta druga wersja na secie działa w O(n). W multiset s.erase(x) kasuje WSZYSTKIE kopie; jedną usuniesz przez s.erase(s.find(x)).
07unordered_set — zbiór haszujący
Bez kolejności, za to średnio O(1). Nie ma lower_bound / upper_bound ani iteracji po kolei.
OperacjaKodŚredniaPesymist.
Wstawienieus.insert(x)O(1)O(n)
Usunięcieus.erase(x)O(1)O(n)
Czy zawieraus.count(x), us.find(x)O(1)O(n)
Rozmiar / czy pustyus.size(), us.empty()O(1)—
Iteracja (losowa kolejność)for (int x : us)O(n)—
Rezerwacja miejscaus.reserve(n)O(n)—
Pułapka konkursowa: na OI trafiają się testy anty-hash, które psują unordered_set do O(n) na operację. Ratunek: zwykły set albo własny hash z losowym ziarnem (chrono::steady_clock::now().time_since_epoch().count()).
t-olimpians.com — ściąga struktur danych C++ — str. 5
08map / unordered_map — słownik
Przypisują kluczom wartości: map<string, int> m;. map trzyma klucze posortowane (drzewo), unordered_map wrzuca je do tablicy haszującej.
OperacjaKodmapunordered_map
Dostęp / wstawieniem[k], m[k] = v;O(log n)O(1) śr.
Czy jest kluczm.count(k), m.find(k)O(log n)O(1) śr.
Usunięciem.erase(k)O(log n)O(1) śr.
Wstawienie bez nadpisaniam.emplace(k, v)O(log n)O(1) śr.
Iteracjafor (auto& [k, v] : m)O(n) rosnącoO(n) losowo
Pierwszy klucz ≥ km.lower_bound(k)O(log n)brak
Najmniejszy kluczm.begin()->firstO(1)brak
Rozmiar / czy pustam.size(), m.empty()O(1)O(1)
Pułapka konkursowa: m[k] TWORZY brakujący klucz z wartością 0 — samo if (m[k] > 0) powiększa mapę i psuje m.size() oraz iterację. Do sprawdzania używaj m.count(k).
09bitset — tablica bitów
N bitów upakowanych po 64 w słowie — operacje na całym zbiorze są ok. 64× szybsze niż na vector<bool>. Rozmiar musi być stałą znaną w czasie kompilacji.
OperacjaKodZłożoność
Deklaracjabitset<1000006> b;O(n/64)
Ustawienie bitub[i] = 1, b.set(i)O(1)
Wyzerowanie bitu / całościb.reset(i), b.reset()O(1) / O(n/64)
Zanegowanieb.flip(i), ~bO(1) / O(n/64)
Odczyt bitub[i], b.test(i)O(1)
Liczba jedynekb.count()O(n/64)
Czy są jedynkib.any(), b.none(), b.all()O(n/64)
Suma / iloczyn / xor zbiorówa | b, a & b, a ^ bO(n/64)
Przesunięcieb << k, b >> kO(n/64)
Pierwsza / następna jedynka (GCC)b._Find_first(), b._Find_next(i)O(n/64)
Zamiana na liczbę / tekstb.to_ullong(), b.to_string()O(n/64)
Klasyka: sito Eratostenesa dla dużych N oraz plecak dp |= dp << w; — zamiast O(n·W) dostajesz O(n·W/64), czyli realnie ok. 64 razy szybciej.
t-olimpians.com — ściąga struktur danych C++ — str. 6
10ordered_set (pbds) — set z numerowaniem
Rozszerzenie GCC: set, który dodatkowo umie odpowiedzieć, ile elementów jest mniejszych od x oraz co stoi na k-tej pozycji. W wielu zadaniach zastępuje drzewo przedziałowe.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;

ordered_set A;
OperacjaKodZłożoność
WstawienieA.insert(x)O(log n)
Usunięcie elementu równego xA.erase(x)O(log n)
Ile elementów mniejszych od xA.order_of_key(x)O(log n)
Element na k-tej pozycji*A.find_by_order(k)O(log n)
Pierwszy ≥ x / pierwszy > xA.lower_bound(x), A.upper_bound(x)O(log n)
Rozmiar / czy pustyA.size(), A.empty()O(1)
Iteracja (rosnąco)for (int x : A)O(n)
Trzeci parametr szablonu decyduje o wszystkim:
1) less<int> / greater<int> → ordered_set — bez duplikatów, rosnąco / malejąco
2) less_equal<int> / greater_equal<int> → ordered_multiset — z duplikatami
Pułapka konkursowa: order_of_key(x) liczy elementy ostro MNIEJSZE od x, a find_by_order(k) numeruje od zera. W wersji z less_equal przestają działać find i erase(x) — usuwaj przez A.erase(A.find_by_order(A.order_of_key(x))) — a lower_bound i upper_bound zamieniają się rolami. Kompiluje się tylko pod g++.
11ordered_set — typowe zastosowania
ZadanieRozwiązanieZłożoność
k-ty najmniejszy element zbioru*A.find_by_order(k - 1)O(log n)
Pozycja x w posortowanym zbiorzeA.order_of_key(x)O(log n)
Ile elementów w przedziale [a, b]A.order_of_key(b + 1) - A.order_of_key(a)O(log n)
Liczba inwersji w ciągu (różne wartości)idź od końca: A.order_of_key(v[i]), potem A.insert(v[i])O(n log n)
t-olimpians.com — ściąga struktur danych C++ — str. 7
12Tabela podsumowująca
StrukturaDostępWstawienieUsunięciePosortowana
vectorO(1)O(1) koniecO(1) koniecnie
dequeO(1)O(1) oba końceO(1) oba końcenie
queue / stackO(1) skrajO(1)O(1)nie
priority_queueO(1) szczytO(log n)O(log n)tylko szczyt
set / multisetO(log n)O(log n)O(log n)tak
mapO(log n)O(log n)O(log n)tak (klucze)
unordered_set / mapO(1) śr.*O(1) śr.*O(1) śr.*nie
bitsetO(1)O(1)O(1)indeks = wartość
ordered_setO(log n)O(log n)O(log n)tak + k-ty
* Pesymistycznie O(n) na operację — przy testach anty-hash struktury haszujące potrafią się wywrócić.
13Co wybrać do czego
Stos
stack — albo vector (push_back/pop_back)
Kolejka (BFS)
queue — push / front / pop
Kolejka priorytetowa / Dijkstra
priority_queue + greater<>
Zliczanie wystąpień
map<int, int> / unordered_map
Szybkie sprawdzenie „czy było”
unordered_set — małe wartości: vector<bool>
Zbiór trzymany w kolejności
set — z duplikatami: multiset
k-ty najmniejszy / ile mniejszych
ordered_set (pbds)
Minimum w oknie przesuwnym
deque — kolejka monotoniczna
Wielkie operacje na zbiorach bitów
bitset — sito, plecak
Klucz złożony z kilku wartości
pair / tuple
0-1 BFS
deque — push_front dla krawędzi 0
Tablica o rozmiarze z wejścia
vector<int> v(n) — zamiast tablic VLA
Na start zawodów: #include <bits/stdc++.h> wciąga całą bibliotekę standardową (g++), a using namespace std; oszczędza pisania std::. Do ordered_set dochodzą jeszcze dwa nagłówki pb_ds z sekcji 10.
t-olimpians.com — ściąga struktur danych C++ — str. 8