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

 

C++

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

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

Язык

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

array (C++11)

vector

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

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

span (C++20)

 

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

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

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

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

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

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

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

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

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

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

Неупорядоченные ассоциативные контейнеры реализуют неупорядоченные (хешированные) структуры данных с возможностью быстрого поиска (со средней сложностью 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	адаптирует контейнер для предоставления очереди с приоритетами (шаблон класса)

span

span это не принадлежащее владельцу представление непрерывной последовательности объектов, память которых принадлежит другому объекту.

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

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

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

Категория	Контейнер	После вставки...		После стирания...		Условие
		итераторы действительны?	ссылки действительны?	итераторы действительны?	ссылки действительны?
Последовательные контейнеры	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.

• Примеры методов стирания: std::set::erase, std::vector::pop_back, std::deque::pop_front и std::map::clear.
  • 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 может получать значения из нескольких потоков). Операции над итератором (например, инкремент итератора) читают, но не изменяют базовый контейнер, и могут выполняться одновременно с операциями над другими итераторами в том же контейнере, с константными функциями-элементами, или читать из элементов. Операции над контейнером, которые делают недействительными любые итераторы, изменяют контейнер и не могут выполняться одновременно с любыми операциями над существующими итераторами, даже если эти итераторы действительны. Элементы одного и того же контейнера можно изменять одновременно с теми функциями-элементами, которые не получают доступ к этим элементам. В более общем плане функции стандартной библиотеки C++ не читают объекты, косвенно доступные через их аргументы (включая другие элементы контейнера), за исключением случаев, когда этого требует спецификация контейнера. В любом случае контейнерные операции (а также алгоритмы или любые другие стандартные библиотечные функции C++) могут быть распараллелены внутренне, если это не меняет видимые для пользователя результаты (например, std::transform может быть распараллелена, но не std::for_each, которая проходит каждый элемент последовательности по порядку)).

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

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

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

		Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адапторы контейнеров
Заголовок		<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>
Контейнер		array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
	(конструктор)	(неявный)	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
	(деструктор)	(неявный)	~vector	~deque	~forward_list	~list	~set	~multiset	~map	~multimap	~unordered_set	~unordered_multiset	~unordered_map	~unordered_multimap	~stack	~queue	~priority_queue
	operator=	(неявный)	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=
	assign		assign	assign	assign	assign
Итераторы	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
	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
Доступ к элементу	at	at	at	at					at				at
	operator[]	operator[]	operator[]	operator[]					operator[]				operator[]
	data	data	data
	front	front	front	front	front	front										front	top
	back	back	back	back		back									top	back
Ёмкость	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
	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
	capacity		capacity								bucket_count	bucket_count	bucket_count	bucket_count
	reserve		reserve								reserve	reserve	reserve	reserve
	shrink_to_fit		shrink_to_fit	shrink_to_fit
Модификаторы	clear		clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear
	insert		insert	insert	insert_after	insert	insert	insert	insert	insert	insert	insert	insert	insert
	insert_or_assign								insert_or_assign				insert_or_assign
	emplace		emplace	emplace	emplace_after	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
	try_emplace								try_emplace				try_emplace
	erase		erase	erase	erase_after	erase	erase	erase	erase	erase	erase	erase	erase	erase
	push_front			push_front	push_front	push_front
	emplace_front			emplace_front	emplace_front	emplace_front
	pop_front			pop_front	pop_front	pop_front										pop	pop
	push_back		push_back	push_back		push_back									push	push	push
	emplace_back		emplace_back	emplace_back		emplace_back									emplace	emplace	emplace
	pop_back		pop_back	pop_back		pop_back									pop
	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
	extract						extract	extract	extract	extract	extract	extract	extract	extract
Операции со списком	splice				splice_after	splice
	remove				remove	remove
	remove_if				remove_if	remove_if
	reverse				reverse	reverse
	unique				unique	unique
	sort				sort	sort
Просмотр	count						count	count	count	count	count	count	count	count
	find						find	find	find	find	find	find	find	find
	contains						contains	contains	contains	contains	contains	contains	contains	contains
	lower_bound						lower_bound	lower_bound	lower_bound	lower_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
Наблюдатели	key_comp						key_comp	key_comp	key_comp	key_comp
	value_comp						value_comp	value_comp	value_comp	value_comp
	hash_function										hash_function	hash_function	hash_function	hash_function
	key_eq										key_eq	key_eq	key_eq	key_eq
Аллокатор	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
Контейнер		array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
		Последовательные контейнеры					Ассоциативные контейнеры				Неупорядоченные ассоциативные контейнеры				Адапторы контейнеров

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

Документация по C++ для Требования по именованию C++: Контейнер