hash_map Class

Artigo
03/14/2013

Observação
este API é obsoleto.Uma alternativa é unordered_map Class.

Armazenar e recuperar dados rapidamente de uma coleção em que cada elemento é um controle que tem uma chave de tipo cujo valor é exclusivo e um valor de dados associado.

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

Parâmetros

Chave
O tipo de dados principal para ser armazenado no hash_map.
Tipo
O elemento tipo de dados a ser armazenado no hash_map.
Traits
O tipo que inclui dois objetos de função, uma classe de compara capaz de comparar dois valores de elemento como chaves de tipo para determinar a ordem relativa e uma função de hash que é um predicado unário que mapeia chave valores dos elementos em números inteiros sem sinal de tipo size_t.Esse argumento é opcional, e hash_compare<Key, less<Key> > é o valor padrão.
Allocator
O tipo que representa o objeto armazenado do distribuidor que encapsula detalhes sobre a alocação e a desalocação de hash_map de memória.Esse argumento é opcional, e o valor padrão é allocator<pair <const principal, tipo**> >**.

Comentários

o hash_map é:

Um contêiner associativo, enquanto um contêiner variável de tamanho que ofereça suporte a recuperação eficiente de valores de elemento baseasse em um valor de chave associada.
Reversível, porque ele fornece um iterador bidirecional para acessar seus elementos.
De hash, porque seus elementos são agrupados de compartimentos de memória com base no valor de uma função de hash aplicada aos valores da chave de elementos.
Exclusivo no sentido que cada um dos seus elementos deve ter uma chave exclusiva.
Um contêiner associativo de pares, porque seus valores de dados do elemento são distintos de seus valores chave.
Uma classe de modelo, porque a funcionalidade que fornece é genérico e portanto independente do tipo específico de dados contidos como elementos ou chaves.Os tipos de dados para ser usados para os elementos e as chaves, em vez de isso, são especificados como parâmetros no modelo de classe juntamente com a função e o distribuidor de comparação.

A principal vantagem de hash sobre a classificação é maior eficiência; um hash com êxito executa inserções, exclusões, e localiza no momento da média da constante em comparação para um horário proporcionais ao logaritmo o número de elementos no recipiente para técnicas de classificação.O valor de um elemento em um hash_map, mas não o valor da chave associado, pode ser alterado diretamente.Em vez de isso, os valores associados com os principais elementos devem ser excluídos antigos e novos valores chave ser associados com os novos elementos inseridos.

A escolha do tipo recipiente deve ser geralmente com base no tipo de pesquisa e de inserir exigido pelo aplicativo.Contêiners associativos formatadas em hash são otimizados para operações de pesquisa, de inserção e remoção.As funções de membro que suportam explicitamente essas operações são eficientes quando usadas com uma função de hash bem estruturado, executando as em um horário que estão na constante intermediária e não dependente no número de elementos no contêiner.Uma função de hash bem estruturado gera uma uniforme distribuição de valores formatadas em hash e minimiza o número de conflitos, onde é uma colisão determina ocorrer quando os valores principais distintas são mapeados no mesmo valor de hash.Em o caso mais grave, com a função de hash possível a pior, o número de operações é proporcionalmente para o número de elementos na seqüência tempo linear ().

O hash_map deve ser o contêiner associativo de opção quando as condições que associa os valores com suas chaves forem atendidas pelo aplicativo.Um modelo para esse tipo de estrutura é uma lista ordenada exclusivamente de ocorrer palavra-chave com os valores da cadeia de caracteres associadas que fornecem por exemplo definições.Se, em vez de isso, a palavra tinham mais de uma definição correta, de modo que as chaves não são exclusivos, então um hash_multimap seria o contêiner de escolha.Se, por outro lado, apenas a lista de palavras foi armazenada, então um hash_set seria o contêiner correto.Se várias ocorrências da palavra foram permitidas, então um hash_multiset seria a estrutura do recipiente apropriado.

O hash_map da seqüência que controla chamando um objeto armazenado Traits de hash da classe value_compare.Este objeto armazenado pode ser acessado chamar a função de membro key_comp.Tal objeto de função deve se comportar o mesmo que um objeto da classe hash_compare<Key, less<Key>>.Especificamente, para todos os valores _Key de tipo Chave, a chamada Traits(_Key ) produzem uma distribuição dos valores do tipo size_t.

Geralmente, os elementos precisam ser simplesmente menor que comparáveis estabelecer ordem: para que, dado todos os dois elementos, pode determinar se qualquer um que são equivalentes (no sentido que nenhum for menor do que o outro) ou um que é menor que o outro.Isso resulta em ordenação entre elementos nonequivalent.Em uma nota mais técnica, a função de comparação binária é um predicado que induza ordenação fraco strict no sentido matemático padrão.Um predicado fde binária (x,*y)*é um objeto de função que tem dois objetos de argumento x e y e um valor de retorno de true ou de false.Uma Classificação aplicada em um hash_map é ordenação livre restrita se o predicado binária é irreflexive, anti-simétrico, e transitivo e se equivalências é transitiva, onde dois objetos x e y são definidos para ser equivalentes enquanto tanto f(x,y) e f(y,x) são falsos.Se a condição mais segura de igualdade entre chaves substitui os de equivalência, então ordenação transformações total (no sentido que todos os elementos são ordenados em relação a se) e chaves correspondidas serão indiscerníveis de se.

A ordem real de elementos na seqüência controlada depende da função de hash, função, classificação e de tamanho atual de tabela de hash armazenado no objeto contêiner.Você não pode determinar o tamanho atual de hash a tabela, para que você não pode prever em geral a ordem dos elementos na seqüência controlada.Inserindo os elementos não invalida nenhum iterador, e remover elementos invalida somente os iteradores que eles tivessem apontada especificamente em elementos removidos.

O iterador fornecido pela classe de hash_map é um iterador bidirecional, mas as funções de membro inserção e hash_map de classe têm as versões que recebem como parâmetros de modelo um iterador mais flexível de entrada, cujos requisitos mínimos de funcionalidade sejam mais do que aquelas se a classe de iteradores bidirecionais.Os conceitos diferentes de iterador formam uma família relacionada por refinamentos em sua funcionalidade.Cada conceito de iterador tem seu próprio conjunto de requisitos, e os algoritmos que funcionam com eles o limite de deve as suposições os requisitos fornecidos pelo tipo de iterador.Pode-se suponha que um iterador de entrada pode ser desreferenciado para referir-se a qualquer objeto e que pode ser iterador incrementado a seguir na seqüência.Este é um conjunto mínimo de funcionalidade, mas é suficiente para poder falar significativa sobre um intervalo de iteradores [_First, _Last) no contexto das funções de membro da classe.

Em o Visual C++ .NET 2003, os membros dos arquivos de cabeçalho de <hash_map> e de <hash_set> não estão mais no namespace de STD, mas tenham sido portados em vez de stdext no namespace.Consulte O namespace de stdext para mais informações.

Construtores

hash_map

Constrói hash_map que está vazio ou que é uma cópia de todo ou parte de qualquer outro hash_map.

Typedefs

allocator_type	Um tipo que representa a classe de allocator para o objeto de hash_map .
const_iterator	Um tipo que fornece um iterador bidirecional que possa ler um elemento de const em hash_map.
const_pointer	Um tipo que provê um ponteiro para um elemento de const em hash_map.
const_reference	Um tipo que fornecesse uma referência a um elemento de const armazenado em hash_map para ler e executar operações de const .
const_reverse_iterator	Um tipo que fornece um iterador bidirecional que pode ler qualquer elemento de const em hash_map.
difference_type	Um tipo de inteiro com sinal que pode ser usado para representar o número de elementos de hash_map em um intervalo entre elementos. apontado por iteradores
iterador	Um tipo que fornece um iterador bidirecional que pode ler ou modificar qualquer elemento em hash_map.
key_compare	Um tipo que provê um objeto de função que pode comparar duas chaves de tipo para determinar a ordem relativo de dois elementos em hash_map.
key_type	Um tipo descreve o objeto de chave de tipo que constitui cada elemento de hash_map.
mapped_type	Um tipo que representa o tipo de dados armazenados em hash_map.
ponteiro	Um tipo que provê um ponteiro para um elemento em hash_map.
referência	Um tipo que fornecesse uma referência a um elemento armazenado em hash_map.
reverse_iterator	Um tipo que fornece um iterador bidirecional que pode ler ou modificar um elemento em hash_mapinvertido.
size_type	Um tipo inteiro sem sinal de que possa representar o número de elementos em hash_map.
value_type	Um tipo que provê um objeto de função que possa comparar dois elementos como chaves de tipo para determinar a ordem em hash_maprelativo.

funções de membro

hash_map::at	Localizar um elemento em hash_map com um valor de chave especificado.
inicie	Retorna um iterador que trata o primeiro elemento em hash_map.
hash_map::cbegin	Retorna um iterador const que trata o primeiro elemento em hash_map.
hash_map::cend	Retorna um iterador const atende o local que é bem-sucedido o último elemento em hash_map.
espaço livre	apaga todos os elementos de hash_map.
contagem	Retorna o número de elementos em hash_map cuja chave corresponde a uma chave parâmetro- especificada.
hash_map::crbegin	Retorna um iterador const que trata o primeiro elemento em hash_mapinvertido.
hash_map::crend	Retorna um iterador const atende o local que é bem-sucedido o último elemento em hash_mapinvertido.
hash_map::emplace	Insere um elemento construído no lugar em hash_map.
hash_map::emplace_hint	Insere um elemento construído no lugar em hash_map, com uma dica de posicionamento.
vazio	Teste se hash_map está vazia.
end	Retorna um iterador atende o local que é bem-sucedido o último elemento em hash_map.
equal_range	Retorna um par de iteradores, respectivamente, para o primeiro elemento em hash_map com uma chave que é maior do que uma chave especificada e o primeiro elemento em hash_map com uma chave para que é igual ou maior do que a chave.
erase	Remove um elemento ou um intervalo de elementos em hash_map das posições especificadas
localizar	Retorna um iterador que trata o local de um elemento em hash_map que tenha um principal equivalente a uma chave especificada.
get_allocator	Retorna uma cópia do objeto de allocator usado para construir hash_map.
inserção	Insere um elemento ou um intervalo de elementos em hash_map.
key_comp	Retorna um iterador para o primeiro elemento em hash_map com um valor de chave que é igual ou maior do que de uma chave especificada.
lower_bound	Retorna um iterador para o primeiro elemento em hash_map com um valor de chave que é igual ou maior do que de uma chave especificada.
max_size	retorna o comprimento máximo de hash_map.
rbegin	Retorna um iterador que trata o primeiro elemento em hash_mapinvertido.
arrancar	Retorna um iterador atende o local que é bem-sucedido o último elemento em hash_mapinvertido.
tamanho	retorna o número de elementos em hash_map.
troca	Troca os elementos de hash_mapdois S.
upper_bound	Retorna um iterador para o primeiro elemento em hash_map que com um valor de chave que é maior do que a de uma chave especificada.
value_comp	Recupera uma cópia do objeto de comparação usado para valores do elemento da ordem em hash_map.

Operadores

operador []	Insere um elemento em hash_map com um valor de chave especificado.
hash_map::operator=	Substitui os elementos de hash_map com uma cópia de outro hash_map.