Boost logo

Boost Users :

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 <> wrote:
Please do not top-post.

On Fri, Aug 20, 2010 at 4:07 PM, B Hart <> 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};


  // 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);


  BOOST_ASSERT(arSet.size() == 1);

  return 0;



Timothy Moore
Montecito Software LLC

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at