Namespaces
Variants

C++ named requirements: AssociativeContainer

From cppreference.net
C++
C++ named requirements

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

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

Содержание

Требования

Легенда
X Класс ассоциативного контейнера
T Тип элемента X
A Тип аллокатора для X : X::allocator_type если существует, иначе std:: allocator < X :: value_type >
a Значение типа X
a2 Значение типа Y , чьи node handles совместимы с 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 Итераторы LegacyInputIterator , ссылающиеся на элементы, неявно преобразуемые в 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 Erasable из X
key_compare Compare CopyConstructible
value_compare BinaryPredicate
node_type Специализация шаблона класса node-handle , такая что публичные вложенные типы совпадают с соответствующими типами в X .

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

**Примечание:** В данном HTML-фрагменте весь текст внутри тегов ` ` является кодом C++, который согласно инструкциям не подлежит переводу. Вне этих тегов отсутствует какой-либо текст для перевода. HTML-разметка полностью сохранена в оригинальном формате.
Выражение Результат Предусловия Эффекты Возвращает Сложность
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 ) ... . Если в 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

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 .

Этот раздел не завершён
Причина: Завершить требования.

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

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

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

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

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

DR Applied to Behavior as published Correct behavior
LWG 354 C++98 lower_bound и upper_bound не
возвращали конечный итератор, если элемент не найден 		они возвращают конечный
итератор в этом случае
LWG 589 C++98 элементы, на которые ссылаются i и j
имели тип X::value_type 		элементы неявно
конвертируемы в X::value_type