std::unordered_set
Definido en el archivo de encabezado <unordered_set> | ||
template< class Key, | (1) | (desde C++11) |
namespace pmr { template< | (2) | (desde C++17) |
std::unordered_set es un contenedor asociativo que contiene un conjunto de objetos únicos de tipo Key. La búsqueda, inserción y remoción tiene una complejidad promedio de tiempo constante.
Internamente, los elementos no se ordenan en ningún orden en particular, sino que se organizan en depósitos (buckets). En qué depósito se coloca un elemento depende completamente de la dispersión (hash) de su valor. Esto permite un acceso rápido a elementos individuales, ya que una vez que se calcula una dispersión, se refiere al depósito exacto en el que se coloca el elemento.
Los elementos del contenedor no pueden modificarse (incluso por iteradores no constantes) ya que la modificación podría cambiar la dispersión de un elemento y corromper el contenedor.
std::unordered_set cumple con los requisitos de Contenedor, ContenedorConscienteDeAsignador, ContenedorAsociativoNoOrdenado.
Contenido |
[editar]Invalidación de iteradores
| Operaciones | Se invalida |
|---|---|
| Todas las operaciones de solo lectura, swap, std::swap | Nunca |
| clear, rehash, reserve, operator= | Siempre |
| insert, emplace, emplace_hint | Solo si ocasiona una redispersión |
| erase | Solo para el elemento borrado |
[editar]Notas
- Las funciones de intercambio no invalidan ninguno de los iteradores dentro del contenedor, pero sí invalidan el iterador que marca el final de la región de intercambio.
- Las referencias y los punteros a datos almacenados en el contenedor solo se invalidan al borrar ese elemento, incluso cuando se invalida el iterador correspondiente.
- Después de la asignación por movimiento del contenedor, a menos que la asignación de movimiento de elemento por elemento sea forzada por asignadores de memoria, referencias, punteros e iteradores incompatibles (que no sean el iterador al final) al contenedor movido siguen siendo válidos, pero se refieren a elementos que ahora están en *this.
[editar]Parámetros de plantilla
| Esta sección está incompleta Razón: Agregar descripciones de los parámetros de plantilla. |
[editar]Tipos miembro
| Tipo miembro | Definición |
key_type | Key |
value_type | Key |
size_type | Tipo entero sin signo (por lo general std::size_t) |
difference_type | Tipo entero con signo (por lo general std::ptrdiff_t) |
hasher | Hash |
key_equal | KeyEqual |
allocator_type | Allocator |
reference | value_type& |
const_reference | const value_type& |
pointer | std::allocator_traits<Allocator>::pointer |
const_pointer | std::allocator_traits<Allocator>::const_pointer |
iterator | IteradorDeAvanceLegado constante |
const_iterator | IteradorDeAvanceLegado constante |
local_iterator | Un tipo iterador cuyos tipos de referencia de categoría, valor, diferencia, puntero y son los mismos que iterator. Este iteradorse puede usar para iterar a través de un solo depósito, pero no a través de depósitos. |
const_local_iterator | Un tipo iterador cuyos tipos de referencia de categoría, valor, diferencia, puntero y son los mismos que const_iterator. Este iteradorse puede usar para iterar a través de un solo depósito, pero no a través de depósitos. |
node_type(desde C++17) | Una especialización de node handle que representa un nodo del contenedor. |
insert_return_type(desde C++17) | Tipo que describe el resultado de insertar un tipo nodo node_type, una especialización detemplate<class Iter, class NodeType> |
[editar]Funciones miembro
Construye el contenedor unordered_set. (función miembro pública) | |
(C++11) | Destruye el contenedor unordered_set. (función miembro pública) |
(C++11) | Asigna valores al contenedor. (función miembro pública) |
(C++11) | Devuelve el asignador de memoria asociado. (función miembro pública) |
Iteradores | |
(C++11) | Devuelve un iterador al principio. (función miembro pública) |
(C++11) | Devuelve un iterador al final. (función miembro pública) |
Capacidad | |
(C++11) | Comprueba si el contenedor está vacío. (función miembro pública) |
(C++11) | Devuelve el número de elementos. (función miembro pública) |
(C++11) | Devuelve el número máximo posible de elementos. (función miembro pública) |
Modificadores | |
(C++11) | Borra el contenido. (función miembro pública) |
(C++11) | Inserta elementos o nodos(desde C++17) (función miembro pública) |
(C++23) | Inserta un rango de elementos. (función miembro pública) |
(C++11) | Construye el elemento en el sitio. (función miembro pública) |
(C++11) | Construye elementos en el sitio utilizando una pista. (función miembro pública) |
(C++11) | Borra elementos (función miembro pública) |
(C++11) | Intercambia el contenido. (función miembro pública) |
(C++17) | Extrae nodos del contenedor (función miembro pública) |
(C++17) | Mueve los nodos de otro contenedor. (función miembro pública) |
Búsqueda | |
(C++11) | Devuelve el número de elementos que coinciden con una clave específica. (función miembro pública) |
(C++11) | Encuentra un elemento con una clave específica. (función miembro pública) |
(C++20) | Comprueba si el contenedor contiene un elemento con una clave específica. (función miembro pública) |
(C++11) | Devuelve un rango de elementos que coinciden con una clase específica. (función miembro pública) |
Interfaz de depósito | |
| Devuelve un iterador al principio del depósito especificado. (función miembro pública) | |
| Devuelve un iterador al final del depósito especificado. (función miembro pública) | |
(C++11) | Devuelve el número de depósitos. (función miembro pública) |
(C++11) | Devuelve el número máximo de depósitos. (función miembro pública) |
(C++11) | Devuelve el número de elementos en un depósito específico. (función miembro pública) |
(C++11) | Devuelve un depósito para una clave específica. (función miembro pública) |
Política de dispersión | |
(C++11) | Devuelve el promedio del número de elementos por depósito. (función miembro pública) |
(C++11) | Gestiona el promedio máximo del número de elementos por depósito. (función miembro pública) |
(C++11) | Reserva al menos el número de depósitos especificados y regenera la tabla de dispersión. (función miembro pública) |
(C++11) | Reserva espacio para al menos el número de elementos especificado y regenera la tabla de dispersión. (función miembro pública) |
Observadores | |
(C++11) | Devuelve la función usada para dispersar las claves. (función miembro pública) |
(C++11) | Devuelve la función usada para comparar la igualdad de las claves. (función miembro pública) |
[editar]Funciones no miembro
| Compara los valores de unordered_set. (plantilla de función) | |
| Especializa el algoritmo std::swap. (plantilla de función) | |
(C++20) | Borra todos los elementos que satisfacen un criterio específico. (plantilla de función) |
Guías de deducción | (desde C++17) |
[editar]Notas
Los tipos miembro iterator y const_iterator pueden ser alias del mismo tipo. Esto significa que definir un par de sobrecargas de función utilizando los dos tipos como tipos de parámetro puede violar la Regla de una definición (ODR). Dado que iterator es convertible a const_iterator, una sola función con un const_iterator como tipo de parámetro funcionará en su lugar.
| Macro de prueba de característica | Valor | Estándar | Comentario |
|---|---|---|---|
__cpp_lib_containers_ranges | 202202L | (C++23) | Construcción e inserción de rangos para contenedores. |
[editar]Ejemplo
#include <iostream>#include <unordered_set> void print(constauto& set){for(constauto& elem : set)std::cout<< elem <<' ';std::cout<<'\n';} int main(){ std::unordered_set<int> mySet{2, 7, 1, 8, 2, 8};// crea un conjunto print(mySet);// de enteros mySet.insert(5);// pone un elemento 5 en el conjunto print(mySet); if(auto iter = mySet.find(5); iter != mySet.end()) mySet.erase(iter);// elimina el elemento al que apunta iter print(mySet); mySet.erase(7);// elimina un elemento 7 print(mySet);}
Posible salida:
8 1 7 2 5 8 1 7 2 8 1 7 2 8 1 2
[editar]Informes de defectos
Los siguientes informes de defectos de cambio de comportamiento se aplicaron de manera retroactiva a los estándares de C++ publicados anteriormente.
| ID | Aplicado a | Comportamiento según lo publicado | Comportamiento correcto |
|---|---|---|---|
| LWG 2050 | C++11 | Las definiciones de reference, const_reference, pointery const_pointer estaban basadas en allocator_type. | Se basan en value_type ystd::allocator_traits. |
[editar]Véase también
(desde C++11) | Colección de claves, dispersos (hashed) por claves. (plantilla de clase) |
| Colección de claves, ordenada por claves, donde las claves son únicas. (plantilla de clase) | |
(C++23) | Adapta un contenedor para proporcionar una colección de claves únicas, ordenadas por claves. (plantilla de clase) |
