specialize std::hash for dependent types

Question

I have defined this template class structure:

template<typename T> struct Outer {
    struct Inner { /* ...some stuff... */ };
};

I want to put Inner objects into an unordered_map (actually, not directly them but containers of them, so the approach of specifying hashing object directly on template parameters for unordered_map is not a great idea), thus I wanted to specialize the hash class for these items.

This will not work, because the compiler cannot match Outer<T>::Inner with the type specified when instantiating hash:

namespace std {
    template<typename T> struct hash<typename Outer<T>::Inner > {
        size_t operator ()( typename Outer<T>::Inner const & obj )
        { /* ...some stuff... */ }
    };
};

Does anyone know a solution to this?

Answer 1

You're obviously right that this will not work because the compiler cannot match a template specialization that is based on such a dependent type (e.g., Inner could be a nested typedef, then how would the compiler be able to tell the difference between that type coming from the nested typedef in Outer, versus from elsewhere? It can't, it's impossible to tell).

There are a number of solutions.

First, you could move the Inner class to the outside of the Outer class (and make them friends, if needed). You can also move it into a "detail" namespace or hide it in a number of other ways depending on your context. It is not uncommon for people to avoid such nested "Inner" classes because they can cause a number of problems like this and some older compilers even have problems accepting such nested classes at all. It's generally better practice to just move those nested classes out of the Outer class. In terms of actual code, you do this:

template <typename T>
struct Outer;  // forward-decl.

namespace detail {
  template <typename T>
  struct Outer_Inner {
    friend class Outer<T>;  // Optional

    // ....

  };
};

template <typename T>
struct Outer {
  typedef detail::Outer_Inner<T> Inner;
  friend class detail::Outer_Inner<T>;  // Optional

  // ...

};

namespace std {
  template<typename T> 
  struct hash< detail::Outer_Inner<T> > {
    // ..
  };
};

Another solution is to define your own hashing class that you can give to the unordered_set. Like this:

template <typename T>
struct Outer {

  struct Inner {
    //..
  };

  struct InnerHash {
    typedef Inner argument_type;
    typedef std::size_t result_type;

    result_type operator()(argument_type const& s) const {
      return /* some hashing code */;
    };
  };

  // ...

  // An example unordered-set member:
  std::unordered_set<Inner, InnerHash> m_set;

};

And finally, there is yet another solution I can think of that, like the first solution, has the advantage of specializing the std::hash class template. However, this solution is a bit convoluted, it involves wrapping your Inner class into an outside class template, like this:

template <typename T>
struct InnerWrapper {
  typedef typename Outer<T>::Inner value_type;
  value_type data;
};

and then creating the specialization std::hash< InnerWrapper<T> >. This solution really only has the advantage of being non-intrusive on the existing implementation of the Outer class, but creating an unordered_map in this case means that the map must contain (directly or indirectly) InnerWrapper objects instead of storing the Inner objects directly. Also, you should notice that this solution can be mixed with the first solution by having some of the functionality of Inner that is more tightly integrated with Outer implemented in a nested class, and having the more "public" functionality of Inner implemented in the outside class, thus avoiding the friendship relationship and allowing tighter Outer-Inner integration, while leaving a clean user-facing class to access Inner's functionalities.