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

AssociativeContainer — это упорядоченный контейнер, обеспечивающий быстрый поиск объектов по ключам.

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

Требования

Обозначения
`X`	Класс ассоциативного контейнера
`T`	Тип элемента `X`
`A`	Тип аллокатора `X`: `X::allocator_type`, если он существует, иначе std::allocator<X::value_type>
`a`	Значение типа `X`
`a2`	Значение типа `Y`, совместимого по узловым дескрипторам с `X`
`b`	Значение типа `X` или constX
`u`	Имя объявляемой переменной
`a_uniq`	Значение типа `X`, если `X` поддерживает уникальные ключи
`a_eq`	Значение типа `X`, если `X` поддерживает эквивалентные ключи
`a_tran`	Значение типа `X` или constX, если существует тип `X::key_compare::is_transparent`
`i`, `j`	LegacyInputIterators, указывающие на элементы, неявно преобразуемые в `X::value_type`
`[i,` `j)`	Допустимый диапазон
`rg` (начиная с C++23)	Значение типа `R`, моделирующего `container-compatible-range<value_type>`
`p`	Допустимый константный итератор для `a`
`q`	Допустимый разыменовываемый константный итератор для `a`
`r`	Допустимый разыменовываемый итератор для `a`
`q1`, `q2`	Допустимый диапазон константных итераторов в `a`
`il`	Объект типа std::initializer_list<X::value_type>
`t`	Значение типа `X::value_type`
`k`	Значение типа `X::key_type`
`c`	Значение типа `X::key_compare` или constX::key_compare
`kl`	Значение, такое что `a` разбито на разделы относительно `c(x, kl)`, где `x` — значение ключа `e`, а `e` находится в `a`
`ku`	Значение, такое что `a` разбито на разделы относительно `!c(ku, x)`, где `x` — значение ключа `e`, а `e` находится в `a`
`ke`	Значение, такое что `a` разбито на разделы относительно `c(x, ke)` и `!c(ke, x)`, причем `c(x, ke)` влечет `!c(ke, x)`, а `x` является значением ключа `e` и `e` в `a`
`kx` (начиная с C++23)	Значение, такое что: `a` разбито на разделы относительно `c(x, kx)` и `!c(kx, x)`, причем `c(x, kx)` влечет `!c(kx, x)`, а `x` является значением ключа `e` и `e` в `a`, и `kx` не преобразуется ни в `X::iterator`, ни в `X::const_iterator`
`m`	Аллокатор типа, преобразуемого в `A`
`nh`	Неконстантное rvalue типа `X::node_type`

Тип X удовлетворяет требованиям AssociativeContainer, если

Тип X удовлетворяет требованиям Container(до C++11)AllocatorAwareContainer(начиная с C++11),
Параметризован типом Key и отношением порядка Compare, задающим строгий слабый порядок для элементов Key, причем
- Кроме того, std::map и std::multimap связывают произвольный тип отображаемого значения T с Key.
- Объект типа Compare называется объектом сравнения контейнера типа X.
Следующие выражения должны быть корректны и иметь указанные эффекты для всех ассоциативных контейнеров:

Типы

Имя	Тип	Требования
`key_type`	`Key`
`mapped_type`	`T` (только для `std::map` и `std::multimap`)
`value_type`	`Key` (только для `std::set` и `std::multiset`) std::pair<constKey,T>(только для `std::map` и `std::multimap`)	Erasable из `X`
`key_compare`	`Compare`	CopyConstructible
`value_compare`	совпадает с `key_compare` (для `std::set` и `std::multiset`) отношение порядка на парах, задаваемое первым компонентом (то есть `Key`) (для `std::map` и `std::multimap`)	BinaryPredicate
`node_type`	Специализация шаблона класса узлового дескриптора, в которой открытые вложенные типы совпадают с соответствующими типами в `X`.

Функции-члены и операторы

Выражение	Результат	Предварительные условия	Эффекты	Возвращаемое значение	Сложность
`X(c)`			Создаёт пустой контейнер. Использует копию `c` в качестве объекта сравнения		Постоянная
`X u = X();` `X u;`		`key_compare` удовлетворяет требованиям DefaultConstructible	Создаёт пустой контейнер. Использует `Compare()` в качестве объекта сравнения		Постоянная
`X(i, j, c)`		`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*i`	Создаёт пустой контейнер и вставляет в него элементы из диапазона `[i,` `j)`; использует `c` в качестве объекта сравнения		`N·log(N)` в общем случае, где `N` имеет значение `std::distance(i, j)`; линейная, если `[i,` `j)` отсортирован относительно `value_comp()`
`X(i, j)`		`key_compare` удовлетворяет требованиям DefaultConstructible. `value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*i`	Создаёт пустой контейнер и вставляет в него элементы из диапазона `[i,` `j)`; использует `Compare()` в качестве объекта сравнения
`X(from_range, rg, c)` (начиная с C++23)		`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*ranges::begin(rg)`	Создаёт пустой контейнер и вставляет в него каждый элемент из `rg`. Использует `c` в качестве объекта сравнения		`N·log(N)` в общем случае, где `N` имеет значение `ranges::distance(rg)`; линейная, если `rg` отсортирован относительно `value_comp()`
`X(from_range, rg)` (начиная с C++23)		`key_compare` удовлетворяет требованиям DefaultConstructible. `value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*ranges::begin(rg)`	Создаёт пустой контейнер и вставляет в него каждый элемент из `rg`. Использует `Compare()` в качестве объекта сравнения
`X(il, c)`			`X(il.begin(), il.end(), c)`
`X(il)`			`X(il.begin(), il.end())`
`a = il`	`X&`	`value_type` удовлетворяет требованиям CopyInsertable для создания в `X` и CopyAssignable	Присваивает диапазон `[il.begin(),` `il.end())` контейнеру `a`. Всем существующим элементам `a` либо присваиваются новые значения, либо они уничтожаются		`N·log(N)` в общем случае, где `N` имеет значение `il.size() + a.size()`; линейная, если `[il.begin(),` `il.end())` отсортирован относительно `value_comp()`
`b.key_comp()`	`X::key_compare`			Объект сравнения, из которого был создан `b`	Постоянная
`b.value_comp()`	`X::value_compare`			Объект типа `value_compare`, созданный из объекта сравнения	Постоянная
`a_uniq.emplace(args)`	`std::pair<iterator,bool>`	`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `args`	Вставляет объект `value_type`, созданный с помощью `std::forward<Args>(args)...`, в позицию `t` тогда и только тогда, когда в контейнере нет элемента с ключом, эквивалентным ключу `t`	Компонент bool возвращаемой пары равен `true` тогда и только тогда, когда произошла вставка, а компонент-итератор пары указывает на элемент с ключом, эквивалентным ключу `t`	Логарифмическая
`a_eq.emplace(args)`	`iterator`	`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `args`	Вставляет объект `value_type`, созданный с помощью `std::forward<Args>(args)...`, в позицию `t`. Если в `a_eq` есть диапазон, содержащий элементы, эквивалентные `t`, `t` вставляется в конец этого диапазона	Итератор, указывающий на только что вставленный элемент	Логарифмическая
`a.emplace_hint(p, args)`	`iterator`		Эквивалентно `a.emplace(std::forward<Args>(args)...)`, за исключением того, что элемент вставляется как можно ближе к позиции непосредственно перед `p`	Итератор, указывающий на элемент с ключом, эквивалентным ключу только что вставленного элемента	В общем случае логарифмическая, но амортизированная постоянная, если элемент вставляется непосредственно перед `p`
`a_uniq.insert(t)`	`std::pair<iterator,bool>`	Если `t` — неконстантное rvalue-значение, `value_type` удовлетворяет требованиям MoveInsertable для создания в `X`; в противном случае `value_type` удовлетворяет требованиям CopyInsertable для создания в `X`	Вставляет `t` тогда и только тогда, когда в контейнере нет элемента с ключом, эквивалентным ключу `t`	Компонент bool возвращаемой пары равен `true` тогда и только тогда, когда произошла вставка, а компонент `iterator` пары указывает на элемент с ключом, эквивалентным ключу `t`	Логарифмическая
`a_eq.insert(t)`	`iterator`	Если `t` — неконстантное rvalue-значение, `value_type` удовлетворяет требованиям MoveInsertable для создания в `X`; в противном случае `value_type` удовлетворяет требованиям CopyInsertable для создания в `X`	Вставляет `t` и возвращает итератор, указывающий на только что вставленный элемент. Если в `a_eq` есть диапазон, содержащий элементы, эквивалентные `t`, `t` вставляется в конец этого диапазона		Логарифмическая
`a.insert(p, t)`	`iterator`	Если `t` — неконстантное rvalue-значение, `value_type` удовлетворяет требованиям MoveInsertable для создания в `X`; в противном случае `value_type` удовлетворяет требованиям CopyInsertable для создания в `X`	Вставляет `t` тогда и только тогда, когда в контейнерах с уникальными ключами нет элемента с ключом, эквивалентным ключу `t`; в контейнерах с эквивалентными ключами всегда вставляет `t`. `t` вставляется как можно ближе к позиции непосредственно перед `p`	Итератор, указывающий на элемент с ключом, эквивалентным ключу `t`	В общем случае логарифмическая, но амортизированная постоянная, если `t` вставляется непосредственно перед `p`
`a.insert(i, j)`	void	`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*i`. Ни `i`, ни `j` не являются итераторами в `a`	Вставляет каждый элемент из диапазона `[i,` `j)` тогда и только тогда, когда в контейнерах с уникальными ключами нет элемента с ключом, эквивалентным ключу этого элемента; в контейнерах с эквивалентными ключами всегда вставляет этот элемент		`N·log(a.size() + N)`, где `N` имеет значение `std::distance(i, j)`
`a.insert_range(rg)` (начиная с C++23)	void	`value_type` удовлетворяет требованиям EmplaceConstructible для создания в `X` из `*ranges::begin(rg)`. `rg` и `a` не пересекаются	Вставляет каждый элемент из `rg` тогда и только тогда, когда в контейнерах с уникальными ключами нет элемента с ключом, эквивалентным ключу этого элемента; в контейнерах с эквивалентными ключами всегда вставляет этот элемент		`N·log(a.size() + N)`, где `N` имеет значение `ranges::distance(rg)`
`a.insert(il)`			`a.insert(il.begin(), il.end())`
`a_uniq.insert(nh)`	`insert_return_type`	`nh` пуст или `a_uniq.get_allocator()==nh.get_allocator()` равен `true`	Если `nh` пуст, ничего не делает. В противном случае вставляет элемент, принадлежащий `nh`, тогда и только тогда, когда в контейнере нет элемента с ключом, эквивалентным `nh.key()`	Если `nh` пуст, `inserted` равен `false`, `position` равен `end()`, а `node` пуст. В противном случае, если вставка выполнена, `inserted` равен `true`, `position` указывает на вставленный элемент, а `node` пуст; если вставка не выполнена, `inserted` равен `false`, `node` имеет предыдущее значение `nh`, а `position` указывает на элемент с ключом, эквивалентным `nh.key()`	Логарифмическая
`a_eq.insert(nh)`	`iterator`	`nh` пуст или `a_eq.get_allocator()==nh.get_allocator()` равен `true`	Если `nh` пуст, ничего не делает и возвращает `a_eq.end()`. В противном случае вставляет элемент, принадлежащий `nh`, и возвращает итератор, указывающий на только что вставленный элемент. Если в `a_eq` есть диапазон, содержащий элементы с ключами, эквивалентными `nh.key()`, элемент вставляется в конец этого диапазона. Гарантируется: `nh` пуст		Логарифмическая
`a.insert(p, nh)`	`iterator`	`nh` пуст или `a.get_allocator()==nh.get_allocator()` равен `true`	Если `nh` пуст, ничего не делает и возвращает `a.end()`. В противном случае вставляет элемент, принадлежащий `nh`, тогда и только тогда, когда в контейнерах с уникальными ключами нет элемента с ключом, эквивалентным `nh.key()`; в контейнерах с эквивалентными ключами всегда вставляет элемент, принадлежащий `nh`. Элемент вставляется как можно ближе к позиции непосредственно перед `p`. Гарантируется: `nh` пуст, если вставка выполнена, и не изменён, если вставка не выполнена	Итератор, указывающий на элемент с ключом, эквивалентным `nh.key()`	В общем случае логарифмическая, но амортизированная постоянная, если элемент вставляется непосредственно перед `p`
`a.extract(k)`	`node_type`		Удаляет первый элемент контейнера с ключом, эквивалентным `k`	Объект `node_type`, владеющий элементом, если он найден; в противном случае — пустой `node_type`	`log(a.size())`
`a_tran.extract(kx)` (начиная с C++23)	`node_type`		Удаляет первый элемент контейнера с ключом `r`, для которого `!c(r, kx) && !c(kx, r)` равен `true`	Объект `node_type`, владеющий элементом, если он найден; в противном случае — пустой `node_type`	`log(a_tran.size())`
`a.extract(q)`	`node_type`		Удаляет элемент, на который указывает `q`	Объект `node_type`, владеющий этим элементом	Амортизированная постоянная
`a.merge(a2)`	void	`a.get_allocator()==a2.get_allocator()`	Пытается извлечь каждый элемент из `a2` и вставить его в `a`, используя объект сравнения `a`. В контейнерах с уникальными ключами, если в `a` есть элемент с ключом, эквивалентным ключу элемента из `a2`, этот элемент не извлекается из `a2`. Гарантируется: указатели и ссылки на перемещённые элементы `a2` указывают на те же элементы, но уже как на элементы `a`. Итераторы, ссылающиеся на перемещённые элементы, продолжат ссылаться на них, но теперь они являются итераторами в `a`, а не в `a2`. Исключения: отсутствуют, если только объект сравнения не выбрасывает исключение		`N·log(a.size() + N)`, где `N` имеет значение `a2.size()`
`a.erase(k)`	`size_type`		Удаляет все элементы контейнера с ключом, эквивалентным `k`	Количество удалённых элементов	`log(a.size())+ a.count(k)`
`a_tran.erase(kx)` (начиная с C++23)	`size_type`		Удаляет все элементы контейнера с ключом `r`, для которых `!c(r, kx) && !c(kx, r)` равен `true`	Количество удалённых элементов	`log(a_tran.size())+ a_tran.count(kx)`
`a.erase(q)`	`iterator`		Удаляет элемент, на который указывает `q`	Итератор, указывающий на элемент, который следовал непосредственно за `q` до удаления элемента. Если такого элемента нет, возвращает `a.end()`	Амортизированная постоянная
`a.erase(r)`	`iterator`		Удаляет элемент, на который указывает `r`	Итератор, указывающий на элемент, который следовал непосредственно за `r` до удаления элемента. Если такого элемента нет, возвращает `a.end()`	Амортизированная постоянная
`a.erase(q1, q2)`	`iterator`		Удаляет все элементы диапазона `[q1,` `q2)`	Итератор, указывающий на элемент, на который указывал `q2` до удаления каких-либо элементов. Если такого элемента нет, возвращается `a.end()`	`log(a.size()) + N`, где `N` имеет значение `std::distance(q1, q2)`
`a.clear()`			`a.erase(a.begin(), a.end())`. Гарантируется: `a.empty()` равен `true`		Линейная по `a.size()`
`b.find(k)`	`iterator`; `const_iterator` для константного `b`			Итератор, указывающий на элемент с ключом, эквивалентным `k`, или `b.end()`, если такой элемент не найден	Логарифмическая
`a_tran.find(ke)`	`iterator`; `const_iterator` для константного `a_tran`			Итератор, указывающий на элемент с ключом `r`, для которого `!c(r, ke) &&!c(ke, r)` равен `true`, или `a_tran.end()`, если такой элемент не найден	Логарифмическая
`b.count(k)`	`size_type`			Количество элементов с ключом, эквивалентным `k`	`log(b.size())+ b.count(k)`
`a_tran.count(ke)`	`size_type`			Количество элементов с ключом `r`, для которых `!c(r, ke) &&!c(ke, r)`	`log(a_tran.size())+ a_tran.count(ke)`
`b.contains(k)`	bool		`return b.find(k) != b.end();`
`a_tran.contains(ke)`	bool		`returna_tran.find(ke) !=a_tran.end();`
`b.lower_bound(k)`	`iterator`; `const_iterator` для константного `b`			Итератор, указывающий на первый элемент с ключом, не меньшим `k`, или `b.end()`, если такой элемент не найден	Логарифмическая
`a_tran.lower_bound(kl)`	`iterator`; `const_iterator` для константного `a_tran`			Итератор, указывающий на первый элемент с ключом `r`, для которого `!c(r, kl)`, или `a_tran.end()`, если такой элемент не найден	Логарифмическая
`b.upper_bound(k)`	`iterator`; `const_iterator` для константного `b`			Итератор, указывающий на первый элемент с ключом, большим `k`, или `b.end()`, если такой элемент не найден	Логарифмическая
`a_tran.upper_bound(ku)`	`iterator`; `const_iterator` для константного `a_tran`			Итератор, указывающий на первый элемент с ключом `r`, для которого `c(ku, r)`, или `a_tran.end()`, если такой элемент не найден	Логарифмическая
`b.equal_range(k)`	`std::pair<iterator,iterator>`; `std::pair<const_iterator,const_iterator>` для константного `b`		Эквивалентно: `returnstd::make_pair(b.lower_bound(k),b.upper_bound(k));`		Логарифмическая
`a_tran.equal_range(ke)`	`std::pair<iterator,iterator>`; `std::pair<const_iterator,const_iterator>` для константного `a_tran`		Эквивалентно: `returnstd::make_pair(a_tran.lower_bound(ke),a_tran.upper_bound(ke));`		Логарифмическая

Итераторы

Итераторы ассоциативных контейнеров удовлетворяют требованиям LegacyBidirectionalIterator.

Для ассоциативных контейнеров, в которых value_type совпадает с key_type, и iterator, и const_iterator являются константными итераторами. Не определено, являются ли iterator и const_iterator типами одного и того же типа.

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

a — ассоциативный контейнер
i и j — разыменовываемые итераторы в a.

Если расстояние от i до j положительно, то a.value_comp()(*j, *i) == false. Кроме того, если a — ассоциативный контейнер с уникальными ключами, выполняется более строгое условие a.value_comp()(*i, *j) != false.

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

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

set	коллекция уникальных ключей, упорядоченных по ключам (шаблон класса)
multiset	коллекция ключей, упорядоченных по ключам (шаблон класса)
map	коллекция пар «ключ — значение», упорядоченных по ключам; ключи уникальны (шаблон класса)
multimap	коллекция пар «ключ — значение», упорядоченных по ключам (шаблон класса)

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

Отчёт об ошибке	Применён к	Опубликованное поведение	Правильное поведение
LWG 354	C++98	`lower_bound` и `upper_bound` не возвращали конечный итератор, если элемент не найден	в этом случае они возвращают конечный итератор
LWG 589	C++98	элементы, на которые ссылались `i` и `j`, имели тип `X::value_type`	элементы неявно преобразуются в `X::value_type`

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/named_req/AssociativeContainer