Hashtable in C++?

solito uso C++ mappa stdlib ogniqualvolta ho bisogno di memorizzare alcuni dati associati a un particolare tipo di valore (un valore di chiave - ad esempio una stringa o un altro oggetto). L'implementazione stdlib mappa si basa su alberi che fornisce migliori prestazioni (O (log n)) che l'array o vettore stdlib standard.Hashtable in C++?

Le mie domande sono, sapete di qualsiasi implementazione di hash standard "C++" che fornisce prestazioni ancora migliori (O (1))? Qualcosa di simile a ciò che è disponibile nella classe Hashtable dall'API Java.

fonte

2008-09-25 Marcos Bento

Se si utilizza C++ 11, si ha accesso alle intestazioni <unordered_map> e <unordered_set>. Questi forniscono classi std::unordered_map e std::unordered_set.

Se stai usando C++ 03 con TR1, è possibile accedere alle classi std::tr1::unordered_map e std::tr1::unordered_set, utilizzando le stesse intestazioni (a meno che non si sta utilizzando GCC, nel qual caso le intestazioni sono <tr1/unordered_map> e <tr1/unordered_set> invece).

In tutti i casi, vi sono anche i tipi unordered_multimap e unordered_multiset corrispondenti.

fonte

2008-09-25 14:15:41

In GCC, devi usare i nomi di intestazione e . È una stranezza del GCC. :-) –

Il VS2008 Feature Pack è stato sostituito da SP1. – Ferruccio

IIRC le implementazioni di VC9 Feature Pack e SP1 tr1 :: unordered_ * sono state fornite con note di rilascio che avvisano di prestazioni non ottimali.Suppongo che questo sarà risolto alla fine. – jwfearn

-1

std::hash_map

fonte

2008-09-25 14:14:20 Dima

Vedi std::hash_map da SGI.

Questo è incluso anche nella distribuzione STLPort.

fonte

2008-09-25 14:14:29

Può essere incluso in STLPort, ma è ancora non "standard", come la domanda desiderata. Non esiste una classe _standard_ chiamata hash_map; è chiamato invece unordered_map, ed è in TR1. –

C'è un oggetto hash_map come molti hanno menzionato qui, ma non fa parte di stl. Si tratta di un'estensione SGI, quindi se state cercando qualcosa nel STL, penso che tu sei fuori di fortuna.

fonte

2008-09-25 14:15:52

Visual Studio ha la classe stdext::hash_map nell'intestazione <hash_map> e gcc ha la classe __gnu_cxx::hash_map nella stessa intestazione.

fonte

2008-09-25 14:17:51

Se hanno la stessa interfaccia, è abbastanza facile realizzare un'implementazione che supporti entrambi usando alias di namespace e alcuni lavori di pre-elaborazione. –

Lo so, lo so, questa è roba deprecata. Non tutti i colleghi possono essere convinti di passare a VS 2008 o installare Boost. Quindi, ecco un buon trucco su come ottenere questi insieme: 'namespace std { #ifdef __GNUC__ \t utilizzando namespace __gnu_cxx; #elif \t utilizzando lo spazio dei nomi stdext; #endif } ' – ypnos

hash_map è supportato anche in GNU libstdc++.

Dinkumware anche supports questo, il che significa che un sacco di implementazioni avranno un hash_map (credo che anche Visual C++ offre con Dinkumware).

fonte

2008-09-25 14:20:31

Potrebbe essere ampiamente supportato, ma non è" standard ", come richiesto dall'interrogante. Solo le strutture TR1 possono essere considerate standard. –

Il punto che stavo facendo è che se tutti i produttori di compilatori lo supportano (o i fornitori di stdlibC++, a seconda del caso), allora potrebbe essere un sostituto abbastanza buono per "standard". BTW, TR1 non è ancora "standard". È accettato per il prossimo standard, il che è sufficiente per convincere i produttori a implementarlo (il mio punto ...) –

Penso che sia solo per libstdC++ version> = 4.0? – rogerdpack

Se non si dispone di unordered_map o unordered_set, fanno parte di boost.
Here's the documentation for both.

fonte

2008-09-25 14:28:21

Yay per Boost che fornisce _maximal portability_ ancora una volta. :-) Vedi http://stackoverflow.com/questions/131445 per un'altra istanza di questo. –

Se disponi delle estensioni TR1 disponibili per il tuo compilatore, utilizza quelle. Altrimenti, boost.org ha una versione abbastanza simile ad eccezione di std :: namespace. In tal caso, inserisci una dichiarazione di utilizzo in modo da poter passare a std :: later.

fonte

2008-09-25 14:28:32 MSalters

std :: tr1 :: unordered_map, in <unordered_map>

se non si dispone di TR1, ottenere spinta, e utilizzare boost :: unordered_map in <boost/unordered_map.hpp>

fonte

2009-03-25 14:58:45 rlbond

Hashtable in C++?

risposta

Problemi correlati