CODEWITHSUNDEEP
c++performancedata-structures
Milan
Milan

Reputation: 15849

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

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?

Upvotes: 8

Views: 3101

Answers (7)

sth
sth

Reputation: 229613

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;

Upvotes: 6

newacct
newacct

Reputation: 122449

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

Upvotes: 2

Fire Lancer
Fire Lancer

Reputation: 30145

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

Upvotes: 0

ChrisW
ChrisW

Reputation: 56113

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++).

Upvotes: 0

Antti Huima
Antti Huima

Reputation: 25522

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

Upvotes: 1

John Kugelman
John Kugelman

Reputation: 361635

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.

Upvotes: 3

Tom
Tom

Reputation: 21902

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.

Upvotes: 5

Related Questions