[boost] Hash table library submission

From: Jeremy Maitin-Shepard (jbms_at_[hidden])
Date: 2002-12-26 00:21:15

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