Guardando le due strutture dati e gli algoritmi per gestirli, una hashmap non è in realtà più complicata di un albero di ricerca binario e probabilmente meno complicata. E l'hashmap ha il vantaggio dell'accesso costante al tempo di una chiave. Quindi, perché abbiamo ottenuto una std :: map molto presto nella cronologia della libreria standard ma per std :: unordered_map che è una hashmap dovevamo aspettare per C ++ 11?
L'implementazione di una hashmap è molto più complicata, non nell'implementazione reale ma nelle possibili varianti da cui scegliere:
Tutti questi fattori influenzano le prestazioni in un modo in cui non è facile dire quale sia in generale migliore.
In confronto a questo, l'albero rosso-nero è molto più semplice per creare un prototipo per cui la gente non andrà in bici all'infinito.
Da link ,
It’s a little bit of an embarrassment to the C++ community that it didn’t have a hash table in the standard library until TR1 was published in 2005. In a perfect world the original standard should have contained hash map and hash set containers. But Alexander Stepanov didn’t include these containers in the original Standard Template Library, and the standardization committee was reluctant to bless containers that didn’t have a decent amount of mileage in the real world.
I comitati degli standard sono generalmente reattivi piuttosto che proattivi. C fu creato nel 1969 ma non fu standardizzato fino al 1989, e il C ++ fu creato nel 1979 ma non fu standardizzato fino al 1998. Il comitato C ++ intraprese alcune azioni proattive nella versione originale dello standard C ++, alcune delle quali risultarono essere errori. (Non c'erano essenzialmente compilatori completamente conformi per la versione originale dello standard.) L'aggiornamento del 2003 era principalmente una correzione di bug. Il comitato non avrebbe intrapreso azioni proattive nel 2003 per funzionalità che non erano state testate sul campo da più produttori di compilatori.
Detto questo, se tu fossi disposto a lavorare con funzionalità che ufficialmente non facevano parte dello standard, ma che furono benedette diventando parte dello standard in futuro, avevi accesso a una mappa non ordinata molto prima del 2011.
Dal punto di vista delle specifiche e della standardizzazione, una tabella hash è un po 'più complessa di un albero.
Per i contenitori basati su albero (ordinati), lo standard deve solo specificare che per memorizzare un oggetto, devi essere in grado di assegnarlo, copiarlo e confrontarlo 1 . Tutti questi sono già concetti ben definiti, e molti tipi integrati li soddisfano (l'unica ovvia eccezione sono i NaN a virgola mobile, che non soddisfano un severo ordinamento debole).
Per l'hashing, è necessario specificare (almeno) un certo tipo di hashing. Questo, a sua volta, richiedeva più infrastrutture, come std::hash , con specializzazioni per tutti i tipi built-in. Nel caso di std::unordered_* , significa anche un po 'di specifiche extra intorno agli iteratori, aggiungendo gli iteratori locali a un bucket ai normali iteratori usati per tutto il resto.
1. sì, entra in un piccolo più dettaglio, come richiedere che il confronto soddisfi un severo ordinamento debole, ma anche questo è abbastanza semplice.
Leggi altre domande sui tag c++ data-structures algorithms