CODEWITHSUNDEEP
c++
Rishibha sharma
Rishibha sharma

Reputation: 33

Data container for fast lookup and retrieval

Actually I need a data structure that helps me in reducing time for look-ups and retrieval of values of the respective keys.

Right now I am using a map container with key as structure and want to retrieve its values as fast as possible.

I am using gcc on fedora 12. I tried unordered map also, but it is not working with my compiler.

Also, Hash map is not available in namespace std.

Upvotes: 1

Views: 465

Answers (2)

Mike Seymour
Mike Seymour

Reputation: 254771

If you're using C++11, use std::unordered_map, defined in <unordered_map>.

Otherwise, use std::tr1::unordered_map, defined in <tr1/unordered_map>, or boost::unordered_map, defined in <boost/unordered_map.hpp>.

If your key is a user-defined type, then you'll need to either define hash and operator== for the type, or provide suitable function types as template arguments to unordered_map.

Of course, you should also measure the performance compared to std::map; that may be faster in some circumstances.

Upvotes: 3

CashCow
CashCow

Reputation: 31455

hash map is called unordered_map. You can get it from boost and that will probably work even if you can't get a std/tr1 one to work. In general the lookup time is "constant" which means it does not increase with the complexity of the nubmer of elements. However you have to look at this in more detail:

  • "constant" assumes you never have more than a fixed number of "collisions". It's unlikely you won't have any, and then you have to measure the fact that there will be some collisions.

  • "constant" includes the time taken to hash the key. This is a constant time as it makes no difference how many other elements there are in the collection, however it is still a task that needs to be done, by which time your std::map may already have found your element.

If the keys are extremely fast to hash and well distributed so very few collisions occur, then hashing will indeed be faster.

One thing I always found when working with hash maps was that for the optimal performance you almost always won by writing your own implementation rather than using a standard one. That is because you could custom-tune your own for the data you knew you were going to handle. Perhaps this is why they didn't put hash maps into the original standard.

One thing I did when writing my own was store the actual hash value (the originally generated one) with the key. This was the first comparison point (usually faster than comparing the key as it's just an int) and also meant it didn't need to be regenerated if you resized your hash-table.

Note that hash-tables are easier to implement if you never delete anything from them, i.e. it is load and read only.

Upvotes: 0

Related Questions