C++ data structure with lookuptime O(1), like java's hashmap in stl?

Question

Is there such a structure in c++ standard library? I don't have access to anything else so unordered_map in tr1 cant be used (and boost etc).

What I have is a large number of custom class elements 100000+ which I need to store, and access them very fast O(1) on everage. I can't use arrays/vectors as the elements will be stored randomly and I don't know the position of the element.

Is my only alternative to implements an own hashmap implementation with only the c++ standard library available?

Answer 1

If you are really restricted to std:: and can't use anything else, std::map is your best bet. This only gives you logarithmic lookup time, not constant one, but compared with arrays/vectors it will be blazingly fast. Also I guess for just 100000 elements the logarithmic lookup will be by fast enough and you won't win much by using a hash table.

That being said, chances are that your implementation already includes some hash table implementation. So if std::map really isn't fast enough, try

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

or

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

or even

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

Answer 2

The problem is that the O(1) lookup is not standard. I am unsure about what boost has, but some STL implementations (like sgi) have hash_map. That's what you need.

Here is the documentation.

Just try out:

#include <hash_map>

Keep in mind if this works, it is not portable... but maybe for now that's ok, and later you can find workarounds.