hash_set Class

Articolo
03/26/2013

[!NOTA]

Questo API è obsoleto.L'alternativa consiste unordered_set Class.

Il hash_set della classe contenitore è un'estensione della raccolta standard (STL) del modello e viene utilizzato per la registrazione e la ricerca veloce di dati da una raccolta in cui i valori degli elementi contenuti sono univoci e funge da valori della chiave.

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

Parametri

Key
Il tipo di dati degli elementi da archiviare in hash_set.
Traits
Il tipo che include due oggetti funzione, di una classe confronta che è un predicato binario in grado di confrontare due valori degli elementi come chiavi di ordinamento per determinare il relativo ordine relativo e una funzione hash che sono valori della chiave unari di un mapping di predicato di elementi agli Unsigned Integer di tipo size_t.Questo argomento è facoltativo e hash_compare*<Key,* less*<Key> >* è il valore predefinito.
Allocator
Il tipo che rappresenta l'oggetto memorizzato di allocatore che incapsula informazioni dettagliate sull'allocazione e la deallocazione di hash_set di memoria.Questo argomento è facoltativo e il valore predefinito è allocator*<Key>.*

Note

Il hash_set è:

Un contenitore di modifica associativo, che un contenitore variabile di dimensioni che supporti il recupero efficiente dei valori degli elementi in base a un valore di chiave collegato.Inoltre, è un contenitore associativo semplice perché i relativi valori dell'elemento sono i valori della chiave.
Reversibile, in quanto fornisce un iteratore bidirezionale per accedere ai relativi elementi.
Con hash, perché i relativi elementi sono raggruppati in bucket in base al valore di una funzione hash applicata ai valori della chiave degli elementi.
Univoco nel senso che ognuno dei relativi elementi deve avere una chiave univoca.Poiché il hash_set è un contenitore associativo semplice, i relativi elementi sono particolari.
Una classe modello perché la funzionalità disponibile in è generica e in modo indipendente dal tipo specifico di dati contenuti negli elementi o chiavi.I tipi di dati da utilizzare per gli elementi e le chiavi, invece, sono specificati come parametri nel modello della classe con la funzione di confronto e l'allocatore.

Il vantaggio principale di hashing nell'ordinamento è maggiore efficienza, una corrispondenza hashing esegue operazioni di inserimento, eliminazione e i trova nel tempo medio costante e non in un momento proporzionale al logaritmo il numero di elementi nel contenitore delle tecniche di ordinamento.Il valore di un elemento in un set non può essere modificato direttamente.Invece, è necessario eliminare i valori obsoleti e inserire gli elementi con i nuovi valori.

La scelta del tipo contenitore deve essere basata in generale sul tipo di ricerca e di inserimento richiesto dall'applicazione.I contenitori associativi con hash ottimizzate per le operazioni di ricerca, l'inserimento e la rimozione.Le funzioni membro che in modo esplicito supportano queste operazioni sono più efficaci quando vengono utilizzate con una funzione hash progettata correttamente, eseguendo li in un periodo di tempo nella costante media e non dipendente dal numero di elementi nel contenitore.Una funzione hash progettata correttamente produce una distribuzione uniforme di valori con hash e ridurre al minimo il numero di conflitti, in cui un conflitto è detto per verificare se i valori della chiave distinti mappati nello stesso valore con hash.Nel caso peggiore, con il più evidente funzione hash possibile, il numero di operazioni è proporzionale al numero di elementi della sequenza temporale (lineare).

Il hash_set deve essere il contenitore associativo di scelta quando le condizioni che associano valori con le chiavi vengono soddisfatte dall'applicazione.Gli elementi di un hash_set sono univoci e funge da rispettive chiavi di ordinamento.Un modello per questo tipo di struttura è un elenco ordinato ad esempio le parole in cui le parole possono verificarsi solo una volta.Se a più occorrenze delle parole sono consentite, un hash_multiset sarebbe la struttura appropriata del contenitore.Se i valori devono essere connessi a un elenco di parole chiave univoca, un hash_map sarebbe una struttura appropriata per contenere questi dati.Se invece le chiavi non sono univoci, un hash_multimap sarebbe il contenitore di scelta.

Il hash_set ordinare la sequenza che controlla chiamando un oggetto archiviato Traits hash di tipo value_compare.Questo oggetto archiviato può essere eseguito chiamando la funzione membro key_comp.Un oggetto funzione deve avere lo stesso come oggetto di classe hash_compare<Key, less<Key> >. In particolare, dato che tutti i valori _Key della chiave del tipo, il tratto di chiamata (_Key ) producono una distribuzione dei valori di size_t del tipo.

Gli elementi devono in genere essere solo minore di confrontabili di stabilire questo ordine: in modo da, specificando tutti gli due elementi, poter stabilire uno che sono equivalenti in quanto non è inferiore all'altro) o che ne è inferiore all'altro.Ciò comporta un ordine tra elementi antivalenti.In una più nota tecnica, la funzione di confronto è un predicato binario che provoca un ordine debole rigido nel senso matematico standard.Un predicato binario f(x,*y)*è un oggetto funzione che ha due oggetti dell'argomento x e y e un valore restituito true o false.Un ordine imposto a un hash_set è un ordine debole rigido se il predicato binario è irreflexive, antisimmetrico e transitivo e se l'equivalenza sia transitiva, in cui due oggetti x e y sono definiti come equivalenti quando entrambe f(x,y) e f(y,x) sono false.Se il più sicuro stato di uguaglianza tra le chiavi sostituisce quello di equivalenza, l'ordine diventa il totale (nel senso che tutti gli elementi vengono ordinati in base all'altro) e chiavi accoppiate siano indistinguibili l'uno da.

L'ordine effettivo di elementi della sequenza selezionata dipende dalla funzione hash, la funzione di ordine e dalla dimensione corrente della tabella hash nell'oggetto contenitore.Non è possibile determinare le dimensioni correnti di hash la tabella, pertanto non è possibile prevedere in generale l'ordine degli elementi nella sequenza selezionata.Inserendo gli elementi non invalida iteratori e rimozione di elementi invalida solo gli iteratori specificatamente avevano fa riferimento agli elementi eliminati.

Un iteratore fornito dalla classe di hash_set è un iteratore bidirezionale, ma il membro della classe funziona inserimento e hash_set dispone di versioni che accettano come parametri di template un iteratore di input più debole, con requisiti di funzionalità sono più minimi di quelli garantiti dalla classe di iteratori bidirezionali.I concetti diversi di iteratore formano una famiglia correlata dai perfezionamenti la funzionalità.Ogni concetto di iteratore dispone di un set di requisiti e gli algoritmi che utilizzano tali il limite di devono le ipotesi ai requisiti fornite da questo tipo di iteratore.Può essere presuppostoe che un iteratore di input è possibile dereferenziare per fare riferimento a un oggetto e che può essere incrementato all'iteratore successivo nella sequenza.Questo è un set minimo di funzionalità, ma è sufficiente da poter comunicare chiaramente su un intervallo degli iteratori [_First, _Lastnel contesto delle funzioni membro della classe.

In Visual C++ .NET 2003, i membri dei file di intestazione <hash_set> e <hash_map> non sono più nello spazio dei nomi di deviazione standard, ma sono stati spostati nello spazio dei nomi di stdext.Per ulteriori informazioni, vedere lo spazio dei nomi stdext.

Costruttori

hash_set

Costruisce hash_set che è vuoto o mediante la copia di tutto o parte di un altro hash_set.

Definizioni typedef

allocator_type	Un tipo che rappresenta la classe allocator per l'oggetto hash_set.
const_iterator	Un tipo che fornisce un iteratore bidirezionale che può leggere un elemento const in hash_set.
const_pointer	Un tipo che fornisce un puntatore a un elemento const in hash_set.
const_reference	Un tipo che fornisce un riferimento a un elemento const archiviare in hash_set per la lettura e l'esecuzione di operazioni const.
const_reverse_iterator	Un tipo che fornisce un iteratore bidirezionale in grado di leggere qualsiasi elemento const in hash_set.
difference_type	Un tipo interi con segno che può essere utilizzato per rappresentare il numero di elementi hash_set in un intervallo tra elementi indicato dagli iteratori.
iteratore	Un tipo che fornisce un iteratore bidirezionale in grado di leggere o modificare qualsiasi elemento in hash_set.
key_compare	Un tipo che fornisce un oggetto funzione che può confrontare due chiavi di ordinamento per determinare l'ordine relativo di due elementi in hash_set.
key_type	Un tipo che descrive un oggetto archiviato come elemento hash_set la capacità come chiave di ordinamento.
pointer	Un tipo che fornisce un puntatore a un elemento in hash_set.
riferimenti	Un tipo che fornisce un riferimento a un elemento ha archiviato in hash_set.
reverse_iterator	Un tipo che fornisce un iteratore bidirezionale in grado di leggere o modificare un elemento in hash_setinvertito.
size_type	Un tipo Integer senza segno che può rappresentare il numero di elementi in hash_set.
value_compare	Un tipo che fornisce due oggetti funzione, un predicato binario di classe confronta che può confrontare due valori degli elementi hash_set per determinare il relativo ordine relativo e un predicato unario che esegue l'hashing gli elementi.
value_type	Un tipo che descrive un oggetto archiviato come elemento hash_set la capacità come valore.

Funzioni membro

begin	Restituisce un iteratore destinato al primo elemento in hash_set.
hash_set::cbegin	Restituisce un iteratore const destinato al primo elemento in hash_set.
hash_set::cend	Restituisce un iteratore const destinato alla posizione che è l'ultimo elemento a hash_set.
clear	Cancella tutti gli elementi hash_set.
Conteggio	Restituisce il numero di elementi in hash_set di cui la chiave corrisponde a una chiave parametro- specificata.
hash_set::crbegin	Restituisce un iteratore const destinato al primo elemento in hash_setinvertito.
hash_set::crend	Restituisce un iteratore const destinato alla posizione che è l'ultimo elemento a hash_setinvertito.
hash_set::emplace	Inserire un elemento costruito sul posto in hash_set.
hash_set::emplace_hint	Inserire un elemento costruito sul posto in hash_set, con un suggerimento di posizione.
empty	Test hash_set se è vuoto.
end	Restituisce un iteratore destinato alla posizione che è l'ultimo elemento a hash_set.
equal_range	Restituisce una coppia degli iteratori rispettivamente al primo elemento in hash_set con una chiave maggiore di una chiave specificata e il primo elemento in hash_set con una chiave a uguale a o maggiore della chiave.
con	Rimuove un elemento o un intervallo di elementi in hash_set da percorsi specificati o rimuove gli elementi che soddisfano una chiave specificata.
find	Restituisce un iteratore destinato alla posizione di un elemento in hash_set con un equivalente principale in una chiave specificata.
get_allocator	Restituisce una copia dell'oggetto allocator utilizzato per costruire hash_set.
inserimento	Inserire un elemento o un intervallo di elementi in hash_set.
key_comp	Recupera una copia dell'oggetto di confronto utilizzato alle chiavi di ordinamento in hash_set.
lower_bound	Restituisce un iteratore il primo elemento in hash_set con una chiave a cui è uguale o superiore alla chiave specificata.
max_size	Restituisce la lunghezza massima hash_set.
rbegin	Restituisce un iteratore destinato al primo elemento in hash_setinvertito.
rend	Restituisce un iteratore destinato alla posizione che è l'ultimo elemento a hash_setinvertito.
size	Restituisce il numero di elementi in hash_set.
scambio	Scambia gli elementi di due hash_setS.
upper_bound	Restituisce un iteratore il primo elemento in hash_set che con una chiave a cui è uguale o superiore alla chiave specificata.
value_comp	Recupera una copia dei tratti di hash oggetto utilizzato per l'hashing e ordinare i valori della chiave dell'elemento in hash_set.