Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::unordered_set — un insieme di chiavi univoche

std::unordered_set memorizza chiavi univoche usando l’hashing. Consente di verificare la presenza, inserire e rimuovere elementi senza garantire l’ordine di iterazione. Le operazioni comuni hanno complessità media costante, ma lineare nel caso peggiore.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#include <unordered_set>
std::unordered_set<Key, Hash, Pred, Allocator> values;
// Defaults: Hash = std::hash<Key>, Pred = std::equal_to<Key>,
// Allocator = std::allocator<Key>

std::unordered_set di <unordered_set> è un contenitore associativo non ordinato: ogni elemento è anche la propria chiave e l’insieme contiene al massimo un elemento per ciascuna classe di equivalenza. I parametri Hash e Pred definiscono l’hashing e l’equivalenza; i valori predefiniti sono std::hash<Key> e std::equal_to<Key>. Le chiavi equivalenti devono avere lo stesso hash; hash uguali non implicano che le chiavi siano equivalenti.

insert(value).second indica se è stato aggiunto un elemento. contains(value) verifica la presenza, find(value) restituisce un iteratore oppure end(), mentre erase(value) restituisce il numero di elementi rimossi: in questo caso, 0 o 1. La ricerca, l’inserimento di un singolo elemento e la rimozione per chiave hanno complessità media O(1) e complessità O(n) nel caso peggiore.

L’ordine di iterazione non è specificato. Non è possibile modificare le chiavi tramite gli iteratori; occorre invece rimuovere la vecchia chiave e inserirne una nuova. Il rehash invalida gli iteratori, ma non i puntatori né i riferimenti agli elementi. Un inserimento può attivare un rehash; reserve(n) prepara un numero sufficiente di bucket per n elementi con il fattore di carico massimo corrente e può anch’esso invalidare gli iteratori. La rimozione di un elemento invalida i suoi iteratori, puntatori e riferimenti.

L’esempio non stampa gli elementi tramite iterazione, quindi il risultato atteso non dipende dal loro ordine. Questa voce è riferita a C++23; un’opzione del compilatore nel repository non certifica l’ambiente di produzione. La bozza di lavoro fornita viene aggiornata nel tempo e può includere funzionalità successive a C++23.

Esempi

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> values{3, 1, 3};
    const bool inserted = values.insert(1).second;

    std::cout << std::boolalpha;
    std::cout << "inserted: " << inserted << '\n';
    std::cout << "contains 3: " << values.contains(3) << '\n';
    std::cout << "erased: " << values.erase(3) << '\n';
    std::cout << "size: " << values.size() << '\n';
}

Risultato

inserted: false
contains 3: true
erased: 1
size: 1

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti