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: Tim Moore (tim_at_[hidden])
Date: 2010-08-20 21:52:48

    On 8/20/2010 4:22 PM, B Hart wrote:
> well assuming an unsigned int array size of 5 what do
>       you suggest for a reasonably good and fast hash?
>       
>       I was hoping that I could use the built in hash w/o having to
>       invent one.  
>       
> On Fri, Aug 20, 2010 at 3:32 PM,
>         OvermindDL1 <[e-mail]>
>         wrote:
> > Please do not top-post.
> >
> >             On Fri, Aug 20, 2010 at 4:07 PM, B Hart <[e-mail]>
> >             wrote:
> >             > Just a comparison function?  How is, for example,
> >             unordered set going to
> >             > know the end of the array, to hash it?  I don't know
> >             what is happening
> >             > under-the-hood so I'm deferring to the list experts.
> >             >
> >             > Can you give me a simple example?
> >             
> >           How is it going to know the end?
> >            That depends on how you create your array and set up your
> >           hash
> >           function.  If you have an end-of-array marker then you would
> >           stop at
> >           that (like how '\0' is the end-of-array marker for C strings),
> >           if it
> >           is a static length then you would just use that, etc...
> >         
>     
    
    
    I'm not claiming the following is the best hash function your
    example but here is one method showing syntactically how to do it. 
    The call to hash_value may not be needed.  Depending up the range of
    your values you could just sum the values up.
    
    
    #include <numeric>
    #include <boost/unordered_set.hpp>
    #include <boost/array.hpp>
    #include <boost/assert.hpp>
    
    typedef boost::array<int,5> small_array;
    
    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));
      }
    };
    
    int main() {
      boost::unordered_set<small_array, ar_hash> arSet;
    
      small_array  one = {1,2,3,4}, one_copy = {1,2,3,4};
      small_array  two = {1,2,3,5};
      small_array  three = {1,2,3};
    
      arSet.insert(one);
    
      // Can we find the one element ?
      BOOST_ASSERT(arSet.find(one) != arSet.end());
    
      // Can we find another array with same elements ??
      BOOST_ASSERT(arSet.find(one_copy) != arSet.end());
    
               
      // Should not find a different array
      BOOST_ASSERT(arSet.find(two) == arSet.end());
    
      // Ditto but different size
      BOOST_ASSERT(arSet.find(three) == arSet.end());
    
      // Insert a copy with identifical elements. Size should still be
    one
      BOOST_ASSERT(arSet.size() == 1);
    
      arSet.insert(one_copy);
    
      BOOST_ASSERT(arSet.size() == 1);
    
      return 0;
    }
    
    
    HTH,
    
    Tim
    
Timothy Moore
Montecito Software LLC
http://www.montecito-software.com