unordered_set storing elements as pointers

c++, equality, hash, pointers, unordered

Solution

For the hash function, you have a choice between specializing `boost::hash` (or `std::hash` in the newer standard) or defining a new functor class. These alternatives work equally well.

For the equality operator, you need to define a new functor, because you cannot redefine the equality operator over pointers. It's a built-in operator (defined in functional terms as `bool operator==( T const *x, T const *y )`) and cannot be replaced.

Both of these can be defined generically by using a templated `operator()` in a non-templated class.

struct indirect_equal {
    template< typename X, typename Y >
    bool operator() ( X const &lhs, Y const &rhs )
        { return * lhs == * rhs; }
};

Follow a similar pattern for the hasher.

Problem

To narrow it down: I'm currently using Boost.Unordered. I see two possible solutions: Define my own Equality Predicates and Hash Functions and to utilize templates (maybe `is_pointer`) to distinct between pointers and instances; Simply to extend `boost::hash` by providing `hash_value(Type* const& x)` as for hashing; and add `==` operator overload as free function with `(Type* const& x, Type* const& y)` parameters as for equality checking. I'm not sure whether both variations are actually possible, since I didn't test them. I would like to find out you handle this problem. Implementations are welcome :) EDIT 1: What about this? ``` template<class T> struct Equals: std::binary_function<T, T, bool> { bool operator()(T const& left, T const& right) const { return left == right; } }; template<class T> struct Equals<T*> : std::binary_function<T*, T*, bool> { bool operator()(T* const& left, T* const& right) const { return *left == *right; } }; ``` EDIT 2: I've just defined: ``` friend std::size_t hash_value(Base const& base) { boost::hash<std::string> hash; return hash(base.string_); } friend std::size_t hash_value(Base* const& base) { return hash_value(*base); } ``` And then: ``` Derived d1("x"); Derived d2("x"); unordered_set<Base*> set; set.insert(&d1); assert(set.find(&d2) == end()); ``` Debugger says that `friend std::size_t hash_value(Base* const& base)` is never called (GCC 4.7). Why is that? EDIT 3: I found out that `template <class T> std::size_t hash_value(T* const& v)` in `boost/functional/hash.hpp` on line #215 (Boost 1.49) is Boost's specialization for pointers and it simply masks your custom implementation of `hash_value` such as mine in EDIT 2. Therefore, it seems like the only way here is to create a custom Hash Functor.

Original source