Re: [boost] [unordered] request for ways to get more space efficient allocations

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2008-04-22 02:23:53

Daniel James skrev:
> On 21/04/2008, Thorsten Ottosen <thorsten.ottosen_at_[hidden]> wrote:
>> Daniel James skrev:
>>  > An alternative that has some appeal is letting the user specify a
>>  > policy class to control the bucket count. Although I'm not sure how
>>  > that would play with the standard.
>>
>> Poor, probably.
>>
>>  I guess for cases where I know the intergers fall in the range, say,
>>  [0,64], I can just use vector<optional<unsigned>>.
> 
> Thinking about it some more, I could create a trait class for the hash function.
> 
> template <class T> struct is_good_hash : public boost::mpl::false_ {};
> template <> struct is_good_hash<groovy_hash> : public boost::mpl::true_ {};
> 
> And use power of 2 tables when the trait is true.

As for the integers case, I think the vector approach is actually more 
appropriate. It's harder to use with pointers though. I'd rather just 
see a way to tell the container "have this initial bucket capacity no 
matter what", then I can find a good size that avoids rehashing and 
comes close to the number of needed buckets (for some application 
specific definition of "close" ).

For example, having a max of 24 pointers, it is probably not necessary 
to go for 53 buckets. This can matter some if the number of hashmaps are 
thousands or millions (as they often are in my case).

-Thorsten