Namespaces
Variants

C++ named requirements: AssociativeContainer

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

Un AssociativeContainer es un Container ordenado que proporciona búsqueda rápida de objetos basada en claves.

Un contenedor asociativo admite claves únicas si puede contener como máximo un elemento por cada clave. De lo contrario, admite claves equivalentes .

Contenidos

Requisitos

Leyenda
X Una clase de contenedor asociativo
T El tipo de elemento de X
A El tipo de asignador de X : X::allocator_type si existe, de lo contrario std:: allocator < X :: value_type >
a Un valor de tipo X
a2 Un valor de tipo Y cuyos node handles son compatibles con X
b Un valor de tipo X o const X
u Un nombre de una variable que se está declarando
a_uniq Un valor de tipo X cuando X admite claves únicas
a_eq Un valor de tipo X cuando X admite claves equivalentes
a_tran Un valor de tipo X o const X cuando existe el tipo X::key_compare::is_transparent
i , j Los LegacyInputIterator s que hacen referencia a elementos convertibles implícitamente a X::value_type
[ i , j ) Un rango válido
rg
(desde C++23) 		Un valor de un tipo R que modela container-compatible-range <value_type>
p Un iterador constante válido a a
q Un iterador constante dereferenciable válido a a
r Un iterador válido desreferenciable a a
q1 , q2 Un rango válido de iteradores constantes en a
il Un objeto de tipo std:: initializer_list < X :: value_type >
t Un valor de tipo X::value_type
k Un valor de tipo X::key_type
c Un valor de tipo X::key_compare o const X :: key_compare
kl Un valor tal que a está particionado con respecto a c ( x, kl ) , con x el valor clave de e y e en a
ku Un valor tal que a está particionado con respecto a ! c ( ku, x ) , con x el valor clave de e y e en a
ke Un valor tal que a está particionado con respecto a c ( x, ke ) y ! c ( ke, x ) , con c ( x, ke ) implicando ! c ( ke, x ) y con x siendo el valor clave de e y e en a
kx
(desde C++23) 		Un valor tal que:
  • a está particionado con respecto a c ( x, kx ) y ! c ( kx, x ) , con c ( x, kx ) implicando ! c ( kx, x ) y con x siendo el valor clave de e y e en a , y
  • kx no es convertible ni a X::iterator ni a X::const_iterator
m Un asignador de un tipo convertible a A
nh Un valor r no constante de tipo X::node_type

El tipo X satisface AssociativeContainer si

  • El tipo X satisface Container (hasta C++11) AllocatorAwareContainer (desde C++11) ,
  • Está parametrizado en Key y una relación de ordenamiento Compare que induce un ordenamiento débil estricto en elementos de Key , y
    • Además, std::map y std::multimap asocian un tipo mapeado arbitrario T con la Key .
    • El objeto de tipo Compare se denomina objeto de comparación de un contenedor de tipo X .
  • Las siguientes expresiones deben ser válidas y tener sus efectos especificados para todos los contenedores asociativos:

Tipos

Nombre Tipo Requisitos
key_type Key
mapped_type T (solo para std::map y std::multimap )
value_type Erasable desde X
key_compare Compare CopyConstructible
value_compare BinaryPredicate
node_type Una especialización de la plantilla de clase node-handle , de modo que los tipos anidados públicos sean los mismos tipos que los correspondientes en X .

Funciones miembro y operadores

Expresión Resultado Precondiciones Efectos Retorna Complejidad
X ( c ) Construye un contenedor vacío. Utiliza una copia de c como objeto de comparación Constante
X u = X ( ) ;
X u ; 		key_compare cumple los requisitos de DefaultConstructible Construye un contenedor vacío. Utiliza Compare ( ) como objeto de comparación Constante
X ( i, j, c ) value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío e inserta elementos del rango [ i , j ) en él; utiliza c como objeto de comparación N·log ( N ) en general, donde N tiene el valor std:: distance ( i, j ) ; lineal si [ i , j ) está ordenado con respecto a value_comp ( )
X ( i, j ) key_compare cumple con los requisitos de DefaultConstructible . value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío e inserta elementos del rango [ i , j ) en él; utiliza Compare ( ) como objeto de comparación
X ( from_range, rg, c )
(desde C++23) 		value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío e inserta cada elemento de rg en él. Utiliza c como objeto de comparación N·log ( N ) en general, donde N tiene el valor ranges:: distance ( rg ) ; lineal si rg está ordenado con respecto a value_comp ( )
X ( from_range, rg )
(desde C++23) 		key_compare cumple con los requisitos de DefaultConstructible . value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío e inserta cada elemento de rg en él. Utiliza Compare ( ) como objeto de comparación
X ( il, c ) X ( il. begin ( ) , il. end ( ) , c )
X ( il ) X ( il. begin ( ) , il. end ( ) )
a = il X & value_type es CopyInsertable en X y CopyAssignable Asigna el rango [ il. begin ( ) , il. end ( ) ) a a . Todos los elementos existentes de a son asignados o destruidos N·log ( N ) en general, donde N tiene el valor il. size ( ) + a. size ( ) ; lineal si [ il. begin ( ) , il. end ( ) ) está ordenado con respecto a value_comp ( )
b. key_comp ( ) X::key_compare El objeto de comparación a partir del cual se construyó b Constante
b. value_comp ( ) X::value_compare Un objeto de value_compare construido a partir del objeto de comparación Constante
a_uniq. emplace ( args ) std:: pair <
iterator,
bool > 		value_type es EmplaceConstructible en X desde args Inserta un objeto value_type t construido con std:: forward < Args > ( args ) ... si y solo si no existe ningún elemento en el contenedor con clave equivalente a la clave de t El componente bool del par devuelto es true si y solo si la inserción se realiza, y el componente iterador del par apunta al elemento con clave equivalente a la clave de t Logarítmico
a_eq. emplace ( args ) iterator value_type es EmplaceConstructible en X desde args Inserta un objeto value_type t construido con std:: forward < Args > ( args ) ... . Si existe un rango que contiene elementos equivalentes a t en a_eq , t se inserta al final de ese rango Un iterador que apunta al elemento recién insertado Logarítmica
a. emplace_hint ( p, args ) iterator Equivalente a

a. emplace (
std:: forward < Args > ( args ) ... ) , excepto que el elemento se inserta lo más cerca posible de la posición inmediatamente anterior a p

Un iterador que apunta al elemento con la clave equivalente al elemento recién insertado Logarítmico en general, pero constante amortizado si el elemento se inserta justo antes de p
a_uniq. insert ( t ) std:: pair <
iterator,
bool > 		Si t es un rvalue no constante, value_type debe ser MoveInsertable en X ; de lo contrario, value_type debe ser CopyInsertable en X Inserta t si y solo si no existe ningún elemento en el contenedor con clave equivalente a la clave de t El componente bool del par devuelto es true si y solo si la inserción se realiza, y el componente iterator del par apunta al elemento con clave equivalente a la clave de t Logarítmico
a_eq. insert ( t ) iterator Si t es un rvalue no constante, value_type debe ser MoveInsertable en X ; de lo contrario, value_type debe ser CopyInsertable en X Inserta t y devuelve el iterador que apunta al elemento recién insertado. Si existe un rango que contiene elementos equivalentes a t en a_eq , t se inserta al final de ese rango Logarítmica
a. insert ( p, t ) iterator Si t es un rvalue no constante, value_type debe ser MoveInsertable en X ; de lo contrario, value_type debe ser CopyInsertable en X Inserta t si y solo si no existe un elemento con clave equivalente a la clave de t en contenedores con claves únicas; siempre inserta t en contenedores con claves equivalentes. t se inserta lo más cerca posible de la posición inmediatamente anterior a p Un iterador que apunta al elemento con clave equivalente a la clave de t Logarítmica en general, pero constante amortizado si t se inserta justo antes de p
a. insert ( i, j ) void value_type es EmplaceConstructible en X desde * i . Ni i ni j son iteradores de a Inserta cada elemento del rango [ i , j ) si y solo si no existe un elemento con clave equivalente a la clave de ese elemento en contenedores con claves únicas; siempre inserta ese elemento en contenedores con claves equivalentes N·log ( a. size ( ) + N ) , donde N tiene el valor std:: distance ( i, j )
a. insert_range ( rg )
(desde C++23) 		void value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) . rg y a no se superponen Inserta cada elemento de rg si y solo si no existe un elemento con clave equivalente a la clave de ese elemento en contenedores con claves únicas; siempre inserta ese elemento en contenedores con claves equivalentes N·log ( a. size ( ) + N ) , donde N tiene el valor ranges:: distance ( rg )
a. insert ( il ) a. insert ( il. begin ( ) , il. end ( ) )
a_uniq. insert ( nh ) insert_return_type nh está vacío o

a_uniq. get_allocator ( )
==
nh. get_allocator ( ) es true

Si nh está vacío, no tiene efecto. De lo contrario, inserta el elemento poseído por nh si y solo si no hay ningún elemento en el contenedor con una clave equivalente a nh. key ( ) Si nh está vacío, inserted es false , position es end ( ) , y node está vacío. De lo contrario, si la inserción tuvo lugar, inserted es true , position apunta al elemento insertado, y node está vacío; si la inserción falló, inserted es false , node tiene el valor previo de nh , y position apunta a un elemento con una clave equivalente a nh. key ( ) Logarítmico
a_eq. insert ( nh ) iterator nh está vacío o

a_eq. get_allocator ( )
==
nh. get_allocator ( ) es true

Si nh está vacío, no tiene efecto y retorna a_eq. end ( ) . De lo contrario, inserta el elemento poseído por nh y retorna un iterador apuntando al elemento recién insertado. Si existe un rango conteniendo elementos con claves equivalentes a nh. key ( ) en a_eq , el elemento se inserta al final de ese rango. Garantiza: nh queda vacío Logarítmica
a. insert ( p, nh ) iterator nh está vacío o

a. get_allocator ( )
==
nh. get_allocator ( ) es true

Si nh está vacío, no tiene efecto y retorna a. end ( ) . De lo contrario, inserta el elemento poseído por nh si y solo si no existe un elemento con clave equivalente a nh. key ( ) en contenedores con claves únicas; siempre inserta el elemento poseído por nh en contenedores con claves equivalentes. El elemento se inserta lo más cerca posible a la posición inmediatamente anterior a p . Garantiza: nh está vacío si la inserción tiene éxito, sin cambios si la inserción falla Un iterador que apunta al elemento con clave equivalente a nh. key ( ) Logarítmico en general, pero constante amortizado si el elemento se inserta justo antes de p
a. extract ( k ) node_type Elimina el primer elemento en el contenedor con clave equivalente a k Un node_type que posee el elemento si se encuentra, de lo contrario un node_type vacío log ( a. size ( ) )
a_tran. extract ( kx )
(desde C++23) 		node_type Elimina el primer elemento del contenedor con clave r tal que ! c ( r, kx ) && ! c ( kx, r ) sea true Un node_type que posee el elemento si se encuentra, de lo contrario un node_type vacío log ( a_tran. size ( ) )
a. extract ( q ) node_type Elimina el elemento apuntado por q Un node_type que posee ese elemento Amortizado constante
a. merge ( a2 ) void a. get_allocator ( )
==
a2. get_allocator ( ) 		Intenta extraer cada elemento en a2 e insertarlo en a utilizando el objeto de comparación de a . En contenedores con claves únicas, si existe un elemento en a con clave equivalente a la clave de un elemento de a2 , entonces ese elemento no se extrae de a2 . Garantiza: Los punteros y referencias a los elementos transferidos de a2 referencian a esos mismos elementos pero como miembros de a . Los iteradores que referencian a los elementos transferidos continuarán referenciando a sus elementos, pero ahora se comportan como iteradores en a , no en a2 . Lanza: Nada a menos que el objeto de comparación lance N·log ( a. size ( ) + N ) , donde N tiene el valor a2. size ( )
a. erase ( k ) size_type Elimina todos los elementos del contenedor con clave equivalente a k El número de elementos eliminados log ( a. size ( ) )
+ a. count ( k )
a_tran. erase ( kx )
(desde C++23) 		size_type Elimina todos los elementos en el contenedor con clave r tal que ! c ( r, kx ) && ! c ( kx, r ) sea true El número de elementos eliminados log ( a_tran. size ( ) )
+ a_tran. count ( kx )
a. erase ( q ) iterator Elimina el elemento apuntado por q Un iterador que apunta al elemento inmediatamente posterior a q antes de que el elemento fuera eliminado. Si no existe tal elemento, retorna a. end ( ) Constante amortizado
a. erase ( r ) iterator Elimina el elemento apuntado por r Un iterador que apunta al elemento inmediatamente siguiente a r antes de que el elemento fuera eliminado. Si no existe tal elemento, retorna a. end ( ) Constante amortizado
a. erase ( q1, q2 ) iterator Elimina todos los elementos en el rango
[ q1 , q2 ) 		Un iterador que apunta al elemento señalado por q2 antes de que se elimine cualquier elemento. Si no existe tal elemento, a. end ( ) es devuelto log ( a. size ( ) ) + N , donde N tiene el valor std:: distance ( q1, q2 )
a. clear ( ) a. erase ( a. begin ( ) , a. end ( ) ) . Garantiza: a. empty ( ) es true Lineal en a. size ( )
b. find ( k ) iterator ; const_iterator para constante b Un iterador que apunta a un elemento con la clave equivalente a k , o b. end ( ) si no se encuentra dicho elemento Logarítmica
a_tran. find ( ke ) iterator ; const_iterator para constante a_tran Un iterador que apunta a un elemento con clave r tal que

! c ( r, ke ) &&
! c ( ke, r ) es true , o a_tran. end ( ) si no se encuentra dicho elemento

Logarítmico
b. count ( k ) size_type El número de elementos con clave equivalente a k log ( b. size ( ) )
+ b. count ( k )
a_tran. count ( ke ) size_type El número de elementos con clave r tal que

! 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 para constante b Un iterador que apunta al primer elemento con clave no menor que k , o b. end ( ) si no se encuentra dicho elemento Logarítmica
a_tran. lower_bound ( kl ) iterator ; const_iterator para constante a_tran Un iterador que apunta al primer elemento con clave r tal que ! c ( r, kl ) , o a_tran. end ( ) si no se encuentra dicho elemento Logarítmico
b. upper_bound ( k ) iterator ; const_iterator para constante b Un iterador que apunta al primer elemento con clave mayor que k , o b. end ( ) si no se encuentra dicho elemento Logarítmico
a_tran. upper_bound ( ku ) iterator ; const_iterator para constante a_tran Un iterador que apunta al primer elemento con clave r tal que c ( ku, r ) , o a_tran. end ( ) si no se encuentra dicho elemento Logarítmico
b. equal_range ( k ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > para constante b

Equivalente a:

return
std:: make_pair (
b. lower_bound ( k ) ,
b. upper_bound ( k ) ) ;

Logarítmico
a_tran. equal_range ( ke ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > para constante a_tran

Equivalente a:

return
std:: make_pair (
a_tran. lower_bound ( ke ) ,
a_tran. upper_bound ( ke ) ) ;

Logarítmico

Iteradores

Los iteradores de contenedores asociativos satisfacen los requisitos de LegacyBidirectionalIterator .

Para contenedores asociativos donde value_type es igual a key_type , tanto iterator como const_iterator son iteradores constantes. No está especificado si iterator y const_iterator son el mismo tipo.

Los iteradores de contenedores asociativos iteran a través de los contenedores en orden no descendente de claves, donde no descendente se define por la comparación que se utilizó para construir los contenedores. Es decir, dado

  • a , un contenedor asociativo
  • i y j , iteradores dereferenciables a a .

Si la distancia desde i hasta j es positiva, entonces a. value_comp ( ) ( * j, * i ) == false . Adicionalmente, si a es un contenedor asociativo con claves únicas, se cumple la condición más fuerte a. value_comp ( ) ( * i, * j ) ! = false .

Esta sección está incompleta
Razón: Completar requisitos.

Biblioteca estándar

Las siguientes contenedores de la biblioteca estándar satisfacen los requisitos de AssociativeContainer :

colección de claves únicas, ordenadas por claves
(class template)
colección de claves, ordenadas por claves
(class template)
colección de pares clave-valor, ordenados por claves, las claves son únicas
(class template)
colección de pares clave-valor, ordenados por claves
(class template)

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares publicados anteriormente de C++.

DR Se aplica a Comportamiento publicado Comportamiento correcto
LWG 354 C++98 lower_bound y upper_bound no
devolvían el iterador final si no se encontraba ningún elemento 		devuelven el iterador
final en este caso
LWG 589 C++98 los elementos a los que i y j se refieren
tenían el tipo X::value_type 		los elementos son implícitamente
convertibles a X::value_type