Библиотека контейнеров — это обобщённый набор шаблонов классов и алгоритмов, позволяющий программистам легко реализовывать общие структуры данных, такие как очереди, списки и стеки. Существует два(до C++11)три(с C++11) типа контейнеров:
контейнеры последовательности,
ассоциативные контейнеры и
неупорядоченные ассоциативные контейнеры,
(с C++11)
каждый из которых предназначен для поддержки разного набора операций.
Контейнер управляет выделенным пространством памяти для своих элементов и предоставляет методы-члены для доступа к ним, либо напрямую, либо через итераторы (объекты, свойства которых аналогичны указателям).
Большинство контейнеров имеют по крайней мере несколько общих методов-членов и общие функции. Какой контейнер лучше подходит для конкретного приложения, зависит не только от предлагаемых функций, но и от его эффективности для различных задач.
Контейнеры последовательности
Контейнеры последовательности реализуют структуры данных, к которым можно получить последовательный доступ.
набор пар ключ-значение, отсортированный по ключам (шаблон класса)
Неупорядоченные ассоциативные контейнеры (с C++11)
Неупорядоченные ассоциативные контейнеры реализуют неупорядоченные (хешированные) структуры данных, которые можно быстро искать (в среднем O(1), в худшем случае O(n)).
многомерное представление массива без владения (шаблон класса)
Недействительность итераторов
Только для чтения методы никогда не аннулируют итераторы или ссылки. Методы, которые изменяют содержимое контейнера, могут аннулировать итераторы и/или ссылки, как указано в этой таблице.
Здесь вставка относится к любому методу, который добавляет один или несколько элементов в контейнер, а удаление относится к любому методу, который удаляет один или несколько элементов из контейнера.
clear делает недействительными все итераторы и ссылки. Поскольку он удаляет все элементы, это технически соответствует вышеуказанным правилам.
Если не указано иное (явно или путем определения функции через другие функции), передача контейнера в качестве аргумента функции библиотеки никогда не делает недействительными итераторы к или не изменяет значения объектов внутри этого контейнера.
Итератор до конца заслуживает особого упоминания. В общем случае этот итератор становится недействительным так, как будто он был обычным итератором на неудалённый элемент. Итак, std::set::end никогда не становится недействительным, std::unordered_set::end становится недействительным только при перехешировании(с C++11), 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 может получать значения из нескольких потоков).
Операции с итераторами (например, инкрементирование итератора) считывают, но не изменяют базовый контейнер, и могут выполняться одновременно с операциями с другими итераторами на том же контейнере, с константными членами-функциями или чтением из элементов. Операции контейнера, которые делают недействительными любые итераторы, изменяют контейнер и не могут выполняться одновременно ни с какими операциями с существующими итераторами, даже если эти итераторы не становятся недействительными.
Элементы одного контейнера могут быть изменены одновременно с теми членами-функциями, которые не указаны для доступа к этим элементам. Более общо, функции стандартной библиотеки C++ не считывают объекты, косвенно доступные через их аргументы (включая другие элементы контейнера), кроме случаев, когда это необходимо в соответствии с его спецификацией.
В любом случае, операции контейнера (а также алгоритмы или любые другие функции стандартной библиотеки C++) могут быть распараллелены внутри, пока это не изменяет видимые пользователем результаты (например, std::transform может быть распараллелен, но не std::for_each, который предназначен для последовательного посещения каждого элемента последовательности).
(с C++11)
Таблица функций
Примечание: std::basic_string не рассматривается как контейнер стандартом, но ведет себя почти как таковой из-за сходства. Для удобства он здесь перечислен как «Псевдоконтейнер».
