Specializing std::hash for nested class in a template class

Question

I have a template class Baz which contains a nested class Sub. I'd like to define a hash function for this subclass by specializing std::hash. However, it doesn't seem to work.

#include <functional>

struct Foo {
    struct Sub {
    };
};

template <class T>
struct Bar {
};

template <class T>
struct Baz {
    struct Sub {
        int x;
    };
};

// declare hash for Foo::Sub - all right
namespace std {
    template <>
    struct hash< Foo::Sub >;
}

// declare hash for Bar<T> - all right
namespace std {
    template <class T>
    struct hash< Bar<T> >;
}

// declare hash function for Baz<T>::Sub - doesn't work!
namespace std {
    template <class T>
    struct hash< Baz<T>::Sub >;
}

// Adding typename produces a different error.
namespace std {
    template <class T>
    struct hash< typename Baz<T>::Sub >;
}

Gcc 4.5.3 complains:

$ g++ -std=c++0x -c hash.cpp
hash.cpp:34:30: error: type/value mismatch at argument 1 in template parameter list for ‘template<class _Tp> struct std::hash’
hash.cpp:34:30: error:   expected a type, got ‘Baz<T>::Sub’
hash.cpp:40:12: error: template parameters not used in partial specialization:
hash.cpp:40:12: error:         ‘T’

UPDATE

What I'm really trying to do is implement a container which supports stable references (not in the C++ sense) to elements within it. I want to allow the user to insert these references into std::unordered_set and similar, and use them to access or modify existing elements efficiently. The following is just a mockup, not the exact container I'm implementing. The problem is in defining a hash function for the reference type.

template <class T>
class Container {
public:
    class Reference {
    public:
        // operator==, operator!=, operator< ...., isNull()
    private:
        size_t index; // index into m_entries (or could be anything else)
        // possibly more stuff
    };

    Reference insert (const T &value);
    Reference find (const T &value);
    void remove (Reference r);
    Reference first ();
    Reference next (Reference prev);

private:
    struct Entry { T value, ... };

    std::vector<Entry> m_entries;
};

Answer 1

The answer to this question is that what you're trying to do is simply impossible to do. The compiler cannot figure out what outer class contains a subtype. Consider why:

struct outer1 { typedef int Sub; };
struct outer2 { typedef int Sub; };

How is the compiler supposed to figure out which outer you want when it gets a Sub? It cannot. There's no possible way for this to work.

In your case it could be remotely possible, though extremely difficult, to derive IFF Sub dependend upon T. But this would require the compiler to know where Sub comes from and it just doesn't.

So you simply cannot do this. No way, no how.

If you need some generic approach to finding a hash function for your types then you'll need to make a metafunction get_hash. It could look for a "hash_type" internal typedef by default and be overridden for the standard hashes. Lot of typing...

Alternatively, put Sub out of the containing class as its own template and have a typedef there instead of inner class. Then you can specialize hash on your template.

Otherwise, just supply the hash you know you need to the hash function parameter to the template you're using.

Answer 2

Just pull the Reference class out of Container.

template <class Container>
class Reference {
public:
    typedef typename Container::value_type value_type; // etc...

    // operator==, operator!=, operator< ...., isNull()
private:
    size_t index; // index into m_entries (or could be anything else)
    // possibly more stuff
};

template <class T>
class Container {
public:
    typedef ::Reference<Container> Reference;
    friend class Reference; // If you cannot help it

    typedef T value_type;

    Reference insert (const T &value);
    Reference find (const T &value);
    void remove (Reference r);
    Reference first ();
    Reference next (Reference prev);

private:
    struct Entry { T value, ... };

    std::vector<Entry> m_entries;
};

Specialize like this:

namespace std {
    template <typename Container>
    struct hash<Reference<Container>>;
}

Answer 3

You cannot specialize a template on a dependent type like that. I would try something like this.

struct yes {};

template <typename T>
yes accept_baz_sub(typename Baz<T>::Sub&&);
void accept_baz_sub(...);

template <class T>
struct is_baz_sub : std::is_same<decltype(accept_baz_sub(std::declval<T>())), yes>
{};

template <typename BazSub>
using CheckedBazSub = typename std::enable_if<is_baz_sub<BazSub>::value, BazSub>::type;

namespace std {
    template <class BazSub>
    struct hash<CheckedBazSub<BazSub>>;
}

Edit: This doesn't quite work, according to [temp.alias] §14.5.7.2 an alias template name is never deduced.

Another solution would be to write your own hash function object and let the container use that (third template parameter of std::unordered_map for instance).