# Глава 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_0061/#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` во многом схожа с контейнерами стандартной библиотеки, однако не считается таковым. Строку иногда называют [псевдо-контейнером](https://en.cppreference.com/w/cpp/container) (pseudo container). Причина тому — ограничения на типы данных, которые позволяет хранить строка. Да, она может состоять не только из символов `char`! Но об этом позже. Внутри строка организована примерно так же, как `std::vector`, о котором вы скоро узнаете. Напишите функцию `rearrange_words()`. Она принимает строку, которая состоит из разделённых пробелами слов. Функция должна вернуть строку, содержащую те же слова, но в обратном порядке. Например, строка `not a bug` превратится в `bug a not`. {.task_text} Строка не может начинаться или заканчиваться пробелом. Одно слово отделяется от другого единственным пробелом. {.task_text} Воспользуйтесь итераторами, функциями [std::find()](https://en.cppreference.com/w/cpp/algorithm/find) и [std::reverse().](https://en.cppreference.com/w/cpp/algorithm/reverse) {.task_text} Эта задача имеет короткое и изящное решение. Если оно не приходит вам в голову, прочтите подсказку. {.task_text} ```cpp {.task_source #cpp_chapter_0071_task_0060} std::string rearrange_words(std::string s) { } ``` Сначала разверните строку целиком. Строка `not a bug` превратится в `gub a ton`. Затем разверните каждое слово по отдельности: `bug a not`. {.task_hint} ```cpp {.task_answer} std::string rearrange_words(std::string s) { std::reverse(s.begin(), s.end()); auto it_word = s.begin(); while (true) { auto it_space = std::find(it_word, s.end(), ' '); std::reverse(it_word, it_space); if (it_space == s.end()) break; it_word = it_space + 1; } return s; } ``` ## Другие классы, которые похожи на контейнеры Также контейнерами _не_ являются [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}