Re: [Boost-users] Using unordered_set or unordered_map to hold small array(s) of ints

Subject: Re: [Boost-users] Using unordered_set or unordered_map to hold small array(s) of ints
From: Nathan Crookston (nathan.crookston_at_[hidden])
Date: 2010-08-21 03:41:30

FYI, the implementation of ar_hash doesn't look quite right

On Fri, Aug 20, 2010 at 7:52 PM, Tim Moore <tim_at_[hidden]> wrote:
> struct ar_hash : std::unary_function<small_array, std::size_t> {
>   std::size_t operator()(small_array const& x) const {
>     int init = 0;
>     return boost::hash_value(std::accumulate(x.begin(), x.end(), init));
>   }
> };

Consider inputs:

small_array one = {1,2,3,4};
small_array two = {1,2,2,5};

The sum of each is 10, which will result in the same hash.  This will
probably cause hash collisions and result in poorer performance than
combining each hash value.  Replacing the implementation with the
following should give better results:

return boost::hash_range(x.begin(), x.end());

Nate