At various places, I've read that STL does not provide hashtable and union data structures. How could these be implemented using other existing STL data structures?
`std::map` is actually a binary tree, not a hashtable. As SB says, `unordered_map` is a hashtable. (Technically, the standard doesn't specify how the map is to be implemented, but the constraints specified by the standard imply a binary tree - and that's certainly the most common implementation)
Dean Harding
2010-06-23 11:42:53
That's tree-based and has different performance characteristics to a hash table (lookup is logarithmic time for a tree, versus constant time for a hash table). C++0x introduces `unordered_map` based on hash tables. Some implementations may provide `hash_map`, which was part of the original STL but wasn't included in the Standard Library.
Mike Seymour
2010-06-23 11:44:16
good to know, thanks :-)
Protostome
2010-06-23 11:46:51
Actually, `std::map` requirements does not imply a binary tree (and certainly not a red-black tree or an AVL tree even though those are the most common implementations). A Skip List would work.
Matthieu M.
2010-06-23 16:39:21
+7
A:
Try the std::tr1::unordered_map for your hash map. std::map is ordered, so it's not really as efficient as hash. Not sure what you mean by a union data structure, but you can have unioned structs in C++
EDIT: Additionally there are many other implementations of hash maps that some have done. Boost has an unordered map, Prasoon mentioned one in the question comments, and Google has sparsehash.
SB
2010-06-23 11:39:36