Classe unordered_set

Articolo
06/09/2015

La classe modello descrive un oggetto che controlla una sequenza di elementi di lunghezza diversa di tipo const Key. La sequenza viene ordinata in modo debole da una funzione hash, che esegue il partizionamento della sequenza in un set ordinato di sottosequenze denominate bucket. In ogni bucket una funzione di confronto determina se una coppia di elementi ha un ordinamento equivalente. Ogni elemento viene utilizzato sia come chiave di ordinamento che come valore. La sequenza viene rappresentata in modo da consentire la ricerca, l'inserimento e la rimozione di un elemento arbitrario mediante una serie di operazioni che possono essere indipendenti dal numero di elementi della sequenza (tempo costante), almeno quando tutti i bucket sono più o meno lunghi uguali. Nella peggiore delle ipotesi, quando tutti gli elementi si trovano in un unico bucket, il numero di operazioni è proporzionale al numero di elementi della sequenza (tempo lineare). Inoltre, l'inserimento di un elemento non invalida gli iteratori e la rimozione di un elemento invalida solo gli iteratori che fanno riferimento all'elemento rimosso.

template<class Key,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_set;

Parametri

Parametro	Descrizione
Key	Tipo di chiave.
Hash	Tipo di oggetto della funzione hash.
Pred	Tipo di oggetto della funzione di confronto di uguaglianza.
Alloc	Classe Allocator.

Membri

Definizione dei tipi	Descrizione
unordered_set::allocator_type	Tipo di un allocatore per gestire l'archiviazione.
unordered_set::const_iterator	Tipo di un iteratore costante per la sequenza controllata.
unordered_set::const_local_iterator	Tipo di un iteratore di bucket costante per la sequenza controllata.
unordered_set::const_pointer	Tipo di un puntatore costante a un elemento.
unordered_set::const_reference	Tipo di un riferimento costante a un elemento.
unordered_set::difference_type	Tipo di una distanza Signed tra due elementi.
unordered_set::hasher	Tipo della funzione hash.
unordered_set::iterator	Tipo di un iteratore per la sequenza controllata.
unordered_set::key_equal	Tipo della funzione di confronto.
unordered_set::key_type	Tipo di una chiave di ordinamento.
unordered_set::local_iterator	Tipo di un iteratore di bucket per la sequenza controllata.
unordered_set::pointer	Tipo di un puntatore a un elemento.
unordered_set::reference	Tipo di un riferimento a un elemento.
unordered_set::size_type	Tipo di una distanza Unsigned tra due elementi.
unordered_set::value_type	Tipo di un elemento.

Funzione membro	Descrizione
unordered_set::begin	Indica l'inizio della sequenza controllata.
unordered_set::bucket	Ottiene il numero di bucket relativo a un valore della chiave.
unordered_set::bucket_count	Ottiene il numero di bucket.
unordered_set::bucket_size	Ottiene le dimensioni di un bucket.
unordered_set::cbegin	Indica l'inizio della sequenza controllata.
unordered_set::cend	Indica la fine della sequenza controllata.
unordered_set::clear	Rimuove tutti gli elementi.
unordered_set::count	Trova il numero di elementi corrispondenti a una chiave specificata.
unordered_set::emplace	Aggiunge un elemento costruito sul posto.
unordered_set::emplace_hint	Aggiunge un elemento costruito sul posto, con il suggerimento.
unordered_set::empty	Verifica se sono presenti o meno degli elementi.
unordered_set::end	Indica la fine della sequenza controllata.
unordered_set::equal_range	Trova un intervallo che corrisponde a una chiave specificata.
unordered_set::erase	Rimuove gli elementi in corrispondenza delle posizioni specificate.
unordered_set::find	Trova un elemento che corrisponde a una chiave specificata.
unordered_set::get_allocator	Ottiene l'oggetto allocatore archiviato.
unordered_set::hash_function	Ottiene l'oggetto della funzione hash archiviato.
unordered_set::insert	Aggiunge elementi.
unordered_set::key_eq	Ottiene l'oggetto archiviato della funzione di confronto.
unordered_set::load_factor	Conta il numero medio di elementi per bucket.
unordered_set::max_bucket_count	Ottiene il numero massimo di bucket.
unordered_set::max_load_factor	Ottiene o imposta il numero massimo di elementi per bucket.
unordered_set::max_size	Ottiene la dimensione massima della sequenza controllata.
unordered_set::rehash	Ricompila la tabella hash.
unordered_set::size	Conta il numero di elementi.
unordered_set::swap	Scambia il contenuto di due contenitori.
unordered_set::unordered_set	Costruisce un oggetto contenitore.

Operatori	Descrizione
unordered_set::operator=	Copia una tabella hash.

Note

L'oggetto ordina la sequenza da esso controllata chiamando due oggetti archiviati, un oggetto della funzione di confronto di tipo unordered_set::key_equal e un oggetto della funzione hash di tipo unordered_set::hasher. È possibile accedere al primo oggetto archiviato chiamando la funzione membro unordered_set::key_eq() ed è possibile accedere al secondo oggetto archiviato chiamando la funzione membro unordered_set::hash_function(). In particolare, per tutti i valori X e Y di tipo Key, la chiamata a key_eq()(X, Y) restituisce true solo se i valori dei due argomenti hanno un ordinamento equivalente; la chiamata a hash_function()(keyval) produce una distribuzione di valori di tipo size_t. A differenza della classe modello Classe unordered_multiset, un oggetto della classe modello unordered_set garantisce che key_eq()(X, Y) sia sempre false per due elementi qualsiasi della sequenza controllata. Le chiavi sono univoche.

L'oggetto consente inoltre di archiviare un fattore di carico massimo che specifica il numero medio massimo di elementi per bucket desiderato. Se l'inserimento di un elemento comporta un superamento del fattore di carico massimo da parte di unordered_set::load_factor(), il contenitore aumenta il numero dei bucket e ricompila la tabella hash in base alle necessità.

L'ordine effettivo degli elementi nella sequenza controllata dipende dalla funzione hash, dalla funzione di confronto, dall'ordine di inserimento, dal fattore di carico massimo e dal numero corrente di bucket. Non è in genere possibile prevedere l'ordine degli elementi nella sequenza selezionata. Si può tuttavia avere sempre la certezza dell'adiacenza dei subset di elementi con un ordinamento equivalente nella sequenza controllata.

L'oggetto alloca e libera la memoria per la sequenza da esso controllata tramite un oggetto allocatore archiviato di tipo unordered_set::allocator_type. Tale oggetto allocatore deve avere la stessa interfaccia esterna di un oggetto della classe modello allocator. Si noti che l'oggetto allocatore archiviato non viene copiato dopo l'assegnazione dell'oggetto contenitore.