◐ Shell
clean mode source ↗

Библиотека контейнеров — cppreference.com

Библиотека контейнеров является универсальной коллекцией шаблонов классов и алгоритмов, позволяющих программистам легко реализовывать общие структуры данных, такие как очереди, списки и стеки. Существуют два (до C++11)три (начиная с C++11) класса контейнеров:

  • последовательные контейнеры,
  • ассоциативные контейнеры, и
  • неупорядоченные ассоциативные контейнеры,
 (начиная с C++11)

каждый из которых предназначен для поддержки различных наборов операций.

Контейнер управляет выделяемой для его элементов памятью и предоставляет функции-элементы для доступа к ним, либо непосредственно, либо через итераторы (объекты, обладающие схожими с указателями свойствами).

Большинство контейнеров обладают по крайней мере несколькими общими функциями-элементами и общей функциональностью. Выбор оптимального контейнера для конкретного случая зависит не только от предоставляемой функциональности, но и от его эффективности при различных рабочих нагрузках.

Последовательные контейнеры

Последовательные контейнеры реализуют структуры данных с возможностью последовательного доступа к ним.

Ассоциативные контейнеры

Ассоциативные контейнеры реализуют упорядоченные структуры данных с возможностью быстрого поиска (со сложностью O(log n)).

коллекция уникальных ключей, отсортированная по ключам
(шаблон класса) [править]
коллекция пар ключ-значение, отсортированных по ключам, ключи уникальны
(шаблон класса) [править]
коллекция ключей, отсортированная по ключам
(шаблон класса) [править]
коллекция пар ключ-значение, отсортированных по ключам
(шаблон класса) [править]

Неупорядоченные ассоциативные контейнеры (начиная с C++11)

Неупорядоченные ассоциативные контейнеры реализуют неупорядоченные (хешированные) структуры данных с возможностью быстрого поиска (со средней сложностью O(1), в худшем случае O(n)).

Адаптеры контейнеров

Адаптеры контейнеров предоставляют различные интерфейсы для последовательных контейнеров.

адаптирует контейнер для предоставления стека (структура данных LIFO)
(шаблон класса) [править]
адаптирует контейнер для предоставления очереди (структура данных FIFO)
(шаблон класса) [править]
адаптирует контейнер для предоставления очереди с приоритетами
(шаблон класса) [править]

(C++23)

 адаптирует контейнер для предоставления набора уникальных ключей, отсортированных по ключам
(шаблон класса) [править]

(C++23)

 адаптирует два контейнера для предоставления набора пар ключ-значение, отсортированных по уникальным ключам
(шаблон класса) [править]
адаптирует контейнер для предоставления набора ключей, отсортированных по ключам
(шаблон класса) [править]
адаптирует два контейнера для предоставления набора пар ключ-значение, отсортированных по ключам
(шаблон класса) [править]

Представления

Представления предоставляют гибкие средства для взаимодействия с одномерными или многомерными представлениями над массивом элементов, не являющимся владельцем.

не владеющее представление непрерывной последовательности объектов
(шаблон класса) [править]
многомерное представление массива без владения
(шаблон класса) [править]

Представления

span(начиная с C++20) и mdspan(начиная с C++23) являются невладеющими представлениями над непрерывной последовательностью объектов, хранилище которых принадлежит какому-то другому объекту.

не владеющее представление непрерывной последовательности объектов
(шаблон класса) [править]
многомерное представление массива без владения
(шаблон класса) [править]

Недействительные итераторы

Методы только для чтения никогда не делают итераторы или ссылки недействительными. Методы, которые изменяют содержимое контейнера, могут сделать недействительными итераторы и/или ссылки, как показано в этой таблице.

Категория Контейнер После вставки... После стирания... Условие
итераторы действительны? ссылки действительны? итераторы действительны? ссылки действительны?
Последовательные контейнеры array Н/Д Н/Д
vector Нет Н/Д Вставка изменяет ёмкость
Да Да Перед изменённым элементом(ами)
(для вставки только если ёмкость не изменилась)
Нет Нет В или после изменённого элемента(ов)
deque Нет Да Да, кроме стёртого элемента(ов) Изменён первый или последний элемент
Нет Нет Изменение только в середине
list Да Да, кроме стёртого элемента(ов)
forward_list Да Да, кроме стёртого элемента(ов)
Ассоциативные контейнеры set
multiset
map
multimap 		Да Да, кроме стёртого элемента(ов)
Неупорядоченные ассоциативные контейнеры unordered_set
unordered_multiset
unordered_map
unordered_multimap 		Нет Да Н/Д Вставка вызывает перехэширование
Да Да, кроме стёртого элемента(ов) Перехэширование не происходит

Здесь вставка относится к любому методу, который добавляет один или несколько элементов в контейнер, а стирание относится к любому методу, который удаляет один или несколько элементов из контейнера.

  • Примеры методов вставки: std::set::insert, std::map::emplace, std::vector::push_back и std::deque::push_front.
  • Обратите внимание, что std::unordered_map::operator[] также относится к ним, поскольку он может вставить элемент в map.
 (начиная с C++11)
  • Примеры методов стирания: std::set::erase, std::vector::pop_back, std::deque::pop_front и std::map::clear.
    • clear делает недействительными все итераторы и ссылки. Поскольку он стирает все элементы, он технически соответствует приведённым выше правилам.

Особого упоминания заслуживает конечный итератор. В общем, этот итератор недействителен, как если бы он был обычным итератором для нестёртого элемента. Таким образом, std::set::end никогда не становится недействительным, std::unordered_set::end становится недействительным только при повторном хешировании (начиная с C++11), std::vector::end всегда недействителен (поскольку он всегда находится после изменённых элементов) и так далее.

Есть одно исключение: стирание, которое удаляет последний элемент std::deque делает недействительным конечный итератор, даже если это не стёртый элемент контейнера (или элемент вообще). В сочетании с общими правилами для итераторов std::deque, конечный результат состоит в том, что единственная модифицирующая операция, которая не делает недействительным std::deque::end это стирание, которое удаляет первый элемент, но не последний.

Безопасность потоков

  1. Все функции контейнеров могут вызываться одновременно разными потоками. В более общем смысле, функции стандартной библиотеки C++ не читают объекты, доступные другим потокам, если только эти объекты не доступны прямо или косвенно через аргументы функции, включая указатель this.
  2. Все функции-элементы const могут вызываться одновременно разными потоками в одном и том же контейнере. Кроме того, функции-элементы begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at() и, за исключением ассоциативных контейнеров, operator[], ведут себя как const в целях безопасности потоков (то есть они также могут вызываться одновременно разными потоками в одном и том же контейнере). В более общем плане функции стандартной библиотеки C++ не изменяют объекты, если эти объекты не доступны, прямо или косвенно, через неконстантные аргументы функции, включая указатель this.
  3. Различные элементы в одном контейнере могут быть изменены одновременно разными потоками, за исключением элементов std::vector<bool> (например, вектор объектов std::future может получать значения из нескольких потоков).
  4. Операции над итератором (например, инкремент итератора) читают, но не изменяют базовый контейнер, и могут выполняться одновременно с операциями над другими итераторами в том же контейнере, с константными функциями-элементами, или читать из элементов. Операции над контейнером, которые делают недействительными любые итераторы, изменяют контейнер и не могут выполняться одновременно с любыми операциями над существующими итераторами, даже если эти итераторы действительны.
  5. Элементы одного и того же контейнера можно изменять одновременно с теми функциями-элементами, которые не получают доступ к этим элементам. В более общем плане функции стандартной библиотеки C++ не читают объекты, косвенно доступные через их аргументы (включая другие элементы контейнера), за исключением случаев, когда этого требует спецификация контейнера.
  6. В любом случае контейнерные операции (а также алгоритмы или любые другие стандартные библиотечные функции C++) могут быть распараллелены внутренне, если это не меняет видимые для пользователя результаты (например, std::transform может быть распараллелена, но не std::for_each, которая проходит каждый элемент последовательности по порядку)).
 (начиная с C++11)

Таблица функций

Примечание: std::basic_string не рассматривается стандартом как контейнер, но ведет себя так же из-за своего сходства. Для удобства он указан здесь как 'Псевдоконтейнер'.

- функции, присутствующие в C++03
- функции, присутствующие в C++11
- функции, присутствующие с C++17
- функции, присутствующие с C++20
- функции, присутствующие с C++23

Таблица функций-элементов

  • Примечание: функции в двух разных строках extract имеют разные значения и синтаксис:
  1. ↑ e.g., node_type extract(const_iterator) or node_type extract(Key&)
  2. ↑ e.g., container_type extract() &&

Таблица функций, не являющихся элементами

Операторы <, <=, >, >= и != синтезируются из operator<=> и operator== соответственно.

(начиная с C++20)

Отчёты о дефектах

Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:

Номер Применён Поведение в стандарте Корректное поведение
LWG 51 C++98 итераторы контейнера могут быть признаны недействительными
из-за произвольной библиотечной операции 		они становятся недействительными
только когда указано

Смотрите также

Именованные требования С++: