I have uploaded my work on a hash table library to the Yahoo group files section: http://groups.yahoo.com/group/boost/files/hash_table.zip
It includes four containers that conform to Matthew Austern's proposal at http://std.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1399.html. In addition, it includes two other containers, boost::hash_table and boost::hash_multitable, which allow the user to specify a function/functor that extracts the key from the value. All of the containers, in addition to Matthew Austern's bucket interface of which I am not particularly fond, provide a container-view interface to the buckets, as suggested by a message forwared by someone on this list. The documentation is not yet perfect, and as I have yet to write a test suite, there may still be bugs. I have done some minimal testing with GCC 3.2.1. I would greatly appreciate any assistance with testing. There are a number of issues still remaining that should be discussed: 1. Exception safety Matthew Austern seems to forget about rehash in his discussion of exception safety. It is especially difficult to provide an exception guarantee for rehash because one of the user-specified functions could throw an exception in the middle of rehashing, in which case the element cannot be put into the new structure, and because the old structure is already partially disassembled, it cannot remain there either. The current solution, which does not seem particularly good, is to erase the element and continue. 2. Naming I am not sure what the best names are for the hash_table and hash_multitable class templates. 3. Bucket interface It is not clear to me that there should even be a bucket interface. A bucket interface excludes an open addressing implementation. In addition, it would be unusual for a standard library container, since for example, the existing associative containers, map, multimap, set, and multiset, do not provide a tree interface. Also, it is not clear to me that a bucket interface would be particularly useful. Going along with this, perhaps the rehash member function should not be public; the higher-level reserve and capacity member functions seem more useful. A preliminary informal review by various members would be quite helpful. - Jeremy Maitin-Shepard _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
