+ 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. + +