La carta non ordinata è davvero non ordinata?

Question

Sono molto confuso dal nome "unordered_map". Il nome suggerisce che le chiavi non sono affatto ordinate. Ma ho sempre pensato che fossero ordinati per il loro valore hash. O è sbagliato (perché il nome implica che non sono ordinati)?

O per dirla diverso: È questo

typedef map<K, V, HashComp<K> > HashMap; 

con

template<typename T> 
struct HashComp { 
    bool operator<(const T& v1, const T& v2) const { 
     return hash<T>()(v1) < hash<T>()(v2); 
    } 
}; 

lo stesso

typedef unordered_map<K, V> HashMap; 

? (OK, non esattamente, STL si lamenterà qui perché ci possono essere le chiavi k1, k2 e né k1 < k2 né k2 < k1 Lei avrebbe bisogno di utilizzare multimap e sovrascrivere il pari-check..)

O ancora in modo diverso: Quando li elabora, posso supporre che la key-list sia ordinata dal loro valore hash?

Answer 1

In risposta alla domanda modificata, questi due frammenti non sono affatto equivalenti. std::map memorizza i nodi in una struttura ad albero, unordered_map li memorizza in una tabella hash *.

Le chiavi non vengono memorizzate in base al loro "valore hash" perché non vengono memorizzate in in qualsiasi ordine. Sono invece memorizzati in "bucket" in cui ciascun bucket corrisponde a un intervallo di valori hash. In sostanza, l'applicazione è questa:

function add_value(object key, object value) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     buckets[bucket_index] = new linked_list(); 
    } 
    buckets[bucket_index].add(new key_value(key, value)); 
} 

function get_value(object key) { 
    int hash = key.getHash(); 

    int bucket_index = hash % NUM_BUCKETS; 
    if (buckets[bucket_index] == null) { 
     return null; 
    } 

    foreach(key_value kv in buckets[bucket_index]) { 
     if (kv.key == key) { 
      return kv.value; 
     } 
    } 
} 

Ovviamente questa è una grave semplificazione e reale attuazione sarebbe molto più avanzato (ad esempio, sostenendo ridimensionamento della matrice buckets, magari usando una struttura ad albero anziché lista collegata per le benne , e così via), ma ciò dovrebbe dare un'idea di come non è possibile recuperare i valori in un ordine particolare. Vedere wikipedia per ulteriori informazioni.

* Tecnicamente, l'implementazione interna di std::map e unordered_map sono definiti dall'implementazione, ma lo standard richiede certa complessità O-grande per le operazioni che implica quelle implementazioni interne

Answer 2

Se si desidera un'analogia, controllare l'RDBMS desiderato.

Se non si specifica una clausola ORDER BY quando si esegue una query, i risultati vengono restituiti "non ordinati", ovvero in qualsiasi ordine si desideri il database. L'ordine non è specificato e il sistema è libero di "ordinarli", ma a suo piacimento per ottenere le migliori prestazioni.

Answer 3

Avete ragione, unordered_map è in realtà hash ordinato. Nota che la maggior parte delle implementazioni attuali (pre TR1) lo chiamano hash_map.

IBM C/C++ compilatore documentation osservazioni che se si dispone di una funzione ottimale hash, il numero di operazioni eseguite durante la ricerca, l'inserimento e la rimozione di un elemento arbitrario non dipende dal numero di elementi nella sequenza , quindi questo significa che l'ordine non è così non ordinato ...

Ora, che cosa significa che è hash ordinato? Poiché un hash dovrebbe essere imprevedibile, per definizione non puoi assumere alcuna ipotesi sull'ordine degli elementi nella mappa. Questo è il motivo per cui è stato rinominato in TR1: il vecchio nome suggeriva un ordine. Ora sappiamo che un ordine è effettivamente utilizzato, ma puoi ignorarlo perché è imprevedibile.

Answer 4

"Non ordinato" non significa che non ci sia una sequenza lineare da qualche parte nell'implementazione. Significa "non puoi assumere nulla sull'ordine di questi elementi".

Ad esempio, le persone spesso presumono che le voci escano da una mappa hash nello stesso ordine in cui sono state inserite. Ma non lo fanno, perché le voci non sono ordinate.

Come per "ordinato dal loro valore di hash": i valori di hash sono generalmente presi dall'intero intervallo di interi, ma le mappe di hash non hanno 2 ** 32 slot in essi. L'intervallo del valore hash verrà ridotto al numero di slot assumendolo modulo il numero di slot. Inoltre, man mano che aggiungi voci a una mappa hash, è possibile che le dimensioni cambino per adattarsi ai nuovi valori. Ciò può causare la reinserzione di tutte le voci precedenti, modificandone l'ordine.

In una struttura di dati non ordinata, non è possibile assumere nulla sull'ordine delle voci.

Answer 5

Come suggerisce il nome unordered_map, nessun ordinamento è specificato dallo standard C++ 0x. L'apparente ordinamento di unordered_map dipenderà da ciò che è conveniente per l'implementazione effettiva.