Deprecated HP/SGI

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 the upcoming C++0x, and may be removed in future releases.

The SGI headers

     <hash_map>
     <hash_set>
     <rope>
     <slist>
     <rb_tree>
   

are all here; <hash_map> and <hash_set> are deprecated but available as backwards-compatible extensions, as discussed further below. <rope> is the SGI specialization for large strings ("rope," "large strings," get it? Love that geeky humor.) <slist> is a singly-linked list, for when the doubly-linked list<> is too much space overhead, and <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.