hash_map Class

Articolo
03/26/2013

[!NOTA]

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

Archivia rapidamente e recuperano dati da una raccolta in cui ogni elemento è una coppia che dispone di una chiave di ordinamento del cui valore è univoco e un valore di dati collegato.

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

Parametri

Chiave
Il tipo di dati chiave da archiviare in hash_map.
Type
Il tipo di dati degli elementi da archiviare in hash_map.
Traits
Il tipo che include due oggetti funzione, di una classe confronta 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<imposta, less<imposta> > è il valore predefinito.
Allocator
Il tipo che rappresenta l'oggetto memorizzato di allocatore che incapsula informazioni dettagliate sull'allocazione e la deallocazione di hash_map di memoria.Questo argomento è facoltativo e il valore predefinito è allocator<pair <const principale, il tipo**> >**.

Note

Il hash_map è:

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.
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.
Un contenitore di modifica associativo della coppia, in quanto i valori di dati degli elementi sono diversi dai valori della chiave.
Una classe modello, poiché 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 hash_map, ma non il valore della chiave collegato, può essere modificato direttamente.Invece, i valori della chiave associati a elementi obsoleti devono essere eliminati e nuovi valori della chiave essere associati ai nuovi elementi inseriti.

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_map deve essere il contenitore associativo di scelta quando le condizioni che associano valori con le chiavi vengono soddisfatte dall'applicazione.Un modello per questo tipo di struttura è un elenco ordinato delle parole chiave in modo univoco verificantesi con valori stringa collegati che forniscono ad esempio le definizioni.Se, invece, le parole hanno più definizioni corretta, in modo che le chiavi non sono univoche, un hash_multimap sarebbe il contenitore di scelta.Se, invece, solo nell'elenco di parole stesse archiviazione, un hash_set sarebbe il contenitore corretto.Se a più occorrenze delle parole sono consentite, un hash_multiset sarebbe la struttura appropriata del contenitore.

Il hash_map ordinare la sequenza che controlla chiamando un oggetto archiviato Traits hash di classe value_compare.Questo oggetto archiviato può essere eseguito chiamando la funzione membro key_comp.Un oggetto funzione deve avere lo stesso di oggetto classe hash_compare<Key, less<Key>>.In particolare, per i valori _Key di tipo Chiave, la chiamata Traits(_Key ) producono una distribuzione di valori di tipo size_t.

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_map è 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_map è un iteratore bidirezionale, ma il membro della classe funziona inserimento e hash_map 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, _Last nel 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_map

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

Definizioni typedef

allocator_type	Un tipo che rappresenta la classe allocator per l'oggetto hash_map.
const_iterator	Un tipo che fornisce un iteratore bidirezionale che può leggere un elemento const in hash_map.
const_pointer	Un tipo che fornisce un puntatore a un elemento const in hash_map.
const_reference	Un tipo che fornisce un riferimento a un elemento const archiviare in hash_map 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_map.
difference_type	Un tipo interi con segno che può essere utilizzato per rappresentare il numero di elementi hash_map 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_map.
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_map.
key_type	Un tipo viene illustrato l'oggetto della chiave di ordinamento che costituiscono ogni elemento hash_map.
mapped_type	Un tipo che rappresenta il tipo di dati è archiviato in hash_map.
pointer	Un tipo che fornisce un puntatore a un elemento in hash_map.
riferimenti	Un tipo che fornisce un riferimento a un elemento ha archiviato in hash_map.
reverse_iterator	Un tipo che fornisce un iteratore bidirezionale in grado di leggere o modificare un elemento in hash_mapinvertito.
size_type	Un tipo Integer senza segno che può rappresentare il numero di elementi in hash_map.
value_type	Un tipo che fornisce un oggetto funzione che può confrontare due elementi come chiavi di ordinamento per determinare il relativo ordine relativo a hash_map.

Funzioni membro

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

Operatori

operator[]	Inserisce un elemento in hash_map con un valore di chiave specificato.
hash_map::operator=	Sostituisce gli elementi hash_map con una copia di un altro hash_map.