Re: [boost] hash table library proposal (was Extensions in Boost.Compatibility)

From: John Maddock (jm_at_[hidden])
Date: 2002-12-14 06:45:01

> Yes, but I think we should try to stick closely to the LWG proposal. In
> fact, it might be an advantage for standardization to have an exact
> implementation. (It might be worth asking Matt Austern how he proposes to
> change the interface to deal with the issues still on the table.)

Absolutely, however you may want to look at the suggestions below as well,
perhaps as an extension/alternative to Matts bucket interface.  I also
understand from Howard that he's planning to at least experiment with this
with the Metrowerks implementation.  Testing this out in a boost
implementation would be a good proof of concept IMO, and BTW if you can
implement Matt's bucket interface, then you can also implement this one as a
rather neater wrapper around it (let me know if you need any help).

Forwarded from:

To: C++ libraries mailing list
Message c++std-lib-10535

First off let me thank Mat Austern for putting together the has table
proposal, I like it a lot, but have a few questions about the bucket
interface:

Specifically: although the interface allows one to iterate through a bucket,
it does not allow you to iterate through a sequence of buckets (well
actually it does, it's just that you can't use iterators for it).  I'll come
on to the reasons for wanting this later, but I wonder if you have
considered a simpler interface based upon a true "container of containers"
concept.  In place of the existing bucket interface the following would be
provided:

   typedef implementation_defined bucket_type;

A container type such that bucket_type::value_type and value_type are the
same type.

   typedef implementation_defined bucket_collection;

A container type whose value type is the same type as bucket_type.

   const bucket_type& bucket(const key_type& v)const;

returns the bucket into which v would be inserted.

   const bucket_collection& buckets()const;

returns a the collection of buckets contained in *this.

~~~~~~~~~~

And that's it, this deceptively simple interface allows for all the use
cases that Mat's does, but also some that are rather tricky otherwise, for
example one could print a histogram of bucket usage like this:

template <class T>
void print_bar(const T& bucket)
{
    std::cout << std::string(bucket.size(), '*') << std::endl;
}

template <class HT>
void print_histogram(const HT& table)
{
   std::for_each(table.buckets().begin(), table.buckets().end(),
&print_bar<typename HT::bucket_type>);
}

And that's really the crux of the argument: by using a container based
interface we gain the leverage provided by the standard lib algorithms, and
the familiarity that these interfaces provide (and hence ease of learning).

Now for the tricky bit: in some implementations there might not really be
any real buckets at all (we may have one big linked list), in this case
buckets would have to be pseudo-containers that don't really exist at all,
but are created on the fly when required as a view of an iterator range.

Likewise the types bucket_type and bucket_collection don't need to provide
any mutating operations since only const-access to these types are provided.

One consequence of this is that it may be difficult to implement
bucket_collection in such a way such that bucket_collection::const_iterator
is a real iterator type - it may be more like a proxy-iterator (as in
vector<bool>::iterator).  If true iterators are required, then the temporary
bucket_type object could be a data member of the iterator so that it can be
returned by const-reference rather than value upon iterator dereference, in
this case the lifetime of the returned object would be constrained by the
lifetime of the iterator through which it is accessed, frankly this may be
worse than providing proxy-iterators.  Either which way it should be
specified that bucket_types are views of existing data, and are therefore
cheep to copy, and indeed *should* be copied when stored.

Anyway, I hope this provides some food for thought,

regards,

John Maddock
http://ourworld.compuserve.com/homepages/john_maddock/index.htm