C++ std :: complessità unordered_map

Question

Ho letto molto su unordered_map(C++ 11)tempo la complessità qui a StackOverflow, ma non ho trovato la risposta per la mia domanda.

Supponiamo indicizzazione per intero (solo per esempio):

Inserire/a funzioni lavorano costantemente (in tempo medio), quindi questo esempio potrebbe prendere O (1)

std::unordered_map<int, int> mymap = { 
      { 1, 1}, 
      { 100, 2}, 
      { 100000, 3 } 
}; 

Quello che ho Sono curioso di sapere quanto tempo ci vuole per scorrere tutti i valori (non ordinati) memorizzati nella mappa - ad es

for (auto it = mymap.begin(); it != mymap.end(); ++it) { ... } 

Posso supporre che ogni valore memorizzato si accede solo una volta (o due o costante volte)? Ciò implicherebbe che iterare attraverso tutti i valori sia nella mappa O a valore N (N). L'altra possibilità è che il mio esempio con le chiavi {1,10,1000000} potrebbe richiedere fino a 1000000 iterazione (se rappresentato dall'array)

C'è un altro contenitore, che può essere iterato linearmente e il valore accessibile costantemente da una determinata chiave ?

Quello che mi ha realmente bisogno è (pseudocodice)

myStructure.add(key, value) // O(1) 
value = myStructure.at(key) // O(1) 
for (auto key : mySructure) {...} // O(1) for each key/value pair = O(N) for N values 

È std :: unordered_map la struttura ho bisogno?

L'indicizzazione di numeri interi è sufficiente, anche la complessità media.

Answer 1

Indipendentemente da come vengono implementati, i contenitori standard forniscono iteratori che soddisfano i requisiti dell'iteratore. L'incremento di un iteratore deve essere costante, quindi iterando su tutti gli elementi di qualsiasi contenitore standard è O (N).

Answer 2

Esistono diversi modi in cui è possibile implementare una tabella hash e suggerisco di leggerne di più se sei interessato, ma i due principali sono la concatenazione e l'indirizzamento aperto.

Nel primo caso si dispone di una serie di elenchi collegati. Ogni voce dell'array potrebbe essere vuota, ogni elemento nella tabella hash sarà in qualche secchio. Quindi l'iterazione sta scendendo lungo l'array e sta scorrendo verso il basso in ciascuna lista non vuota. Chiaramente O (N), ma potrebbe potenzialmente essere molto inefficiente in memoria a seconda di come sono allocati gli elenchi collegati.

Nel secondo caso, si dispone solo di un array molto grande con un sacco di slot vuoti. Qui, l'iterazione è di nuovo chiaramente lineare, ma potrebbe essere inefficiente se la tabella è per lo più vuota (che dovrebbe essere a scopo di ricerca) perché gli elementi effettivamente presenti si troveranno in diverse linee della cache.

In entrambi i casi, avrai un'iterazione lineare e toccherai ogni elemento esattamente una volta. Nota che questo è vero per std::map, anche l'iterazione sarà lineare anche lì. Ma nel caso delle mappe, l'iterazione sarà sicuramente molto meno efficiente che iterando un vettore, quindi tienilo a mente. Se il tuo caso d'uso implica richiedere SIA ricerca rapida e iterazione rapida, se inserisci tutti gli elementi in primo piano e non li cancelli mai, potrebbe essere molto meglio avere effettivamente sia la mappa che il vettore. Prendi lo spazio extra per le prestazioni aggiuntive.

Answer 3

Le garanzie di complessità di tutti i contenitori standard sono specificate nello C++ Standard.

std::unordered_map l'accesso agli elementi e l'inserimento degli elementi devono essere di complessità O(1) in media e O(N) nel caso peggiore (cfr.Sezioni 23.5.4.3 e 23.5.4.4; pagine 797-798).

Un'implementazione specifica (ovvero l'implementazione di un fornitore specifico della Libreria standard) può scegliere qualsiasi struttura di dati che desiderano. Tuttavia, per essere conformi allo standard, la loro complessità deve essere almeno come specificato.