Come scegliere tra la mappa e unordered_map?

Supponiamo di voler mappare i dati con una stringa come chiave. Quale contenitore dovrei scegliere, map o unordered_map ? unordered_map occupa più memoria quindi supponiamo che la memoria non sia un problema e che la preoccupazione sia la velocità.

unordered_map dovrebbe generalmente dare una complessità media di O (1) con il caso peggiore di O (n). In quali casi otterrebbe O (n)? Quando una map un tempo più efficiente di unordered_map ? Succede quando n è piccolo?

Supponendo che userò STL unordered_map con l’hash predefinito Vs. carta geografica. la stringa è la chiave.

Se ho intenzione di scorrere gli elementi piuttosto che accedere ad ogni singolo elemento ogni volta, dovrei preferire la map ?

In pratica, se la memoria non è un problema, unordered_map è sempre più veloce se si desidera l’accesso a un singolo elemento.

Il caso peggiore è teorico e legato a un singolo hash che tiene conto di tutti gli elementi. Questo non ha rilevanza pratica. unordered_map rallenta non appena si ha almeno il log N elementi appartenenti allo stesso hash. Anche questo non è di rilevanza pratica. In alcuni scenari speciali è ansible utilizzare uno specifico algoritmo di hash che garantisce una distribuzione più uniforms. Per le stringhe ordinarie che non condividono un modello specifico, le funzioni di hash generiche che arrivano con unordered_map sono altrettanto buone.

Se si desidera attraversare la mappa (utilizzando gli iteratori) in modo ordinato, non è ansible utilizzare unordered_map . Al contrario, map non solo lo consente, ma può anche fornire l’elemento successivo in una mappa in base all’approssimazione della chiave (vedi metodi lower_bound e upper_bound ).

  | map | unordered_map --------------------------------------------------------- element ordering | strict weak | n/a | | common implementation | balanced tree | hash table | or red-black tree| | | search time | log(n) | O(1) if there are no hash collisions | | Up to O(n) if there are hash collisions | | O(n) when hash is the same for any key | | Insertion time | log(n)+rebalance | Same as search | | Deletion time | log(n)+rebalance | Same as search | | needs comparators | only operator < | only operator == | | needs hash function | no | yes | | common use case | when good hash is| In most other cases. | not possible or | | too slow. Or when| | order is required| 

Quale contenitore dovrei scegliere, mappare o unordered_map? unordered_map occupa più memoria quindi supponiamo che la memoria non sia un problema e che la preoccupazione sia la velocità.

Profilo e poi decidere. unordered_map è generalmente più veloce, ma varia a caso.

In quali casi otterrebbe O (n)?

Quando l’hashing non è buono e un gruppo di elementi viene assegnato agli stessi bidoni.

Quando una mappa ha un tempo più efficiente di unordered_map? Accade quando n è piccolo?

Probabilmente no, ma profilalo se ti interessa davvero. Avere un contenitore di piccole dimensioni è il collo di bottiglia del tuo programma sembra estremamente improbabile. Ad ogni modo, un semplice vector con ricerca lineare potrebbe essere più veloce in questi casi.


La cosa più importante quando si decide sono i requisiti di ordine e la mancanza di invalidazione iteratore. Se è necessario, è necessario utilizzare la map . Altrimenti, unordered_map .

In quali casi otterrebbe O (n)?

se si dispone di una funzione hash così ctriggers che produce lo stesso valore di hash per tutti gli stirng di input (cioè producono collisioni) …

Quale contenitore dovrei scegliere, mappare o unordered_map?

Sono sempre le domande dei requisiti e il tipo / quantità di dati che hai.

Quando una mappa ha un tempo più efficiente di unordered_map?

Sono solo diverse strutture. Faresti meglio a fare un chiose per usarne uno a seconda dei tuoi tipici casi d’uso (prendendo in considerazione che tipo di dati hai e il loro ammontare)

Ti hppaen quando n è piccolo?

Nel caso di una piccola quantità di dati, tutto dipende da una particolare implementazione STL … Quindi a volte persino un semplice vettore / array potrebbe essere più veloce dei contenitori associativi …