specialize std::hash<T> 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?

Wino

Try typename Outer<T>::Inner. But it is a private type. Is that by design? – Stacey

@Stacey no, sorry I wrote wrong. It is public, and there is typename already – Wino

So what error do you get? – Stacey

no error, only a warning that the compiler will ignore the whole specialization Class template partial specialization contains a template parameter that can not be deduced, this partial specialization will never be used (clang++ 4.3ish) – Wino

If it compiles and only emits a warning it seems that the code where you actually use the unordered_map is ok. That code however uses on the hash<typename Outer<T>::Inner>, so if it does not get instantiated, one has to wonder what hash is used instead. Does the unordered_map compile and work as expected? Maybe the warning is misleading or bogous. – Crystalloid

@ArneMertz no, the code shown only gives a warning, but if you try to use that object in a unordered_map it doesn't compile – Wino

well, than that compiler error would be a vital addition to your question ;-) – Crystalloid

The problem is that the compiler doesn't know what typename Outer<T>::Inner is when you are specialising it; it could be anything. You will have to move Inner out of Outer and use Inner<T>. – Weeper

@ArneMertz The compiler error is nothing interesting. It is complaining about not finding a specialization for hash<Inner>, the same error you would get if you didn't write any specialization at all – Wino

@Weeper Yeah moving the inner class outside would solve it. I would like to avoid this road if possible though, because in my case that would mean some kind of CRTP definition for Inner which would make the code pretty unreadable. I probably would prefer to explicitly instantiate hash<Outer<T>::Inner for each concrete type T that I am going to use. – Wino

Relevant. – Hugues

I believe that the argument lies in 14.5.5.1: "The template arguments of a specialization are deduced from the arguments of the primary template." Since in the template argument in your partial specialization the parameter T of the specialization appears in a non-deduced context, this deduction cannot happen. (But I'm not sure how to phrase a coherent argument.) – Caves

Stuff like this is why hash<T> should be hash<T,void>, so we can run a SFINAE test against T to determine if we want to specialize it: that is, however, ugly. I wonder if concept based specializations will solve this issue? template<MyConcept X>struct hash<X>{? – Precedent

The fact it doesn't work makes sense because the compiler has no way to understand whether a certain type U used in some hash<U> has the same type of Outer<T>::Inner for a certain T except trying to compile the template Outer<> for all possible types. – Wino

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.

Morril