I'm looking for a HashTable or Dictionary implementation in C++ that has similar functionality to the one in C#? Does the STL contain an object like this and how would I use it?
map is a balanced tree, not a hash container.
Joe
2010-04-27 13:28:23
@joe - question was for a hashmap *or* dictionary class in c++ STL, so `std::map` fits the bill.
gnud
2010-04-27 21:51:09
@gnud: OP also said "that has similar functionality to the one in C#", which only unordered_map fits, if you're talking about performance characteristics.
Joe
2010-04-28 00:01:28
+5
A:
Actually, to be exactly the same as .NET's Dictionary/Hashtable, what you want is hash_map or unordered_map (std::map is implemented as a binary tree), hash_map is an extension to the SC++L. I believe C++0x is going to include unordered_map. Most compilers that I know of come with hash_map, though, and boost obviously has unordered_map until C++0x is available in all compilers, so you should just be able to use it without trouble.
Dean Harding
2010-04-27 13:01:54
C++ has no such container as hash_map,, and won't in C++0x. The name of the name of the hash table in C++ is unordered_map - se http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/topic/com.ibm.xlcpp9.aix.doc/standlib/stl_unordered_map.htm
anon
2010-04-27 13:03:48
Ahh, the C++ standards process. Bickering about the name of a hashtable class while Rome burns.
stusmith
2010-04-27 13:08:22
+2
A:
The STL std::map can be used to build a dictionary. std::map is usually implemented as a search tree, not a hash table. That means both lookup and insertion has different perfomance characteristics than C#'s HashMap - for very large maps, average lookup will be slower, especially if the objects in the map are fragmented in memory.
In the TR1 of the new c++ standard, you have std::tr1::unordered_map and std::tr1::unordered_multimap, which will usually be implemented using a hash table. If your compiler does not provide those libraries, you can use the implementation from http://www.boost.org/.
Yet another alternative is Google's sparse_hash.
gnud
2010-04-27 13:05:49
A lookup in an std::map is **not** per se slower than in a hash_map. Only the asymptotical performance of a hash_map is O(1) vs. O(log n), but for big enough values of 1, log n may be faster. Even practically this is often enough the case, _and_ finding a good hash-function is much more difficult than implementing a correct operator<.
gimpf
2010-04-27 13:08:47
Just re-read, you said _often_, not always, my fault. However, _often_ implies that most often people use dictionaries with, well, more than about 1000 entries, using correct hash-functions. Depending on area of work and the skill level within a company this may indeed be unlikely.
gimpf
2010-04-27 13:10:24
Maybe 'will often be slower' isa bit harsh. My point is mainly that they have different performance characteristics.
gnud
2010-04-27 13:11:19
There is also [MCT's closed_hash_map](https://launchpad.net/libmct) similar to Google's `dense_hash_map` but without the restriction on keys.
doublep
2010-04-27 17:13:50