CODEWITHSUNDEEP
c++hashmap
PrettyPrincessKitty FS
PrettyPrincessKitty FS

Reputation: 6400

Hash map, string compares, and std::map?

First off, I would like to make a few points I believe to be true. Please can these be verified?

If std::map is not a hash map and I should not be relying on string compares (basically, I have a map with strings as keys...I was told to look up using hash maps instead?), is there a hash map in the C++ STL? If not, how about Boost?

Secondly, Is a hash map worth it for [originally] an std::map< std::string, non-POD GameState >?

I think my point is getting across...I plan to have a store of different game states I can look up and register into a factory. If any more info is needed, please ask.

Thanks for your time.

Upvotes: 1

Views: 11026

Answers (3)

anon
anon

Reputation:

I don't believe most of your points are correct.

  • there is no hash map in the current standard. C++0x introduces unordered_map, who's implementation will be a hash table and your compiler probably already supports it.

  • std::map is implemented as a balanced tree, not a hash table. There are no "memory issues" when using either map type with strings, either as keys or data.

  • strings are not stored as numbers in either case - an unordered_map will use a hashing function to derive a numeric key from the string, but this is not stored.

  • my experience is that unordered_map is about twice the speed of map - they have basically the same interface, so you can try both with your own data - whenever you are interested in performance you should always perform tests your self with your own real data, rather than depending on the experience of others. Both map types will be somewhat sensitive to the length of the string key.

Assuming you have some class A, that you want to access via a string key, the maps would be declared as:

map <string, A> amap;
unordered_map <string, A> umap;

Upvotes: 10

doep
doep

Reputation: 113

I made a benchmark that compares std::map with boost::unordered_map. My conclusion was basically this: If you do not need map-specific things like equal_range, then always use boost::unordered_map. The full benchmark can be found here

Upvotes: 8

Kylotan
Kylotan

Reputation: 18449

A hash map will typically have some integral representation of a string, yes.

std::map has a requirement to be sorted, so implementing it as a hash table is unlikely, and I've never seen it in practice.

Whether string comparisons are good or bad depends entirely on what you're doing, what data you're comparing, and how often. If the first letter differs then that's barely any different from an integer comparison, for example.

You want unordered_map (that's the Boost version - there is also a version in the TR1 standard library if your compiler has that).

Is it worth it for game states? Yes, but only because using an unordered_map is simple. You're prematurely worrying about optimisations at this stage. Save the worries over access patterns for things you're going to look up thousands of times a second (ie. when your profiler tells you that it's a problem).

Upvotes: 1

Related Questions