How to make boost unordered_map to support flyweight<string>

Question

I am trying to do the following:

boost::unordered_map<boost::flyweight<std::string>, boost::flyweight<std::string> > map;

        boost::flyweight<std::string> foo(name);
        map[foo] = foo;

But the compiler complains: "error C2665: 'boost::hash_value' : none of the 17 overloads could convert all the argument types".

But I have defined the following function:

std::size_t hash_value(const boost::flyweight<std::string> & b)
{
    boost::hash<std::string> hasher;
    const std::string & str = b.get();
    return hasher(str);
}
bool operator==(const boost::flyweight<std::string>& f, const boost::flyweight<std::string> & second)
{
    return f.get() == second.get();
}

But it doesn´t compile.

What do I need to do to make boost unordered_map to support flyweight?

[EDIT] I got it to work with the following code:

    struct flyweight_hash
    {
        std::size_t operator()(const boost::flyweight<std::string> &elm) const
        {
            boost::hash<std::string> hasher;
            const std::string & str = elm.get();
            return hasher(str);
        }
    };

and passed it as a template parameter to the construction of the map:

boost::unordered_map<boost::flyweight<std::string>, boost::flyweight<std::string> , flyweight_hash > map;

In this case I don´t understand way overloading hash_value didn´t worked.

Americano

Answer 1

boost::hash calls hash_value through argument dependent lookup (ADL). You are trying to define a hash_value function for a class in namespace boost. Hence your hash_value function would need to go into this namespace as well for ADL to work. Unfortunately, adding functions to a foreign namespace is rather evil and should be avoided. Your solution of using a custom hasher seems fine.

A little example code to illustrate:

namespace boost {
  // somewhere in boost
  template<typename T>
  std::size_t hash(const T& t) { 
    // call using ADL
    // e.g. if called with object of class type foo::bar this will
    // pick up foo::hash_value despite the lack of namespace
    // qualification
    return hash_value(t); 
  }
}

// your hash_value (presumably in the global namespace)
// not picked up by above call
std::size_t hash_value(boost::flyweight<T>...);

namespace boost {
  // this would be picked up but is slightly evil
  std::size_t hash_value(boost::flyweight<T>...);
}

Fenton

It's only bad because boost::unordered_map's default hasher doesn't seem to trigger ADL by using boost::hash_value; return hash_value(key);. I can't check that right now though. – Daryn

@Daryn The default hasher should be boost::hash and should not be specific to unordered_map. At least the doc says so. – Fenton

Sure, but that doesn't change that ADL-enabled calls don't seem to be used. – Daryn

@Daryn How would ADL be able to find the hash_value shown in the example? flyweight is in namespace boost and there is no matching overload in that namespace and the one outside of the namespace won't be considered. Unless OP actually defined his hash_value in that namespace, but I doubt that. – Fenton

Err, right.. nevermind me, I actually got a bit confused here. :| – Daryn

@Daryn I added some example code to make things a little clearer. – Fenton

Answer 2

It is a pity to hash something which has already been hashed. Flyweight keeps a single instance of equal objects, so it is more efficient to hash the address of this instance, instead of its content. I do as follows (in std, not in boost, as I'm using C++11, so I'm extending std::hash, not boost::hash):

namespace std
{
  template <typename T>
  struct hash<boost::flyweight<T, boost::flyweights::no_tracking>>
  {
    using value_type = boost::flyweight<T, boost::flyweights::no_tracking>;
    size_t operator()(const value_type& ss) const
    {
      hash<const void*> hasher;
      return hasher(&ss.get());
    }
  };
}

I have been confirmed that this works by design, not by accident: http://lists.boost.org/boost-users/2013/03/78007.php

Chlorinate