Библиотека контейнеров

 

C++

Поддержка компилятором

Автономные и размещённые реализации

Язык

Стандартная библиотека

Заголовки стандартной библиотеки

Требования к именованию

Макросы тестирования функциональности (C++20)

Поддержка языка

Библиотека концептов (C++20)

Библиотека метапрограммирования (C++11)

Библиотека диагностики

Библиотека общих утилит

Библиотека строк

Библиотека контейнеров

Библиотека итераторов

Библиотека диапазонов (C++20)

Библиотека алгоритмов

Библиотека численных данных

Библиотека ввода/вывода

Библиотека локализаций

Регулярные выражения (C++11)

Атомарные операции (C++11)

Библиотека поддержки конкуренции (C++11)

Библиотека файловой системы (C++17)

Технические спецификации

Указатель символов

Внешние библиотеки

 

Библиотека контейнеров

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

array (C++11)

vector

vector<bool>

deque

forward_list (C++11)

list

Ассоциативные

set

multiset

map

multimap

Неупорядоченные ассоциативные

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

Адаптеры

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

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

span (C++20)

mdspan (C++23)

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

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

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

 

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

• последовательные контейнеры,
• ассоциативные контейнеры, и

неупорядоченные ассоциативные контейнеры,

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

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

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

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

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

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

array (начиная с C++11)	статический непрерывный массив (шаблон класса)
vector	динамический непрерывный массив (шаблон класса)
deque	двусторонняя очередь (шаблон класса)
forward_list (начиная с C++11)	односвязный список (шаблон класса)
list	двусвязный список (шаблон класса)

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

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

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

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

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

unordered_set (начиная с C++11)	коллекция уникальных ключей, хэшированная по ключам (шаблон класса)
unordered_map (начиная с C++11)	коллекция пар ключ-значение, хэшированная по ключам, ключи уникальны (шаблон класса)
unordered_multiset (начиная с C++11)	коллекция ключей, хэшированная по ключам (шаблон класса)
unordered_multimap (начиная с C++11)	коллекция пар ключ-значение, хешированных по ключам (шаблон класса)

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

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

stack	адаптирует контейнер для предоставления стека (структура данных LIFO) (шаблон класса)
queue	адаптирует контейнер для предоставления очереди (структура данных FIFO) (шаблон класса)
priority_queue	адаптирует контейнер для предоставления очереди с приоритетами (шаблон класса)
flat_set (C++23)	адаптирует контейнер для предоставления набора уникальных ключей, отсортированных по ключам (шаблон класса)
flat_map (C++23)	адаптирует два контейнера для предоставления набора пар ключ-значение, отсортированных по уникальным ключам (шаблон класса)
flat_multiset (C++23)	адаптирует контейнер для предоставления набора ключей, отсортированных по ключам (шаблон класса)
flat_multimap (C++23)	адаптирует два контейнера для предоставления набора пар ключ-значение, отсортированных по ключам (шаблон класса)

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

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

span (C++20)	не владеющее представление непрерывной последовательности объектов (шаблон класса)
mdspan (C++23)	многомерное представление массива без владения (шаблон класса)

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

span(начиная с C++20) и mdspan(начиная с 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 это стирание, которое удаляет первый элемент, но не последний.

Безопасность потоков Все функции контейнеров могут вызываться одновременно разными потоками. В более общем смысле, функции стандартной библиотеки 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 не рассматривается стандартом как контейнер, но ведет себя так же из-за своего сходства. Для удобства он указан здесь как 'Псевдоконтейнер'.

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

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

		Псевдоконтейнеры	Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адаптеры контейнеров
Заголовок		<string>	<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>		<flat_set>		<flat_map>		Заголовок
Контейнер		basic_string	array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue	flat_set	flat_multiset	flat_map	flat_multimap	Контейнер
	(конструктор)	basic_string	(неявный)	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue	flat_set	flat_multiset	flat_map	flat_multimap	(конструктор)
	(деструктор)	~basic_string	(неявный)	~vector	~deque	~forward_list	~list	~set	~multiset	~map	~multimap	~unordered_set	~unordered_multiset	~unordered_map	~unordered_multimap	~stack	~queue	~priority_queue	~flat_set	~flat_multiset	~flat_map	~flat_multimap	(деструктор)
	operator=	operator=	(неявный)	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=
	assign	assign		assign	assign	assign	assign																assign
	assign_range	assign_range		assign_range	assign_range	assign_range	assign_range																assign_range
Итераторы	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin				begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	Итераторы
	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend				end cend	end cend	end cend	end cend	end cend
	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin		rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin								rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin
	rend crend	rend crend	rend crend	rend crend	rend crend		rend crend	rend crend	rend crend	rend crend	rend crend								rend crend	rend crend	rend crend	rend crend	rend crend
Доступ к элементу	at	at	at	at	at					at				at							at		at	Доступ к элементу
	operator[]	operator[]	operator[]	operator[]	operator[]					operator[]				operator[]							operator[]		operator[]
	data	data	data	data																			data
	front	front	front	front	front	front	front										front	top					front
	back	back	back	back	back		back									top	back						back
Вместимость	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	Вместимость
	size	size	size	size	size		size	size	size	size	size	size	size	size	size	size	size	size	size	size	size	size	size
	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size				max_size	max_size	max_size	max_size	max_size
	resize	resize		resize	resize	resize	resize																resize
	capacity	capacity		capacity																			capacity
	reserve	reserve		reserve								reserve	reserve	reserve	reserve								reserve
	shrink_to_fit	shrink_to_fit		shrink_to_fit	shrink_to_fit																		shrink_to_fit
Модификаторы	clear	clear		clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear				clear	clear	clear	clear	clear	Модификаторы
	insert	insert		insert	insert	insert_after	insert	insert	insert	insert	insert	insert	insert	insert	insert				insert	insert	insert	insert	insert
	insert_range	insert_range		insert_range	insert_range	insert_range_after	insert_range	insert_range	insert_range	insert_range	insert_range	insert_range	insert_range	insert_range	insert_range				insert_range	insert_range	insert_range	insert_range	insert_range
	insert_or_assign									insert_or_assign				insert_or_assign							insert_or_assign		insert_or_assign
	emplace			emplace	emplace	emplace_after	emplace	emplace	emplace	emplace	emplace	emplace	emplace	emplace	emplace				emplace	emplace	emplace	emplace	emplace
	emplace_hint							emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint				emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint
	try_emplace									try_emplace				try_emplace							try_emplace		try_emplace
	erase	erase		erase	erase	erase_after	erase	erase	erase	erase	erase	erase	erase	erase	erase				erase	erase	erase	erase	erase
	push_front				push_front	push_front	push_front																push_front
	prepend_range				prepend_range	prepend_range	prepend_range																prepend_range
	emplace_front				emplace_front	emplace_front	emplace_front																emplace_front
	pop_front				pop_front	pop_front	pop_front										pop	pop					pop_front
	push_back	push_back		push_back	push_back		push_back									push	push	push					push_back
	append_range	append_range		append_range	append_range		append_range									push_range	push_range	push_range					append_range
	emplace_back			emplace_back	emplace_back		emplace_back									emplace	emplace	emplace					emplace_back
	pop_back	pop_back		pop_back	pop_back		pop_back									pop							pop_back
	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap
	merge					merge	merge	merge	merge	merge	merge	merge	merge	merge	merge								merge
	extract							extract	extract	extract	extract	extract	extract	extract	extract								extract
Операции со списком	splice					splice_after	splice																splice	Операции со списком
	remove					remove	remove																remove
	remove_if					remove_if	remove_if																remove_if
	reverse					reverse	reverse																reverse
	unique					unique	unique																unique
	sort					sort	sort																sort
Сигмент и Хэш	begin(size_type) cbegin(size_type)											begin(size_type) cbegin(size_type)	begin(size_type) cbegin(size_type)	begin(size_type) cbegin(size_type)	begin(size_type) cbegin(size_type)								begin(size_type) cbegin(size_type)	Сигмент и Хэш
	end(size_type) cend(size_type)											end(size_type) cend(size_type)	end(size_type) cend(size_type)	end(size_type) cend(size_type)	end(size_type) cend(size_type)								end(size_type) cend(size_type)
	bucket_count											bucket_count	bucket_count	bucket_count	bucket_count								bucket_count
	max_bucket_count											max_bucket_count	max_bucket_count	max_bucket_count	max_bucket_count								max_bucket_count
	bucket_size											bucket_size	bucket_size	bucket_size	bucket_size								bucket_size
	bucket											bucket	bucket	bucket	bucket								bucket
	load_factor											load_factor	load_factor	load_factor	load_factor								load_factor
	max_load_factor											max_load_factor	max_load_factor	max_load_factor	max_load_factor								max_load_factor
	rehash											rehash	rehash	rehash	rehash								rehash
Поиск	count							count	count	count	count	count	count	count	count				count	count	count	count	count	Поиск
	find	find						find	find	find	find	find	find	find	find				find	find	find	find	find
	contains	contains						contains	contains	contains	contains	contains	contains	contains	contains				contains	contains	contains	contains	contains
	lower_bound							lower_bound	lower_bound	lower_bound	lower_bound								lower_bound	lower_bound	lower_bound	lower_bound	lower_bound
	upper_bound							upper_bound	upper_bound	upper_bound	upper_bound								upper_bound	upper_bound	upper_bound	upper_bound	upper_bound
	equal_range							equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range				equal_range	equal_range	equal_range	equal_range	equal_range
Наблюдатели	key_comp							key_comp	key_comp	key_comp	key_comp								key_comp	key_comp	key_comp	key_comp	key_comp	Наблюдатели
	value_comp							value_comp	value_comp	value_comp	value_comp								value_comp	value_comp	value_comp	value_comp	value_comp
	hash_function											hash_function	hash_function	hash_function	hash_function								hash_function
	key_eq											key_eq	key_eq	key_eq	key_eq								key_eq
Allocator	get_allocator	get_allocator		get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator								get_allocator	Allocator
Адаптеры	extract																		extract	extract	extract	extract	extract	Адаптеры
	replace																		replace	replace	replace	replace	replace
Контейнер		basic_string	array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue	flat_set	flat_multiset	flat_map	flat_multimap	Контейнер
Заголовок		<string>	<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>		<flat_set>		<flat_map>		Заголовок
		Псевдоконтейнер	Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адаптеры для контейнеров

• Примечание: функции в двух разных строках extract имеют разные значения и синтаксис:

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

		Псевдоконтейнер	Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адаптеры контейнеров
Заголовок		<string>	<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>		<flat_set>		<flat_map>		Заголовок
Контейнер		basic_string	array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue	flat_set	flat_multiset	flat_map	flat_multimap	Контейнер
Функция, не являющаяся элементом	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==	operator==		operator==	operator==	operator==	operator==	operator==	Функция, не являющаяся элементом
	operator!= (удалено в C++20)	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=	operator!=						operator!= (удалено в C++20)
	operator< (удалено в C++20)	operator<	operator<	operator<	operator<	operator<	operator<	operator<	operator<	operator<	operator<					operator<	operator<						operator< (удалено в C++20)
	operator<= (удалено в C++20)	operator<=	operator<=	operator<=	operator<=	operator<=	operator<=	operator<=	operator<=	operator<=	operator<=					operator<=	operator<=						operator<= (удалено в C++20)
	operator> (удалено в C++20)	operator>	operator>	operator>	operator>	operator>	operator>	operator>	operator>	operator>	operator>					operator>	operator>						operator> (удалено в C++20)
	operator>= (удалено в C++20)	operator>=	operator>=	operator>=	operator>=	operator>=	operator>=	operator>=	operator>=	operator>=	operator>=					operator>=	operator>=						operator>= (удалено в C++20)
	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>	operator<=>					operator<=>	operator<=>		operator<=>	operator<=>	operator<=>	operator<=>	operator<=>
	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap
	erase	erase		erase	erase	erase	erase																erase
	erase_if	erase_if		erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if	erase_if				erase_if	erase_if	erase_if	erase_if	erase_if
Контейнер		basic_string	array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue	flat_set	flat_multiset	flat_map	flat_multimap	Контейнер
Заголовок		<string>	<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>		<flat_set>		<flat_map>		Заголовок
		Псевдоконтейнер	Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адаптеры контейнеров

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

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

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

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

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

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

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

• Container
• SequenceContainer
• ContiguousContainer
• ReversibleContainer
• AssociativeContainer
• AllocatorAwareContainer
• UnorderedAssociativeContainer

valarray	числовые массивы, маски массивов и срезы массивов (шаблон класса)
basic_string	хранит и управляет последовательностями символов (шаблон класса)
basic_string_view (C++17)	строковое представление только для чтения (шаблон класса)