Контейнеры

По умолчанию vector — cache-friendly обход. map/set — для сортированного O(log n), unordered_map/set — для среднего O(1) без порядка, list — только когда стабильные итераторы или O(1) splice важнее локальности кэша.

std::array<T, N> — для известных на этапе компиляции размеров: стековая аллокация, обёртка над C-массивом без накладных расходов. std::vector<T> — для динамических размеров или больших буферов; владеет heap-блоком с ростом по capacity.

vector::erase инвалидирует it и все итераторы после него; следующий ++it продвигает уже висячий итератор — UB. Решение: использовать возвращаемое значение, it = v.erase(it);, и делать ++it только если ничего не удалили. Либо std::erase_if(v, pred); (C++20).

Инвалидация — итератор больше не указывает на валидный элемент после мутации. Реаллокация vector инвалидирует всё; вставка в list/map сохраняет итераторы; rehash unordered_map инвалидирует.

push_back может перевыделить память вектора при росте за пределы вместимости, инвалидируя p, который теперь висячий — UB. Указатели, ссылки и итераторы внутрь vector инвалидируются перевыделением. Решение: заново получить p после вставки или reserve вместимости заранее.

reserve(n) увеличивает capacity() минимум до n без конструирования элементов — полезно перед известной серией push_back. resize(n) меняет size() до n, value-инициализируя новые элементы и уничтожая лишние.

Оба — адаптеры, оборачивающие underlying-контейнер (по умолчанию std::deque) с ограниченным интерфейсом. std::stack даёт LIFO push/pop/top; std::queue — FIFO push/pop/front/back.

std::deque — страничная таблица указателей на блоки фиксированного размера: O(1) push/pop с обоих концов, произвольный доступ, не contiguous. Push/pop с конца инвалидирует итераторы, но сохраняет ссылки; вставка в середину — всё.

emplace_back(args...) строит элемент на месте из аргументов конструктора, экономя временный объект, который создал бы push_back(T(a,b)). С готовым T push_back(std::move(x)) эквивалентен и яснее.

Используйте container.empty() — он O(1) для всех стандартных контейнеров (включая std::list до C++11, где size() был O(n)) и прямо выражает намерение.

Специализируйте std::hash<MyKey> в namespace std или передайте хеш-callable вторым шаблонным параметром. Комбинируйте поля через hash_combine (не тривиальный XOR) и предоставьте согласованный operator==.

std::list<T> — двусвязный список из узлов на куче (значение + prev + next) с фиктивной головой/хвостом. O(1) вставка/удаление везде, плохая локальность кэша, O(1) size() с C++11.

std::map — красно-чёрное дерево: O(log n), сортированная итерация, нужен только operator<. std::unordered_map — хэш-таблица: O(1) средний (O(n) худший), произвольный порядок, нужны operator== и хэш.

По умолчанию max-heap через std::less<T> поверх vector<T>; для min-heap передайте std::greater<T> как компаратор. Push/pop — O(log n) через push_heap/pop_heap; top — O(1).

std::remove лишь сдвигает не совпадающие элементы вперёд и возвращает новый логический конец; хвост не определён. Вызовите container.erase(new_end, end()), чтобы реально отбросить хвост — remove сам не может, он работает на любых диапазонах.

std::string_view (C++17) — невладеющий view (указатель+длина) над буфером символов. Не продлевает время жизни: view от временного std::string сразу dangling, поэтому не храните его дольше источника.

unordered_map использует separate chaining — каждый bucket это связный список коллидирующих узлов. Bucket-API (load_factor, max_load_factor, rehash) задаёт момент rehash; rehash инвалидирует все итераторы.

Стандартный erase(it) — O(n), сдвигает последующие элементы влево. Если порядок не важен, используйте swap-and-pop: меняем местами с последним и вызываем pop_back() — O(1).

Три указателя (begin, end, end_of_storage) поверх contiguous heap-блока. При переполнении выделяется блок 2x, элементы перемещаются (если noexcept) или копируются, старый освобождается — амортизируя push_back до O(1).

Шесть категорий: input/output (single-pass), forward (forward_list), bidirectional (list, set, map), random-access (vector, deque, array) и contiguous из C++20 (vector, array, string, span).

C++11 требует O(1) size() через кэшированный счётчик; до C++11 было определено реализацией и часто O(n). Цена — splice всего списка стал O(n), так как счётчик нужно обновлять.

std::set хранит уникальные ключи; insert возвращает pair<iter, bool> с false при дубликате. std::multiset допускает дубликаты и всегда успешен; используйте его, когда дубликаты важны, и equal_range для обхода совпадений.

Передайте кастомный аллокатор как шаблонный параметр контейнера — он должен предоставлять value_type, allocate, deallocate (или умолчания allocator_traits). C++17 std::pmr даёт полиморфные ресурсы памяти без перешаблонизации.

ForwardIterator должен предоставлять operator*, prefix operator++, operator==/!=, конструктор копирования и псевдонимы (iterator_category, value_type, difference_type, pointer, reference) через вложенные типы или iterator_traits.

shrink_to_fit() — необязывающий запрос освободить лишнюю capacity; реализация может его проигнорировать. Переносимый приём — swap-идиома: std::vector<T>(v).swap(v).

std::span<T> (C++20) — невладеющий view (указатель+длина) над contiguous-диапазоном. Используйте как параметр функции, чтобы единообразно принимать vector, array или C-массивы без шаблонов; буфер должен жить дольше span.

Оба contiguous, но std::string добавляет гарантированный null-терминатор (c_str() — O(1)), small-string optimisation, текстовые API (find, substr) и char_traits. У vector<char> ничего этого нет — для текста используйте string.

Шаблонный параметр Allocator управляет источником памяти контейнера через allocate/deallocate. Кастомные нужны для arena/pool/NUMA/трекинга; C++17 std::pmr::polymorphic_allocator подменяет поведение во время выполнения.

std::set/std::map — красно-чёрные деревья: O(log n) операции, стабильные итераторы при вставке. std::unordered_map — хэш-таблица с раздельным связыванием: O(1) средний, O(n) худший при плохом std::hash.

std::flat_map<K, V> (C++23) — sorted contiguous container на двух параллельных vector: O(log n) бинарный поиск с локальностью кэша лучше std::map, но O(n) insert/erase. Лучшее для read-heavy нагрузок.

SBO встраивает inline-буфер на N элементов; пока size() ≤ N, heap-аллокаций нет, выше — динамическое выделение. Цена: избегаем heap для малых размеров, но sizeof(container) растёт на N * sizeof(T).