Namespaces
Variants

C++ named requirements: UnorderedAssociativeContainer (since C++11)

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

Los contenedores asociativos no ordenados son Container s que proporcionan búsqueda rápida de objetos basada en claves. La complejidad en el peor caso es lineal pero en promedio son mucho más rápidos para la mayoría de las operaciones.

Los contenedores asociativos no ordenados están parametrizados por Key ; Hash , un objeto función Hash que actúa como función hash en Key ; y Pred , un BinaryPredicate que evalúa la equivalencia entre Key s. std::unordered_map y std::unordered_multimap también tienen un tipo mapeado T asociado con la Key .

Si dos Key s son iguales según Pred , Hash debe devolver el mismo valor para ambas claves.

Si tanto Hash::is_transparent como Pred::is_transparent existen y cada uno nombra un tipo, las funciones miembro find , contains , count , equal_range , y bucket aceptan argumentos de tipos distintos a Key y esperan que Hash sea invocable con valores de esos tipos, y que Pred sea una función de comparación transparente como std::equal_to<> .

(desde C++20)

std::unordered_map y std::unordered_set pueden contener como máximo un elemento con una clave dada, std::unordered_multiset y std::unordered_multimap en cambio pueden tener múltiples elementos con la misma clave (los cuales siempre deben ser adyacentes en las iteraciones).

Para std::unordered_set y std::unordered_multiset el tipo de valor es el mismo que el tipo de clave y tanto iterator como const_iterator son iteradores constantes. Para std::unordered_map y std::unordered_multimap el tipo de valor es std:: pair < const Key, T > .

Los elementos en un contenedor asociativo no ordenado se organizan en cubos (buckets), las claves con el mismo hash terminarán en el mismo cubo. El número de cubos se incrementa cuando el tamaño del contenedor aumenta para mantener el número promedio de elementos en cada cubo por debajo de un valor determinado.

El rehash invalida los iteradores y puede causar que los elementos se reorganicen en diferentes buckets, pero no invalida las referencias a los elementos.

Los contenedores asociativos no ordenados cumplen con los requisitos de AllocatorAwareContainer . Para std::unordered_map y std::unordered_multimap los requisitos de value_type en AllocatorAwareContainer se aplican a key_type y mapped_type (no a value_type ).

Contenidos

Requisitos

Leyenda
X Una clase de contenedor asociativo no ordenado
a Un valor de tipo X
a2 Un valor de un tipo con nodos compatibles con el tipo X
b Un valor de tipo X o const X
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 los identificadores calificados X::key_equal::is_transparent y X::hasher::is_transparent son ambos válidos y denotan tipos
i , j Iteradores de entrada que hacen referencia a 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 , q2 Iteradores constantes válidos a a
q , q1 Iteradores constantes válidos desreferenciables a a
r Un iterador válido desreferenciable a a
[ q1 , q2 ) Un rango válido en a
il Un valor de tipo std:: initializer_list < value_type >
t Un valor de tipo X::value_type
k Un valor de tipo key_type
hf Un valor de tipo hasher o const hasher
eq Un valor de tipo key_equal o const key_equal
ke Un valor tal que
  • eq ( r1, ke ) == eq ( ke, r1 ) ,
  • hf ( r1 ) == hf ( ke ) si eq ( r1, ke ) es true , y
  • si dos cualesquiera de eq ( r1, ke ) , eq ( r2, ke ) , y eq ( r1, r2 ) son true , entonces los tres son true ,

donde r1 y r2 son claves de elementos en a_tran

kx (desde C++23) Un valor tal que
  • eq ( r1, kx ) == eq ( kx, r1 ) ,
  • hf ( r1 ) == hf ( kx ) si eq ( r1, kx ) es true ,
  • si dos cualesquiera de eq ( r1, kx ) , eq ( r2, kx ) , y eq ( r1, r2 ) son true , entonces los tres son true , y
  • kx no es convertible ni a iterator ni a const_iterator ,

donde r1 y r2 son claves de elementos en a_tran

n Un valor de tipo size_type
z Un valor de tipo float
nh (desde C++17) Un valor r de tipo X :: node_type

Tipos de miembros

Nombre Tipo Requisitos Notas
X::key_type Key
X::mapped_type T std::unordered_map y std::unordered_multimap únicamente
X::value_type Key std::unordered_set y std::unordered_multiset únicamente. Erasable en X
std:: pair < const Key, T > std::unordered_map y std::unordered_multimap únicamente. Erasable en X
X::hasher Hash Hash
X::key_equal Pred CopyConstructible ; BinaryPredicate que toma dos argumentos de tipo Key y expresa una relación de equivalencia
X::local_iterator LegacyIterator La categoría y tipos son los mismos que X::iterator Puede usarse para iterar a través de un solo bucket, pero no entre buckets
X::const_local_iterator LegacyIterator La categoría y tipos son los mismos que X::const_iterator
X::node_type (desde C++17) Una especialización de la plantilla de clase node-handle Los tipos anidados públicos son los mismos que los tipos correspondientes en X

Funciones miembro y operadores

Expresión Resultado Precondiciones Efectos Retorna Complejidad
X ( n, hf, eq ) Construye un contenedor vacío con al menos n cubetas, usando hf como función hash y eq como predicado de igualdad de claves O ( n )
X ( n, hf ) key_equal es DefaultConstructible Construye un contenedor vacío con al menos n cubetas, usando hf como función hash y key_equal ( ) como predicado de igualdad de claves O ( n )
X ( n ) hasher y key_equal son DefaultConstructible Construye un contenedor vacío con al menos n cubetas, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves O ( n )
X a = X ( ) ;
X a ; 		hasher y key_equal son DefaultConstructible Construye un contenedor vacío con un número no especificado de buckets, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves Constante
X ( i, j, n, hf, eq ) value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío con al menos n cubos, usando hf como función hash y eq como predicado de igualdad de claves, e inserta elementos desde [ i , j ) en él Caso promedio O(N) ( N es std:: distance ( i, j ) ), caso peor O(N 2 )
X ( i, j, n, hf ) key_equal es DefaultConstructible . value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío con al menos n cubetas, usando hf como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde [ i , j ) en él Caso promedio O(N) ( N es std:: distance ( i, j ) ), caso peor O(N 2 )
X ( i, j, n ) hasher y key_equal son DefaultConstructible . value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío con al menos n cubetas, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde [ i , j ) en él Caso promedio O(N) ( N es std:: distance ( i, j ) ), caso peor O(N 2 )
X ( i, j ) hasher y key_equal son DefaultConstructible . value_type es EmplaceConstructible en X desde * i Construye un contenedor vacío con un número no especificado de buckets, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde [ i , j ) en él Caso promedio O(N) ( N es std:: distance ( i, j ) ), caso peor O(N 2 )
X ( std:: from_range ,
rg, n, hf, eq )
(desde C++23) 		value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío con al menos n buckets, usando hf como función hash y eq como predicado de igualdad de claves, e inserta elementos desde rg en él Caso promedio O(N) ( N es ranges:: distance ( rg ) ), caso peor O(N 2 )
X ( std:: from_range ,
rg, n, hf )
(desde C++23) 		key_equal es DefaultConstructible . value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío con al menos n cubetas, usando hf como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde rg en él Caso promedio O(N) ( N es ranges:: distance ( rg ) ), caso peor O(N 2 )
X ( std:: from_range ,
rg, n )
(desde C++23) 		hasher y key_equal son DefaultConstructible . value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío con al menos n cubetas, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde rg en él Caso promedio O(N) ( N es ranges:: distance ( rg ) ), caso peor O(N 2 )
X ( std:: from_range ,
rg )
(desde C++23) 		hasher y key_equal son DefaultConstructible . value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) Construye un contenedor vacío con un número no especificado de buckets, usando hasher ( ) como función hash y key_equal ( ) como predicado de igualdad de claves, e inserta elementos desde rg en él Caso promedio O(N) ( N es ranges:: distance ( rg ) ), caso peor O(N 2 )
X ( il ) X ( il. begin ( ) , il. end ( ) )
X ( il, n ) X ( il. begin ( ) , il. end ( ) , n )
X ( il, n, hf ) X ( il. begin ( ) , il. end ( ) , n, hf )
X ( il, n, hf, eq ) X ( il. begin ( ) , il. end ( ) , n, hf, eq )
X ( b ) Container ; Copia la función hash, el predicado y el factor de carga máximo Caso promedio lineal en b. size ( ) , caso peor O(N 2 )
a = b X& Container ; copia la función hash, el predicado y el factor de carga máximo Caso promedio lineal en b. size ( ) , caso peor O(N 2 )
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 Caso promedio lineal en il. size ( ) , caso peor O(N 2 )
b. hash_function ( ) hasher b función hash de b Constante
b. key_eq ( ) key_equal b 's predicado de igualdad de claves 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 Caso promedio O(1) , caso peor O ( a_uniq. size ( ) )
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 ) ... Un iterador que apunta al elemento recién insertado Caso promedio O(1) , caso peor O ( a_eq. size ( ) )
a. emplace_hint ( p, args ) iterator value_type es EmplaceConstructible en X desde args a. emplace (
std:: forward < Args > ( args ) ... ) 		Un iterador que apunta al elemento con la clave equivalente al elemento recién insertado. El const_iterator p es una sugerencia que indica dónde debería comenzar la búsqueda. Se permite a las implementaciones ignorar la sugerencia Caso promedio O(1) , caso peor O ( a. size ( ) )
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 indica si la inserción se realiza, y el componente iterator apunta al elemento con clave equivalente a la clave de t Caso promedio O(1) , caso peor O ( a_uniq. size ( ) )
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 Un iterador que apunta al elemento recién insertado Caso promedio O(1) , caso peor O ( a_eq. size ( ) )
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 a. insert ( t ) . El iterador p es una sugerencia que indica dónde debe comenzar la búsqueda. Las implementaciones pueden ignorar la sugerencia Un iterador que apunta al elemento con clave equivalente a la de t Caso promedio O(1) , caso peor O ( a. size ( ) )
a. insert ( i, j ) void value_type es EmplaceConstructible en X desde * i . Ni i ni j son iteradores de a a. insert ( t ) para cada elemento en
[ i , j ) 		Caso promedio O(N) , donde N es std:: distance ( i, j ) , caso peor O ( N· ( a. size ( ) + 1 ) )
a. insert_range ( rg )
(desde C++23) 		void value_type es EmplaceConstructible en X desde * ranges:: begin ( rg ) . rg y a no se superponen a. insert ( t ) para cada elemento t en rg Caso promedio O(N) , donde N es ranges:: distance ( rg ) , caso peor O ( N· ( a. size ( ) + 1 ) )
a. insert ( il ) a. insert ( il. begin ( ) , il. end ( ) )
a_uniq. insert ( nh )
(desde C++17) 		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 ( ) . Garantiza: 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 ( ) Caso promedio O(1) , peor caso O ( a_uniq. size ( ) )
a_eq. insert ( nh )
(desde C++17) 		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 que apunta al elemento recién insertado. Garantiza: nh queda vacío Caso promedio O(1) , caso peor O ( a_eq. size ( ) )
a. insert ( q, nh )
(desde C++17) 		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 iterador q es una sugerencia que indica dónde debería comenzar la búsqueda. Se permite a las implementaciones ignorar la sugerencia. 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 ( ) Caso promedio O(1) , caso peor O ( a. size ( ) )
a. extract ( k )
(desde C++17) 		node_type Elimina un elemento del contenedor con clave equivalente a k Un node_type que posee el elemento si se encuentra, de lo contrario un node_type vacío Caso promedio O(1) , caso peor O ( a. size ( ) )
a_tran. extract ( kx )
(desde C++23) 		node_type Elimina un elemento del contenedor con clave equivalente a kx Un node_type que posee el elemento si se encuentra, de lo contrario un node_type vacío Caso promedio O(1) , caso peor O ( a_tran. size ( ) )
a. extract ( q )
(desde C++17) 		node_type Elimina el elemento apuntado por q Un node_type que posee ese elemento Caso promedio O(1) , caso peor O ( a. size ( ) )
a. merge ( a2 )
(desde C++17) 		void a. get_allocator ( )
==
a2. get_allocator ( ) 		Intenta extraer cada elemento en a2 e insertarlo en a usando la función hash y el predicado de igualdad de claves 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 se refieren a esos mismos elementos pero como miembros de a . Los iteradores que se refieren a los elementos transferidos y todos los iteradores que se refieren a a quedarán invalidados, pero los iteradores a elementos que permanecen en a2 permanecerán válidos Caso promedio O(N) , donde N es a2. size ( ) , caso peor O ( N· ( a. size ( ) + 1 ) )
a. erase ( k ) size_type Elimina todos los elementos con clave equivalente a k El número de elementos eliminados Caso promedio O ( a. count ( k ) ), caso peor O ( a. size ( ) )
a_tran. erase ( kx )
(desde C++23) 		size_type Elimina todos los elementos con clave equivalente a kx El número de elementos eliminados Caso promedio O ( a_tran. count ( kx ) ), caso peor O ( a_tran. size ( ) )
a. erase ( q ) iterator Elimina el elemento apuntado por q El iterador inmediatamente posterior a q antes de la eliminación Caso promedio O(1) , caso peor O ( a. size ( ) )
a. erase ( r )
(desde C++17) 		iterator Elimina el elemento apuntado por r El iterador inmediatamente posterior a r antes de la eliminación Caso promedio O(1) , caso peor O ( a. size ( ) )
a. erase ( q1, q2 ) iterator Elimina todos los elementos en el rango
[ q1 , q2 ) 		El iterador inmediatamente posterior a los elementos eliminados antes del borrado Caso promedio lineal en std:: distance ( q1, q2 ) , caso peor O ( a. size ( ) )
a. clear ( ) void Borra todos los elementos del contenedor. Garantiza que: a. empty ( ) sea true Lineal en a. size ( )
b. find ( k ) iterator ; const_iterator para constante b Un iterador que apunta a un elemento con clave equivalente a k , o b. end ( ) si no existe tal elemento Caso promedio O(1) , caso peor O ( b. size ( ) )
a_tran. find ( ke )
(desde C++17) ? 		iterator ; const_iterator para constante a_tran Un iterador que apunta a un elemento con clave equivalente a ke , o a_tran. end ( ) si no existe tal elemento Caso promedio O(1) , caso peor O ( a_tran. size ( ) )
b. count ( k ) size_type El número de elementos con clave equivalente a k Caso promedio O ( b. count ( k ) ), caso peor O ( b. size ( ) )
a_tran. count ( ke )
(desde C++17) ? 		size_type El número de elementos con clave equivalente a ke Caso promedio O ( a_tran. count ( ke ) ), caso peor O ( a_tran. size ( ) )
b. contains ( k )
(desde C++20) ? 		b. find ( k ) ! = b. end ( )
a_tran. contains ( ke )
(desde C++20) ? 		a_tran. find ( ke ) ! = a_tran. end ( )
b. equal_range ( k ) std:: pair <
iterator,
iterator > ;

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

Un rango que contiene todos los elementos con claves equivalentes a k . Devuelve

std:: make_pair (
b. end ( ) , b. end ( ) ) si no existen tales elementos

Caso promedio O ( b. count ( k ) ), caso peor O ( b. size ( ) )
a_tran. equal_range ( ke )
(desde C++20) ? 		std:: pair <
iterator,
iterator > ;

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

Un rango que contiene todos los elementos con claves equivalentes a ke . Retorna

std:: make_pair (
a_tran. end ( ) ,
a_tran. end ( ) ) si no existen tales elementos

Caso promedio O ( a_tran. count ( ke ) ), caso peor O ( a_tran. size ( ) )
b. bucket_count ( ) size_type El número de buckets que b contiene Constante
b. max_bucket_count ( ) size_type Un límite superior en el número de buckets que b puede contener jamás Constante
b. bucket ( k ) size_type b. bucket_count ( ) > 0 El índice del bucket en el que se encontrarían los elementos con claves equivalentes a k , si existiera algún elemento de este tipo. El valor de retorno está en el rango [ ​ 0 ​ , b. bucket_count ( ) ) Constante
a_tran. bucket ( ke ) size_type a_tran.
bucket_count ( ) > 0 		El índice del bucket en el que se encontrarían elementos con claves equivalentes a ke , si existiera algún elemento de este tipo. El valor devuelto debe estar en el rango [ ​ 0 ​ , a_tran. bucket_count ( ) ) Constante
b. bucket_size ( n ) size_type n está en [ ​ 0 ​ , b. bucket_count ( ) ) El número de elementos en el n ésimo bucket O ( b. bucket_size ( n ) )
b. begin ( n ) local_iterator ; const_local_iterator para constante b n está en [ ​ 0 ​ , b. bucket_count ( ) ) Un iterador que hace referencia al primer elemento en el bucket. Si el bucket está vacío, entonces b. begin ( n ) == b. end ( n ) Constante
b. end ( n ) local_iterator ; const_local_iterator para constante b n está en [ ​ 0 ​ , b. bucket_count ( ) ) Un iterador que representa el valor pasado-el-final para el bucket Constante
b. cbegin ( n ) const_local_iterator n está en [ ​ 0 ​ , b. bucket_count ( ) ) Un iterador que hace referencia al primer elemento en el cubo. Si el cubo está vacío, entonces b. cbegin ( n ) == b. cend ( n ) Constante
b. cend ( n ) const_local_iterator n está en [ ​ 0 ​ , b. bucket_count ( ) ) Un iterador que representa el valor pasado-el-final para el bucket Constante
b. load_factor ( ) float El número promedio de elementos por bucket Constante
b. max_load_factor ( ) float Un número positivo que el contenedor intenta mantener como límite superior para el factor de carga. El contenedor incrementa automáticamente el número de cubetas según sea necesario para mantener el factor de carga por debajo de este valor Constante
a. max_load_factor ( z ) void z debe ser positivo. Puede cambiar el factor de carga máximo del contenedor, usando z como sugerencia Constante
a. rehash ( n ) void Garantiza:

a. bucket_count ( ) >=
a. size ( ) / a. max_load_factor ( ) y a. bucket_count ( ) >= n

Caso promedio lineal en a. size ( ) , caso peor O(N 2 )
a. reserve ( n ) a. rehash ( std:: ceil (
n / a. max_load_factor ( ) ) )
Esta sección está incompleta
Razón: Requisitos respecto a las funciones miembro.

Biblioteca estándar

Los siguientes contenedores de la biblioteca estándar satisfacen los requisitos de UnorderedAssociativeContainer :

(C++11)
colección de claves únicas, hasheadas por claves
(class template)
(C++11)
colección de claves, hasheadas por claves
(class template)
(C++11)
colección de pares clave-valor, hasheados por claves, claves únicas
(class template)
(C++11)
colección de pares clave-valor, hasheados 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 Aplicado a Comportamiento publicado Comportamiento correcto
LWG 2156 C++11 el factor de carga después del rehash solo podía ser
estrictamente menor que el factor de carga máximo 		permitido ser igual