Re: [boost] portable hash_map

From: Matt Austern (austern_at_[hidden])
Date: 2001-03-05 14:27:51

Neal Fachan wrote:
> 
> Hello.
> 
> We noticed you don't include a hash_map template in the
> Boost libraries. We assume this is because every STL
> implementation we can find includes their own hash_map.
> 
> Unfortunately, none of these hash_map implementations are
> compatible.
> 
> We have portable software which uses the native vendor STL
> on all platforms, so this makes using vendors' hash_maps
> troublesome.
> 
> What would you advise us to do? We are leaning towards
> taking SGI STL (STLPort)'s hash_map, but putting it into
> it's own quarantined namespace.

I'm working on a new version of hash tables, very loosely
based on the SGI version.  One problem with the SGI version
is that it's too tightly coupled to the rest of the SGI
library.  Decoupling it would be possible, but, in my opinion,
not worth the trouble.

I thought that my new version was closer to being finished
than I now do.  Two things I need to change:
 - I was using an slist for each bucket.  Howard convinced
   me that this was a bad idea: if a user specified an
   allocator with per-object state, then this would be
   grossly wasteful.
 - I might have an new idea that will permit fast iteration 
   without giving up any of the other desirable properties:
   have a single slist for all the elements, and then have
   a separate vector of slist iterator pairs for the buckets.
   My new insight is that elements in that single slist do 
   not have to appear in bucket order.  I don't know why that
   didn't occur to me before today.

The bad news is that this requires an almost complete rewrite.
Oh well.  The more I stare at the code, the more bugs I'll
find.

                        --Matt