hash_set Class

Artigo
03/14/2013

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

O hash_set da classe recipiente é uma extensão de biblioteca padrão (STL) do modelo e é usado para armazenamento e recuperação rápida de dados de uma coleção em que os valores dos elementos contidos são exclusivos e serve como os valores chave.

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

Parâmetros

Key
O elemento tipo de dados a ser armazenado no hash_set.
Traits
O tipo que inclui dois objetos de função, uma classe de compara que é um predicado binário 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 o 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_set de memória.Esse argumento é opcional, e o valor padrão é allocator*<Key>.*

Comentários

o hash_set é:

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.Além de isso, é um contêiner associativo simples porque seus valores de elemento são os valores chave.
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.Porque o hash_set também é um contêiner associativo simples, seus elementos também são exclusivos.
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 dataset não pode ser alterado diretamente.Em vez de isso, você deve excluir valores antigo e inserir os elementos com novos valores.

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_set deve ser o contêiner associativo de opção quando as condições que associa os valores com suas chaves forem atendidas pelo aplicativo.Os elementos de um hash_set são exclusivos e serve como suas próprias chaves de tipo.Um modelo para esse tipo de estrutura é ordenada por exemplo uma lista de palavras em que a palavra podem ocorrer apenas uma vez.Se várias ocorrências da palavra foram permitidas, então um hash_multiset seria a estrutura do recipiente apropriado.Se os valores precisam ser anexados a uma lista de palavras chaves de chave exclusiva, então um hash_map seria uma estrutura apropriado para conter esses dados.Se o invés das chaves não são exclusivos, então um hash_multimap seria o contêiner de escolha.

O hash_set da seqüência que controla chamando um objeto armazenado Traits de hash do tipo 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 de classe hash_compare<Key, less<Key> >. Especificamente, porque todos os valores _Key de chave do tipo, o sublinhado () da chamada_Key produz uma distribuição dos valores de size_t do tipo.

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 que não são do equivalente.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 verdadeiro ou falso.Uma classificação aplicada em um hash_set é 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_set é um iterador bidirecional, mas as funções de membro inserção e hash_set 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_set

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

Typedefs

allocator_type	Um tipo que representa a classe de allocator para o objeto de hash_set .
const_iterator	Um tipo que fornece um iterador bidirecional que possa ler um elemento de const em hash_set.
const_pointer	Um tipo que provê um ponteiro para um elemento de const em hash_set.
const_reference	Um tipo que fornecesse uma referência a um elemento de const armazenado em hash_set 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_set.
difference_type	Um tipo de inteiro com sinal que pode ser usado para representar o número de elementos de hash_set 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_set.
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_set.
key_type	Um tipo que descreve um objeto armazenado como um elemento de hash_set em sua capacidade como a chave de tipo.
ponteiro	Um tipo que provê um ponteiro para um elemento em hash_set.
referência	Um tipo que fornecesse uma referência a um elemento armazenado em hash_set.
reverse_iterator	Um tipo que fornece um iterador bidirecional que pode ler ou modificar um elemento em hash_setinvertido.
size_type	Um tipo inteiro sem sinal de que possa representar o número de elementos em hash_set.
value_compare	Um tipo que fornece dois objetos de função, um predicado binária da classe compara que possa comparar dois valores de elemento de hash_set para determinar a ordem relativa e um predicado unário que divida elementos.
value_type	Um tipo que descreve um objeto armazenado como um elemento de hash_set em sua capacidade como um valor.

funções de membro

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