# Глава 7.1. Какие бывают контейнеры Контейнер — это коллекция элементов, реализованная как шаблон класса или структуры. Но в C++ не каждый шаблонный класс для хранения элементов может считаться контейнером. Контейнеры — это конкретные классы и структуры стандартной библиотеки. Их выбор разнообразен: есть массивы, хеш-таблицы, очереди и многое другое. Шаблоны разных контейнеров имеют разный набор параметров. Но среди них всегда есть тип элемента. Вам не обязательно досконально изучать интерфейс каждого из классов контейнеров, ведь всегда можно обратиться к [cppreference.](https://en.cppreference.com/w/cpp/container) Важнее уметь подбирать контейнер под конкретную задачу. А для этого полезно помнить: - Под какие сценарии оптимизирован контейнер. - Какова алгоритмическая сложность поддерживаемых им операций. - Какие структуры данных у него _скорее всего_ под капотом. Знание подкапотного устройства и алгоритмической сложности поможет находить ответы на вопросы: - Насколько возрастет время доступа к элементу, если размер контейнера увеличится с сотни до десятков миллионов элементов? - Почему в каких-то случаях вставка элемента работает быстро, а в каких-то — медленно? - Какие контейнеры дружелюбны к кешу процессора ([cache-friendly](https://web.cecs.pdx.edu/~jrb/cs201/lectures/cache.friendly.code.pdf)), а какие — нет? Стандарт C++ фиксирует публичный интерфейс контейнеров, ограничения на алгоритмическую сложность операций и некоторые свойства. Например, в какой последовательности хранятся элементы. У стандартной библиотеки C++ больше одной реализации. Но многие реализации контейнеров схожи из-за налагаемых стандартом требований. ## Классификация контейнеров Контейнеры делятся на три категории, по одной на каждый из основных сценариев использования: - последовательные, - упорядоченные ассоциативные, - неупорядоченные ассоциативные. В **последовательных** (sequence) контейнерах элементы хранятся линейно. Место элемента зависит от того, когда и на какую позицию он был добавлен. И не зависит от значения самого элемента. Вы уже [познакомились](/courses/cpp/chapters/cpp_chapter_0060/#block-vector) с типичным представителем последовательных контейнеров — динамическим массивом `std::vector`. Поверх последовательных контейнеров реализованы **адаптеры.** Это классы, внутри использующие контейнеры, но предоставляющие над ними другой интерфейс. Например, поверх вектора организованы такие полезные структуры данных как [стек,](https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BA) [куча](https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D1%87%D0%B0_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)) и [очереди.](https://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)) В **ассоциативных** (associative) контейнерах позиция элемента зависит от его ключа. Эти контейнеры предназначены для хранения пар «ключ-значение» или только ключей. Сопоставление ключу значения называется отображением (mapping) или ассоциацией (association). Иногда такие контейнеры называют словарями. Ассоциативные контейнеры бывают упорядоченными и неупорядоченными. **Упорядоченные** (ordered) ассоциативные контейнеры часто называют просто ассоциативными контейнерами. Их элементы всегда отсортированы, а вставка, удаление и поиск элемента осуществляются за `O(log(N))`. **Неупорядоченные** (unordered) ассоциативные контейнеры часто называют хеш-таблицами. В них элементы, напротив, не отсортированы. Любое действие с элементом выполняется за `O(1)` в среднем и `O(N)` в худшем случае. Класс `std::string`, [как вы помните,](/courses/cpp/chapters/cpp_chapter_0060/#block-string) не считается контейнером. Причина тому — ограничения на типы данных, которые позволяет хранить строка. Да, она может состоять не только из символов `char`! Но об этом позже. Внутри строка организована примерно так же, как `std::vector`, о котором вы сейчас узнаете. Также контейнерами _не_ являются [std::bitset](https://en.cppreference.com/w/cpp/utility/bitset) и [std::valarray](https://en.cppreference.com/w/cpp/numeric/valarray). Класс `std::bitset` — это статический массив битов. А `std::valaray` — динамический массив, заточенный под математические вычисления. Этот класс не пользуется популярностью: он появился в C++98 и не отличается удобным интерфейсом. Вместо него для математических расчетов обычно подключают классы из специализированных библиотек, таких как [Eigen](https://eigen.tuxfamily.org/index.php?title=Main_Page) и [Armadillo](https://arma.sourceforge.net/). ---------- ## Резюме Классификация контейнеров стандартной библиотеки:  {.illustration}