Библиотека контейнеров — это универсальный набор шаблонов классов и алгоритмов, позволяющих программистам легко реализовывать распространённые структуры данных, такие как очереди, списки и стеки. Существует два(до C++11)три(начиная с C++11) класса контейнеров:
последовательные контейнеры,
ассоциативные контейнеры,
неупорядоченные ассоциативные контейнеры,
(начиная с C++11)
каждый из которых предназначен для поддержки своего набора операций.
Контейнер управляет пространством хранения, выделенным для его элементов, и предоставляет функции-члены для доступа к ним — напрямую или через итераторы (объекты со свойствами, подобными свойствам указателей).
У большинства контейнеров есть как минимум несколько общих функций-членов и общие возможности. Выбор наиболее подходящего контейнера для конкретного приложения зависит не только от предоставляемых возможностей, но и от эффективности при различных нагрузках.
Последовательные контейнеры
Последовательные контейнеры реализуют структуры данных, к элементам которых можно обращаться последовательно.
коллекция пар «ключ — значение», отсортированных по ключам (шаблон класса)
Неупорядоченные ассоциативные контейнеры (начиная с C++11)
Неупорядоченные ассоциативные контейнеры реализуют неотсортированные (хешированные) структуры данных, поиск в которых выполняется быстро (средняя сложность O(1), в худшем случае — O(n)).
невладеющее представление многомерного массива (шаблон класса)
Инвалидация итераторов
Методы, доступные только для чтения, никогда не инвалидируют итераторы или ссылки. Методы, изменяющие содержимое контейнера, могут инвалидировать итераторы и/или ссылки, как показано в этой таблице.
Да, за исключением удалённого элемента (элементов)
Рехеширования не произошло
Здесь под вставкой понимается любой метод, добавляющий в контейнер один или несколько элементов, а под удалением — любой метод, удаляющий из контейнера один или несколько элементов.
clear инвалидирует все итераторы и ссылки. Поскольку он удаляет все элементы, формально это соответствует приведённым выше правилам.
Если не указано иное (явно или через определение функции в терминах других функций), передача контейнера в качестве аргумента функции библиотеки никогда не инвалидирует итераторы на объекты внутри контейнера и не изменяет значения этих объектов.
Особого упоминания заслуживает итератор за последним элементом. В общем случае этот итератор инвалидируется так же, как обычный итератор на не удалённый элемент. Поэтому std::set::end никогда не инвалидируется, std::unordered_set::end инвалидируется только при рехешировании, std::vector::end всегда инвалидируется (поскольку он всегда находится после изменённых элементов) и так далее.
Есть одно исключение: удаление, при котором удаляется последний элемент std::deque, инвалидирует итератор за последним элементом, хотя он не указывает на удалённый элемент контейнера (и вообще не указывает на элемент). В сочетании с общими правилами для итераторов std::deque итог таков: единственная изменяющая операция, которая не инвалидирует std::deque::end, — это удаление первого элемента, если он не является последним.
Безопасность при работе с потоками
Все функции контейнеров можно одновременно вызывать из разных потоков для разных контейнеров. В более общем случае функции стандартной библиотеки C++ не читают объекты, доступные из других потоков, если эти объекты не доступны прямо или косвенно через аргументы функции, включая указатель this.
Все функции-члены const можно одновременно вызывать из разных потоков для одного и того же контейнера. Кроме того, функции-члены begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at() и, за исключением ассоциативных контейнеров, operator[], для целей обеспечения безопасности при работе с потоками ведут себя как const (то есть их также можно одновременно вызывать из разных потоков для одного и того же контейнера). В более общем случае функции стандартной библиотеки C++ не изменяют объекты, если эти объекты не доступны прямо или косвенно через неконстантные аргументы функции, включая указатель this.
Разные элементы одного контейнера можно изменять одновременно из разных потоков, за исключением элементов std::vector<bool> (например, вектор объектов std::future может получать значения из нескольких потоков).
Операции с итераторами (например, увеличение итератора) читают базовый контейнер, но не изменяют его; их можно выполнять одновременно с операциями над другими итераторами того же контейнера, с функциями-членами const или с чтением элементов. Операции с контейнером, инвалидирующие любые итераторы, изменяют контейнер, поэтому их нельзя выполнять одновременно с операциями над существующими итераторами, даже если эти итераторы не инвалидируются.
Элементы одного контейнера можно изменять одновременно с функциями-членами, для которых не указано обращение к этим элементам. В более общем случае функции стандартной библиотеки C++ не читают объекты, доступные косвенно через свои аргументы (включая другие элементы контейнера), если этого не требует их спецификация.
В любом случае операции с контейнерами (а также алгоритмы и любые другие функции стандартной библиотеки C++) могут распараллеливаться внутри реализации, если это не меняет видимые пользователю результаты (например, std::transform может выполняться параллельно, а std::for_each — нет, поскольку по спецификации он должен посещать каждый элемент последовательности по порядку).
(начиная с C++11)
Таблица функций
Примечание: стандарт не считает std::basic_string контейнером, но из-за его сходства он ведёт себя почти так же. Для удобства здесь он указан как «псевдоконтейнер».
