Dato due std::set s, è possibile semplicemente eseguire iterazioni su entrambi gli insiemi contemporaneamente e confrontare gli elementi, con conseguente complessità lineare. Questo non funziona per std::unordered_set s, perché gli elementi possono essere memorizzati in qualsiasi ordine. Quindi quanto è costoso a == b per std::unordered_set?Quanto costa mettere a confronto due set non ordinati per l'uguaglianza?
Complessità operator== e operator!=:
complessità lineare nel caso medio. N nel caso peggiore, dove N è la dimensione del contenitore.
Maggiori dettagli nel §23.2.5 norma, punto 11:
Per unordered_set e unordered_map, la complessità di operator== (cioè, il numero di chiamate al == operatore del value_type, al predicato restituito da key_equal(), ed al hasher restituito da hash_function()) è proporzionale alla N nel caso medio e N 2 nel caso peggiore, dove N è a.size().
Il caso peggiore è O (n²).
Ma i set non ordinati sono in effetti ordinati per hash. Quindi è possibile confrontare gli hash (se ciò non riesce i set non possono essere uguali) e quindi verificare che gli stessi hash (lineari) abbiano gli stessi valori reali (O (n²) per diversi valori con lo stesso hash) dietro.
Nel migliore dei casi questo è O (n).
Normalmente la complessità tende a O (n) se la funzione di hash è "buona" (oggetti diversi -> hash sempre diverso) e a O (n²) se la funzione di hash è "cattiva" (tutto ha sempre lo stesso valore hash)
"la funzione di hash è buona (oggetti diversi -> hash sempre diversi)" -> diversi hash possono essere veri anche per un terribile algoritmo di hash (ad es. Stringhe hash fino a 128 caratteri restituendo un valore hash 8 * a 128 bit clonato da la stringa), ma mod quello nel numero di secchi e il risultato è brutto. Quando non ci sono particolari informazioni sugli input che facilitano l'evitamento della collisione, una buona modificazione della funzione hash in genere ha collisioni nel rapporto tra i bucket usati e quelli non utilizzati ... il che risulta comunque nelle medie O (n). –
@TonyDelroy: Grazie per aver segnalato questo! Un "buon hash" non deve solo restituire "valori diversi", ma anche "ben distribuiti" rispetto ai secchi (lo spazio dell'hash dovrebbe essere uniforme e primo rispetto ai secchi, solo per minimizzare l'effetto che si menziona) –
Avete un modo efficace per controllare l'appartenenza al set (ad esempio sono supportati da hashtables)? – Thilo
Nelle parole chiare, semplici, comprensibili e comprensibili dello standard C++: "Due contenitori non ordinati' a' e 'b' sono uguali se' a.size() == b.size() 'e, per ogni gruppo di chiavi equivalenti '[Ea1, Ea2)' ottenuto da 'a.equal_range (Ea1)', esiste un gruppo di chiavi equivalenti '[Eb1, Eb2)' ottenuto da 'b.equal_range (Ea1)', tale che ' distance (Ea1, Ea2) == distance (Eb1, Eb2) 'e' is_permutation (Ea1, Ea2, Eb1) 'restituisce' true'. Per 'unordered_set' ... la complessità di' operator == '... è proporzionale a 'N' nel caso medio e a' N^2' nel caso peggiore, dove 'N' è' a.size() '." –