Struttura dati C++ con lookuptime O (1), come l'hashmap di java in stl?

Question

Esiste una tale struttura nella libreria standard C++? Non ho accesso a nient'altro che non sia possibile usare unordered_map in tr1 (e boost ecc.).

Quello che ho è un gran numero di elementi di classe personalizzati 100000+ che ho bisogno di memorizzare, e accedervi O (1) molto veloce su Everage. Non posso usare matrici/vettori poiché gli elementi verranno memorizzati casualmente e non conosco la posizione dell'elemento.

È la mia unica alternativa all'implementazione di una propria implementazione di hashmap con la sola libreria standard C++ disponibile?

Answer 1

Il problema è che la ricerca O (1) non è standard. Non sono sicuro di quale boost abbia, ma alcune implementazioni STL (come sgi) hanno hash_map. Questo è quello che ti serve.

Questo è il documentation.

Basta provare:

#include <hash_map> 

tenere a mente se questo funziona, non è portatile ... ma forse per ora va bene così, e più tardi si possono trovare soluzioni alternative.

Answer 2

Perché non è possibile utilizzare Boost? La libreria di raccolte Unordered è "Solo intestazione", il che significa che non è necessario eseguire il processo di compilazione e l'installazione di BJam di Boost. Potresti semplicemente prendere i file .hpp e aggiungerli al tuo progetto.

Answer 3

L'STL predefinito nello standard corrente non dispone di contenitori di ricerca O (1).

Answer 4

Così come hash_map in alcuni STL, cercare unordered_map (che è ciò che verrà chiamato e/o viene chiamato nella versione TR1 di C++).

Answer 5

È possibile utilizzare il contenitore unordered_map. È in tr1 e sarà nel prossimo standard completo. Visual Studio ha un'implementazione di esso in <unordered_map> il e la documentazione può essere trovato qui: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 6

hash_map fa parte dell'estensione SGI al STL. In GCC, puoi usarlo facendo quanto segue; Non so su altre implementazioni:

#include <ext/hash_map> 

using __gnu_cxx::hash_map; 

hash_map<int,string> foo; // or whatever 

unordered_map fa parte della TR1. In GCC, puoi usarlo facendo quanto segue; Non so su altre implementazioni:

#include <tr1/unordered_map> 

using std::tr1::unordered_map; 

unordered_map<int,string> foo; // or whatever 

Answer 7

Se siete veramente limitati a std:: e non è possibile utilizzare qualsiasi altra cosa, std::map è la soluzione migliore. Questo ti dà solo il tempo di ricerca logaritmico, non costante, ma rispetto agli array/vettori sarà incredibilmente veloce. Inoltre suppongo che per soli 100.000 elementi la ricerca logaritmica sia abbastanza veloce e non vincerai molto usando una tabella hash.

Ciò detto, è probabile che l'implementazione includa già un'implementazione della tabella hash.Quindi, se std::map in realtà non è abbastanza veloce, prova a

#include <tr1/unordered_map> 
std::tr1::unordered_map<int,int> test; 

o

#include <hash_map> 
stdext::hash_map<int,int> test; 

o anche

#include <boost/tr1/unordered_map.hpp> 
std::tr1::unordered_map<int,int> test;