hash_map (Clase)

Artículo
06/09/2015

Nota

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

Almacena y recupera datos rápidamente de una colección en la que cada elemento es un par que tiene una clave de ordenación cuyo valor es único y un valor de datos asociado.

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

Parámetros

Key
Tipo de datos de clave que se almacenará en hash_map.
Type
Tipo de datos de elemento que se almacenará en hash_map.
Traits
Tipo que incluye dos objetos de función: uno de clase compare que puede comparar dos valores de elemento como claves de ordenación para determinar su orden relativo y una función hash que es un predicado unario que asigna valores de clave de los elementos a enteros sin signo de tipo size_t. Este argumento es opcional, y hash_compare<Key, less<Key> > es el valor predeterminado.
Allocator
Tipo que representa el objeto de asignador almacenado que encapsula los detalles acerca de la asignación y desasignación de memoria de hash_map. Este argumento es opcional y el valor predeterminado es allocator<pair <const Key, Type>>.

Comentarios

hash_map 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.
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.
Un contenedor asociativo de pares, ya que los valores de datos de sus elementos son distintos de sus valores de clave.
Una clase de plantilla, porque la funcionalidad que proporciona es genérica y por tanto 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 de hash_map se puede cambiar directamente, pero no su valor de clave asociado. En su lugar, se deben eliminar los valores de clave asociados a los antiguos elementos e insertar los nuevos valores de clave asociados a los elementos nuevos.

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_map debe ser el contenedor asociativo preferido cuando la aplicación satisfaga las condiciones que asocian los valores a sus claves. Un modelo de este tipo de estructura es una lista ordenada de palabras clave únicas con valores de cadena asociados que proporcionan, por ejemplo, definiciones. Si por el contrario las palabras tienen más una definición correcta, de modo que las claves no son únicas, el contenedor más adecuado sería hash_multimap. Por otra parte, si solo se va a almacenar la lista de palabras, el contenedor correcto sería hash_set. Si se permiten varias repeticiones de las palabras, la estructura de contenedor adecuada sería hash_multiset.

El hash_map ordena la secuencia que controla llamando a un objeto Traits hash almacenado de clase value_compare. Se puede obtener acceso a este objeto almacenado llamando a la función miembro key_comp. Este tipo de objeto de función debe comportarse igual que un objeto de clase hash_compare<Key, less<Key>>. En concreto, para todos los valores Key de tipo Key, la llamada a Traits(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. Un predicado binario f(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. Una ordenación impuesta en un hash_map es una ordenación débil estricta si el predicado binario es irreflexivo, antisimétrico y transitivo, y si la equivalencia es transitiva, donde dos objetos x e y se definen como equivalentes cuando tanto f(x, y) como f(y, x) son 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 hash_map es un iterador bidireccional, pero las funciones miembro de clase insert y hash_map tienen versiones que toman como parámetros de plantilla un iterador de entrada más débil, 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. Se trata de un conjunto mínimo de funcionalidad, pero es suficiente para poder comunicarse 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_map

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

Typedefs

allocator_type	Tipo que representa la clase allocator para el objeto hash_map.
const_iterator	Tipo que proporciona un iterador bidireccional que puede leer un elemento const en hash_map.
const_pointer	Tipo que proporciona un puntero a un elemento const en un hash_map.
const_reference	Tipo que proporciona una referencia a un elemento const almacenado en un hash_map para leer y realizar operaciones const.
const_reverse_iterator	Tipo que proporciona un iterador bidireccional que puede leer cualquier elemento const en hash_map.
difference_type	Tipo entero con signo que se puede usar para representar el número de elementos de un hash_map 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_map.
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_map.
key_type	Tipo que describe el objeto de clave de ordenación que constituye cada elemento de hash_map.
mapped_type	Tipo que representa el tipo de datos almacenados en un hash_map.
puntero	Tipo que proporciona un puntero a un elemento de hash_map.
reference	Tipo que proporciona una referencia a un elemento almacenado en un hash_map.
reverse_iterator	Tipo que proporciona un iterador bidireccional que puede leer o modificar un elemento de hash_map invertido.
size_type	Tipo entero sin signo que puede representar el número de elementos de un hash_map.
value_type	Tipo que proporciona un objeto de función que puede comparar dos elementos como claves de ordenación para determinar su orden relativo en el hash_map.

Funciones miembro

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

Operadores

operator[]	Inserta un elemento en un hash_map con un valor de clave especificado.
hash_map::operator=	Reemplaza los elementos de un hash_map con una copia de otro hash_map.