hash_set (Clase)

Artículo
06/09/2015

Nota
Esta API está obsoleta.La alternativa es unordered_set (Clase).

El hash_set de la clase contenedora es una extensión de la biblioteca estándar (STL) de plantilla y se utiliza para el almacenamiento y la recuperación rápida de datos de una colección en la que los valores de los elementos contenidos son únicos y servicio como valores de clave.

template <
   class Key, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<Key> 
>
class hash_set

Parámetros

Key
El tipo de datos del elemento que se almacene en el hash_set.
Traits
El tipo que incluye dos objetos de función, uno de la clase compara que es un predicado binario que puede comparar dos valores de elemento como criterio de ordenación para determinar el orden relativo y una función hash que sea valores de clave unarios de una asignación de predicado de elementos a enteros sin signo de size_tescrito. Este argumento es opcional, yhash_compare*<Clave,* menos*<Clave>>*es el valor predeterminado.
Allocator
El tipo que representa el objeto almacenado de asignador que encapsula los detalles sobre la asignación y la desasignación de los hash_set de memoria. Este argumento es opcional, y el valor predeterminado esallocator*<Clave>.*

Comentarios

El hash_set es:

Un contenedor asociativo de tamaño variable que admite la recuperación eficaz de valores de elemento según un valor de clave asociado. Además, es un contenedor asociativa simple porque sus valores de elemento son los valores de clave.
Reversible, porque proporciona un iterador bidireccional para tener acceso a sus elementos.
Con algoritmo hash, ya que sus elementos se agrupan en depósitos en función del valor de una función hash aplicada a los valores de clave de los elementos.
Único en el sentido de que cada uno de sus elementos debe tener una clave única. Dado que el hash_set también es un contenedor asociativa simple, sus elementos también son únicos.
Una clase de plantilla porque la funcionalidad que proporciona es genérica y así que independiente del tipo específico de datos contenido como elementos o claves. Los tipos de datos que se usarán para los elementos y las claves se especifican como parámetros en la plantilla de clase junto con la función de comparación y el asignador.

La ventaja principal de los algoritmos hash sobre la ordenación es su mayor eficacia; un algoritmo hash que se ejecuta correctamente realiza inserciones, eliminaciones y búsquedas en un tiempo promedio constante en comparación con un tiempo proporcional al logaritmo del número de elementos del contenedor en el caso de las técnicas de ordenación. El valor de un elemento en un conjunto no se puede cambiar directamente. En su lugar, debe eliminar valores antiguos y insertar elementos con nuevos valores.

En general, la elección del tipo de contenedor se debe tomar según el tipo de búsqueda y de inserción que necesite la aplicación. Los contenedores asociativos con algoritmo hash están optimizados para las operaciones de búsqueda, inserción y eliminación. Las funciones miembro que admiten explícitamente estas operaciones son eficaces cuando se usan con una función hash bien diseñada, las realizan en un tiempo que es una constante promedio y no dependen del número de elementos del contenedor. Una función hash bien diseñada genera una distribución uniforme de valores hash y minimiza el número de colisiones; se produce una colisión cuando se asignan valores de clave distintos al mismo valor hash. En el peor de los casos, con la peor función hash posible, el número de operaciones es proporcional al número de elementos de la secuencia (tiempo lineal).

El hash_set debe ser el contenedor asociativa choice si las condiciones que asocian los valores a las claves son satisfechas por la aplicación. Los elementos de un hash_set son únicos y actúan como sus propios criterios de ordenación. Un modelo para este tipo de estructura es una lista ordenada, por ejemplo, de palabras en las que las palabras pueden aparecer sólo una vez. Si se permiten varias repeticiones de las palabras, la estructura de contenedor adecuada sería hash_multiset. Si los valores deben estar asociados a una lista de palabras claves únicas, un hash_map sería una estructura adecuada para contener estos datos. Si en su lugar las claves no son únicas, un hash_multimap sería el contenedor de la opción.

El hash_set pide la secuencia que controla llamando a un objeto almacenado de Rasgos hash de value_compareescrito. Se puede obtener acceso a este objeto almacenado llamando a la función miembro key_comp. Este tipo de objeto de la función debe comportarse igual que un objeto de hash_compareKey de la clase<, lessKey<>>. Específicamente, porque todos los valores _Key de la clave de tipo, la llamada Trait (_Key ) produce una distribución de valores de tipo size_t.

En general, se debe poder comparar si los elementos son menores que otros para poder establecer este orden; de este modo, dados dos elementos cualesquiera, se puede determinar que son equivalentes (en el sentido de que ninguno es menor que el otro) o que uno es menor que el otro. Esto produce una ordenación entre los elementos no equivalentes. En un sentido más técnico, la función de comparación es un predicado binario que induce una ordenación débil estricta en el sentido matemático estándar. Una fbinaria de predicado (x,*y)*es un objeto de función que tiene dos objetos de argumento x e y y un valor devuelto de true o false. El orden impuesto a un hash_set es el orden débil estricto si el predicado binario es irreflexive, antisimétrico, y transitiva y si la equivalencia es transitiva, donde dos objetos x e y se definen para ser equivalentes cuando tanto f(x,*y)*y f(la y,*x)*es false. Si la condición más fuerte de igualdad entre las claves reemplaza la de equivalencia, la ordenación se convierte en total (en el sentido de que todos los elementos se ordenan entre sí) y las claves coincidentes serán indiscernibles unas de otras.

El orden real de los elementos de la secuencia controlada depende de la función hash, la función de ordenación y el tamaño actual de la tabla hash almacenada en el objeto contenedor. No se puede determinar el tamaño actual de la tabla hash, por lo que en general no se puede predecir el orden de los elementos de la secuencia controlada. La inserción de elementos no invalida ningún iterador y al quitar elementos solo se invalidan los iteradores que habían apuntado específicamente a los elementos quitados.

El iterador proporcionado por la clase de hash_set es un iterador bidireccional, pero el miembro de clase funciona inserción y hash_set tiene versiones que toman como parámetros de plantilla un iterador más débil de entrada, cuyos requisitos de funcionalidad son más mínimos que los garantizados por la clase de iteradores bidireccionales. Los distintos conceptos de iterador forman una familia relacionada por los refinamientos de su funcionalidad. Cada concepto de iterador tiene su propio conjunto de requisitos, y los algoritmos que funcionan con ellos deben limitar sus suposiciones a los requisitos proporcionados por ese tipo de iterador. Se puede suponer que se puede desreferenciar un iterador de entrada para hacer referencia a un objeto y que se puede incrementar hasta el iterador siguiente de la secuencia. Éste es un conjunto mínimo de funcionalidad, pero es suficiente para poder comunicarse significativo sobre un intervalo de iteradores [_First, _Last) en el contexto de las funciones miembro de clase.

En Visual C++ .NET 2003, los miembros de los archivos de encabezado <hash_map> y <hash_set> ya no están en el espacio de nombres std, sino que se han movido al espacio de nombres stdext. Vea El espacio de nombres stdext para obtener más información.

Constructores

hash_set

Construye un hash_set que está vacío o que es una copia de todo o de parte de otro hash_set.

Typedefs

allocator_type	Tipo que representa la clase allocator para el objeto hash_set.
const_iterator	Tipo que proporciona un iterador bidireccional que puede leer un elemento const en hash_set.
const_pointer	Tipo que proporciona un puntero a un elemento const en un hash_set.
const_reference	Tipo que proporciona una referencia a un elemento const almacenado en un hash_set para leer y realizar operaciones const.
const_reverse_iterator	Tipo que proporciona un iterador bidireccional que puede leer cualquier elemento const en hash_set.
difference_type	Tipo entero con signo que se puede usar para representar el número de elementos de un hash_set en un intervalo entre elementos a los que apuntan los iteradores.
iterator	Tipo que proporciona un iterador bidireccional que puede leer o modificar cualquier elemento de hash_set.
key_compare	Tipo que proporciona un objeto de función que puede comparar dos claves de ordenación para determinar el orden relativo de dos elementos en el hash_set.
key_type	Un tipo que describe un objeto almacenado como elemento de hash_set en su capacidad como criterio de ordenación.
puntero	Tipo que proporciona un puntero a un elemento de hash_set.
reference	Tipo que proporciona una referencia a un elemento almacenado en un hash_set.
reverse_iterator	Tipo que proporciona un iterador bidireccional que puede leer o modificar un elemento de hash_set invertido.
size_type	Tipo entero sin signo que puede representar el número de elementos de un hash_set.
value_compare	Un tipo que proporciona dos objetos de función, un predicado binario de la clase compara que puede comparar dos valores de elemento de hash_set para determinar el orden relativo y un predicado unario que aplique un algoritmo hash a los elementos.
value_type	Un tipo que describe un objeto almacenado como elemento de hash_set en su capacidad como valor.

Funciones miembro

begin	Devuelve un iterador que dirige el primer elemento de hash_set.
hash_set::cbegin	Devuelve un iterador constante que direcciona el primer elemento del hash_set.
hash_set::cend	Devuelve un iterador constante que direcciona la ubicación que sigue al último elemento de hash_set.
clear	Borra todos los elementos de un hash_set.
count	Devuelve el número de elementos de un hash_set cuya clave coincide con una clave especificada por un parámetro.
hash_set::crbegin	Devuelve un iterador constante que direcciona el primer elemento de hash_set invertido.
hash_set::crend	Devuelve un iterador constante que direcciona la ubicación que sigue al último elemento de hash_set invertido.
hash_set::emplace	Inserta en un hash_set un elemento construido en contexto.
hash_set::emplace_hint	Inserta en un hash_set un elemento construido en contexto, con una sugerencia de colocación.
empty	Comprueba si un hash_set está vacío.
end	Devuelve un iterador que direcciona la ubicación que sigue al último elemento de hash_set.
equal_range	Devuelve un par de iteradores respectivamente al primer elemento de hash_set con una clave mayor que una clave especificada y al primer elemento de hash_set con una clave a la que sea igual o mayor que la clave.
erase	Quita un elemento o un intervalo de elementos de hash_set de posiciones especificadas o quita los elementos que coinciden con una clave especificada.
find	Devuelve un iterador que direcciona la ubicación de un elemento en un hash_set que tiene una clave equivalente a una clave especificada.
get_allocator	Devuelve una copia del objeto allocator utilizado para construir el hash_set.
insert	Inserta un elemento o un intervalo de elementos en un hash_set.
key_comp	Recupera una copia del objeto de comparación utilizado para ordenar claves de un hash_set.
lower_bound	Devuelve un iterador al primer elemento de hash_set con una clave a la que sea igual o mayor que una clave especificada.
max_size	Devuelve la longitud máxima del hash_set.
rbegin	Devuelve un iterador que direcciona el primer elemento de hash_set invertido.
rend	Devuelve un iterador que direcciona la ubicación que sigue al último elemento de hash_set invertido.
size	Devuelve el número de elementos de hash_set.
swap	Intercambia los elementos de dos hash_set.
upper_bound	Devuelve un iterador al primer elemento de hash_set que con una clave a la que sea igual o mayor que una clave especificada.
value_comp	Recupera una copia del objeto de los rasgos hash utilizado el hash y los valores de clave del elemento del orden en hash_set.