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

An AssociativeContainer is an ordered Container that provides fast lookup of objects based on keys.

An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys.

Требования

Легенда
`X`	Класс ассоциативного контейнера
`T`	Тип элемента `X`
`A`	Тип аллокатора `X`: `X::allocator_type` если он существует, иначе std::allocator<X::value_type>
`a`	Значение типа `X`
`a2`	Значение типа `Y`, чьи дескрипторы узлов совместимы с `X`
`b`	Значение типа `X` или const X
`u`	Имя переменной, подлежащей объявлению
`a_uniq`	Значение типа `X` при `X` поддерживает уникальные ключи
`a_eq`	Значение типа `X` при `X` поддерживает эквивалентные ключи
`a_tran`	Значение типа `X` или const X, если тип `X::key_compare::is_transparent` существует
`i`, `j`	Легаси-итераторы ссылаящиеся на элементы неявно преобразуемые в `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` или const X::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<const Key, T>(только для `std::map` и `std::multimap` )	Удаляемый из `X`
`key_compare`	`Compare`	Копируемый
`value_compare`	такой же, как `key_compare` (для `std::set` и `std::multiset`) отношение порядка на парах, индуцированное первой компонентой (т.е. `Key`) (для `std::map` и `std::multimap`)	Бинарное отношение
`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` `t`, созданный с помощью `std::forward<Args>(args)...`, только если в контейнере нет элемента с ключом, эквивалентным ключу `t`	Компонент `bool` возвращаемой пары — `true`, если вставка выполнена, и итератор компоненты пары указывает на элемент с ключом, эквивалентным ключу `t`	Логарифмическая
`a_eq.emplace(args)`	`iterator`	`value_type` является EmplaceConstructible в `X` из `args`.	Вставляет объект `value_type` `t`, созданный с помощью `std::forward<Args>(args)...`. Если диапазон, содержащий элементы, эквивалентные `t`, существует в `a_eq`, `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` и возвращает итератор, указывающий на новый вставленный элемент. Если диапазон, содержащий элементы, эквивалентные `t`, существует в `a_eq`, `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())`

END_OF_DOCUMENT_MARKER

`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`		`return a_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`		Эквивалентно: `return std::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`		Эквивалентно: `return std::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.

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

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

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

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

DR	Применен к	Поведение при публикации	Правильное поведение
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/w/cpp/named_req/AssociativeContainer