Hashtable in C ++?
https://stackoverflow.com/questions/133569
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Di solito utilizzo la mappa stdlib C ++ ogni volta che devo archiviare alcuni dati associati a un tipo specifico di valore (un valore chiave - ad esempio una stringa o un altro oggetto). L'implementazione della mappa stdlib si basa su alberi che forniscono prestazioni migliori (O (log n)) rispetto all'array standard o al vettore stdlib.
Le mie domande sono: conosci C ++ " standard " implementazione hashtable che offre prestazioni ancora migliori (O (1))? Qualcosa di simile a ciò che è disponibile nella classe Hashtable dall'API Java.
Soluzione
Se usi C ++ 11, hai accesso alle intestazioni <unordered_map> e <unordered_set>. Questi forniscono le classi std::unordered_map e std::unordered_set .
Se stai usando C ++ 03 con TR1, hai accesso alle classi std::tr1::unordered_map e std::tr1::unordered_set, usando le stesse intestazioni (a meno che tu non stia usando GCC, nel qual caso le intestazioni sono <tr1/unordered_map> e <tr1/unordered_set> invece).
In tutti i casi, ci sono anche unordered_multimap e unordered_multiset tipi corrispondenti.
Altri suggerimenti
Se non hai già unordered_map o unordered_set, fanno parte di boost .
Ecco la documentazione per entrambi .
Esiste un oggetto hash_map come molti qui hanno menzionato, ma è non fa parte dello stl. È un'estensione SGI, quindi se stavi cercando qualcosa nella STL, penso che tu sia sfortunato.
std :: tr1 :: unordered_map, in <unordered_map>
se non hai tr1, ottieni boost e usa
boost :: unordered_map in <boost/unordered_map.hpp>
Visual Studio ha la classe stdext::hash_map nell'intestazione <hash_map> e gcc ha la classe __gnu_cxx::hash_map nella stessa intestazione.
Vedi std :: hash_map da SGI.
Questo è incluso anche nella distribuzione STLPort .
hash_map è supportato anche in libstdc ++ .
Dinkumware anche supporta questo, che significa che molte implementazioni avranno una hash_map (penso che anche Visual C ++ offra Dinkumware).
Se hai le estensioni TR1 disponibili per il tuo compilatore, usa quelle. Altrimenti, boost.org ha una versione che è abbastanza simile ad eccezione dello spazio std :: namespace. In tal caso, inserisci una dichiarazione using in modo da poter passare a std :: later.
