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

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.

Answer 2

Why can't you use Boost? The Unordered collections library is "Header only", meaning you don't have to pull in Boost's BJam build process and installer. You could just grab the .hpp files and add them to your project.

Answer 3

Default STL in the current standard does not have O(1) lookup containers.

Answer 4

As well as hash_map in some STLs, look for unordered_map (which is what it will be called and/or is called in the TR1 version of C++).

Answer 5

You can use the unordered_map container. Its in tr1 and will be in the next full standard. Visual Studio has an implementation of it in <unordered_map> the and documentation can be found here: http://msdn.microsoft.com/en-us/library/bb982522.aspx

Answer 6

hash_map is part of the SGI extension to the STL. In GCC, you can use it by doing the following; I don't know about other implementations:

#include <ext/hash_map>

using __gnu_cxx::hash_map;

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

unordered_map is part of the TR1. In GCC, you can use it by doing the following; I don't know about other implementations:

#include <tr1/unordered_map>

using std::tr1::unordered_map;

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

Answer 7

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;