Контейнер	Поиск	Конец (вставка)	Середина (вставка)	Random access
`vector`	O(n)	O(1) аморт.	O(n)	O(1)
`deque`	O(n)	O(1)	O(n)	O(1)
`list`	O(n)	O(1)	O(1) после `find`	—
`map`	O(log n)	O(log n)	O(log n)	—
`unordered_map`	O(1) avg	O(1) avg	O(1) avg	—
`set`	O(log n)	O(log n)	O(log n)	—

Ошибка	Последствие
Хранить ссылку/указатель на элемент `vector` через `push_back`	Реаллокация → UB, ссылка указывает на освобождённую память
Использовать `operator[]` на `std::map` для проверки наличия ключа	Молча вставится элемент с дефолтным значением
Выбирать `std::list` из-за `O(1)` вставки в середину	На малых/средних данных проигрывает `vector` из-за cache miss
`unordered_map` без качественного хэша на внешних ключах	Hash collision attack — деградация до `O(n)`
Полагаться на симметричное XOR-комбинирование хэшей	`hash(a) ^ hash(b) == hash(b) ^ hash(a)` — лишние коллизии
Сравнивать `std::vector<int>` и `std::vector<int, MyAlloc>` как один тип	Это разные шаблонные инстансы, не взаимозаменяемы
Использовать `[i]` на `vector` без проверки границ	UB при выходе; для безопасности есть `.at(i)`
`pop()` у адаптеров считать возвращающим значение	Не возвращает — exception-safety design; используйте `top()`+`pop()`
`iterator` после рехэша `unordered_map`	Инвалидирован; нужно перезапросить
Кастомный компаратор `<=` вместо `<`	Нарушение strict weak ordering → UB в RB-tree

beginner

STL Containers

vector, list, map, unordered_map, iterators, and allocators — the standard C++ containers, their internals, complexity, and selection rules.

Containers

Practice: 31 questions · 1 task →

Sections

Contents

Detailed explanation

STL Containers — choose by guarantees, not by name

Picking a container is one of the first technical decisions in any data structure and one of the most common topics on a C++ interview. Easy to get wrong: std::list looks attractive for "frequent middle insertions" until profiling shows it 3× slower than std::vector on real data because of a cache miss per node. std::unordered_map looks like the obvious "fast lookup" until its hash function degrades on adversarial keys.

In C++ an "STL container" is not just a data structure — it is a bundle of four things: a storage model (array, tree, hash), an iterator interface, an invalidation policy, and an allocator template parameter. All standard algorithms (std::sort, std::find, ranges) work through the iterator interface without knowing the underlying container. Allocators let you change where the memory comes from without changing the algorithm.

The right container choice is the choice of guarantees: what complexity, what ordering, what iterator stability, what memory model do you want. The full map lives in the layers below.

Topic map

Sequence containers and adapters — vector, deque, list, forward_list, array; stack/queue/priority_queue adapters; growth strategy and cache locality.
Ordered associative containers — map, set, multimap, multiset on a red-black tree; range queries, lower_bound, custom comparators.
Unordered associative containers — unordered_map/set; hash table, load factor, rehash, hash quality, hash collision attack.
Iterators and invalidation — iterator categories, range-based for, invalidation rules after insert/erase/push_back.
Allocators and std::pmr — std::allocator, custom allocators as part of the type, polymorphic memory resources from C++17, monotonic buffer.

Complexity at a glance

Container	Find	End insert	Mid insert	Random access
`vector`	O(n)	O(1) amortized	O(n)	O(1)
`deque`	O(n)	O(1)	O(n)	O(1)
`list`	O(n)	O(1)	O(1) after `find`	—
`map`	O(log n)	O(log n)	O(log n)	—
`unordered_map`	O(1) avg	O(1) avg	O(1) avg	—
`set`	O(log n)	O(log n)	O(log n)	—

Common traps

Mistake	Consequence
Holding a reference/pointer to a `vector` element across `push_back`	Reallocation → UB, reference points at freed memory
`operator[]` on `std::map` to check for a key	Silently inserts a default-valued element
Picking `std::list` because mid-insert is `O(1)`	On small/medium data it loses to `vector` due to cache misses
`unordered_map` without a good hash on external keys	Hash collision attack — degrades to `O(n)`
Combining hashes with symmetric XOR	`hash(a) ^ hash(b) == hash(b) ^ hash(a)` — extra collisions
Treating `std::vector<int>` and `std::vector<int, MyAlloc>` as one type	They are different template instantiations
Indexing `vector` with `[i]` and no bounds check	UB on overflow; use `.at(i)` for the checked version
Assuming adapter `pop()` returns a value	It does not — by design, for exception safety; use `top()` + `pop()`
Using an iterator after `unordered_map` rehash	Invalidated; re-query needed
Custom comparator using `<=` instead of `<`	Breaks strict weak ordering → UB in the RB-tree

Interview relevance

Containers appear on almost every C++ interview, from junior to staff. Reason: container choice exposes your understanding of complexity, the memory model, and trade-offs — the things that separate a confident engineer from someone who "knows the syntax".

Typical checks:

How vector and list differ in actual speed, not just Big-O.
vector growth strategy and what push_back invalidates.
map vs unordered_map — which guarantees, when to pick which.
What load factor is and when rehash happens.
Iterator categories and invalidation rules.
Why operator[] on map is dangerous and how to avoid it.
What std::pmr is and why it exists.
How to build an LRU cache on top of standard containers (list + unordered_map).

Common wrong answer: "I pick list because mid-insert is O(1)." That opens the discussion of amortized complexity vs hardware reality, where cache misses often dominate the count of comparisons.

Why it matters

Container choice exposes understanding of algorithmic complexity, memory model, and practical trade-offs — the things that separate a confident engineer from someone who "knows the syntax".

Контейнер	Поиск	Конец (вставка)	Середина (вставка)	Random access
`vector`	O(n)	O(1) аморт.	O(n)	O(1)
`deque`	O(n)	O(1)	O(n)	O(1)
`list`	O(n)	O(1)	O(1) после `find`	—
`map`	O(log n)	O(log n)	O(log n)	—
`unordered_map`	O(1) avg	O(1) avg	O(1) avg	—
`set`	O(log n)	O(log n)	O(log n)	—

Ошибка	Последствие
Хранить ссылку/указатель на элемент `vector` через `push_back`	Реаллокация → UB, ссылка указывает на освобождённую память
Использовать `operator[]` на `std::map` для проверки наличия ключа	Молча вставится элемент с дефолтным значением
Выбирать `std::list` из-за `O(1)` вставки в середину	На малых/средних данных проигрывает `vector` из-за cache miss
`unordered_map` без качественного хэша на внешних ключах	Hash collision attack — деградация до `O(n)`
Полагаться на симметричное XOR-комбинирование хэшей	`hash(a) ^ hash(b) == hash(b) ^ hash(a)` — лишние коллизии
Сравнивать `std::vector<int>` и `std::vector<int, MyAlloc>` как один тип	Это разные шаблонные инстансы, не взаимозаменяемы
Использовать `[i]` на `vector` без проверки границ	UB при выходе; для безопасности есть `.at(i)`
`pop()` у адаптеров считать возвращающим значение	Не возвращает — exception-safety design; используйте `top()`+`pop()`
`iterator` после рехэша `unordered_map`	Инвалидирован; нужно перезапросить
Кастомный компаратор `<=` вместо `<`	Нарушение strict weak ordering → UB в RB-tree

beginner

STL Containers

vector, list, map, unordered_map, iterators, and allocators — the standard C++ containers, their internals, complexity, and selection rules.

Containers

Practice: 31 questions · 1 task →

Sections

Contents

Detailed explanation

STL Containers — choose by guarantees, not by name

The right container choice is the choice of guarantees: what complexity, what ordering, what iterator stability, what memory model do you want. The full map lives in the layers below.

Topic map

Sequence containers and adapters — vector, deque, list, forward_list, array; stack/queue/priority_queue adapters; growth strategy and cache locality.
Ordered associative containers — map, set, multimap, multiset on a red-black tree; range queries, lower_bound, custom comparators.
Unordered associative containers — unordered_map/set; hash table, load factor, rehash, hash quality, hash collision attack.
Iterators and invalidation — iterator categories, range-based for, invalidation rules after insert/erase/push_back.
Allocators and std::pmr — std::allocator, custom allocators as part of the type, polymorphic memory resources from C++17, monotonic buffer.

Complexity at a glance

Container	Find	End insert	Mid insert	Random access
`vector`	O(n)	O(1) amortized	O(n)	O(1)
`deque`	O(n)	O(1)	O(n)	O(1)
`list`	O(n)	O(1)	O(1) after `find`	—
`map`	O(log n)	O(log n)	O(log n)	—
`unordered_map`	O(1) avg	O(1) avg	O(1) avg	—
`set`	O(log n)	O(log n)	O(log n)	—

Common traps

Mistake	Consequence
Holding a reference/pointer to a `vector` element across `push_back`	Reallocation → UB, reference points at freed memory
`operator[]` on `std::map` to check for a key	Silently inserts a default-valued element
Picking `std::list` because mid-insert is `O(1)`	On small/medium data it loses to `vector` due to cache misses
`unordered_map` without a good hash on external keys	Hash collision attack — degrades to `O(n)`
Combining hashes with symmetric XOR	`hash(a) ^ hash(b) == hash(b) ^ hash(a)` — extra collisions
Treating `std::vector<int>` and `std::vector<int, MyAlloc>` as one type	They are different template instantiations
Indexing `vector` with `[i]` and no bounds check	UB on overflow; use `.at(i)` for the checked version
Assuming adapter `pop()` returns a value	It does not — by design, for exception safety; use `top()` + `pop()`
Using an iterator after `unordered_map` rehash	Invalidated; re-query needed
Custom comparator using `<=` instead of `<`	Breaks strict weak ordering → UB in the RB-tree

Interview relevance

Typical checks:

How vector and list differ in actual speed, not just Big-O.
vector growth strategy and what push_back invalidates.
map vs unordered_map — which guarantees, when to pick which.
What load factor is and when rehash happens.
Iterator categories and invalidation rules.
Why operator[] on map is dangerous and how to avoid it.
What std::pmr is and why it exists.
How to build an LRU cache on top of standard containers (list + unordered_map).

Why it matters

Container choice exposes understanding of algorithmic complexity, memory model, and practical trade-offs — the things that separate a confident engineer from someone who "knows the syntax".

Контейнеры STL

Контейнеры STL — выбор по гарантиям, а не по названию

Карта темы

Сравнение сложностей

Частые ошибки и ловушки

Значение для собеседований

STL Containers

STL Containers — choose by guarantees, not by name

Topic map

Complexity at a glance

Common traps

Interview relevance

Контейнеры STL

Контейнеры STL — выбор по гарантиям, а не по названию

Карта темы

Сравнение сложностей

Частые ошибки и ловушки

Значение для собеседований

STL Containers

STL Containers — choose by guarantees, not by name

Topic map

Complexity at a glance

Common traps

Interview relevance