The SGI hashing classes hash_set and
hash_set have been deprecated by the
unordered_set, unordered_multiset, unordered_map,
unordered_multimap containers in TR1 and C++11, and
may be removed in future releases.
The SGI headers
<hash_map>
<hash_set>
<rope>
<slist>
<rb_tree>
are all here;
<backwards/hash_map> and
<backwards/hash_set>
are deprecated but available as backwards-compatible extensions,
as discussed further below.
<ext/rope> is the SGI
specialization for large strings ("rope," "large strings," get it? Love
that geeky humor.)
<ext/slist> (superseded in
C++11 by <forward_list>)
is a singly-linked list, for when the doubly-linked list<>
is too much space overhead, and
<ext/rb_tree> exposes the
red-black tree classes used in the implementation of the standard maps
and sets.
Each of the associative containers map, multimap, set, and multiset have a counterpart which uses a hashing function to do the arranging, instead of a strict weak ordering function. The classes take as one of their template parameters a function object that will return the hash value; by default, an instantiation of hash. You should specialize this functor for your class, or define your own, before trying to use one of the hashing classes.
The hashing classes support all the usual associative container functions, as well as some extra constructors specifying the number of buckets, etc.
Why would you want to use a hashing class instead of the “normal”implementations? Matt Austern writes:
[W]ith a well chosen hash function, hash tables generally provide much better average-case performance than binary search trees, and much worse worst-case performance. So if your implementation has hash_map, if you don't mind using nonstandard components, and if you aren't scared about the possibility of pathological cases, you'll probably get better performance from hash_map.
The deprecated hash tables are superseded by the standard unordered
associative containers defined in the ISO C++ 2011 standard in the
headers <unordered_map>
and <unordered_set>.