CODEWITHSUNDEEP
c++11hashunordered-setuser-defined
John Smith
John Smith

Reputation: 201

where should I put the specialized std::hash for user defined type

I searched many pages, and I think I have known how to write the std::hash. But I don't know where to put it.

An example is presented here http://en.cppreference.com/w/cpp/utility/hash .

However, I defined my type Instance in namespace ca in file instance_management.h. I want to use unordered_set<Instance> in the same file in another class InstanceManager. So I write the following code:

namespace std
{
    template <> struct hash<ca::Instance>
    {
        size_t operator()(const ca::Instance & instance) const
        {
            std::size_t seed = 0;
            // Some hash value calculation here.
            return seed;
        }
    };
} // namespace std

But where should I put it? I tried many locations but all failed.

I am using visual studio 2013. I tried to put the previous code in some locations but all failed to compile it.

// location 1

namespace ca
{
    class Instance {...}
    class InstanceManager
    {
        // ... some other things.
        private unordered_set<Instance>;
    }
}

// location 2

Upvotes: 4

Views: 3026

Answers (3)

TemplateRex
TemplateRex

Reputation: 70526

There are several ways.

Specializing std::hash

In your code make sure that your std::hash<Instance> specialization is preceded immediately by the Instance class definition, and followed by the use of the unordered_set container that uses it. 

namespace ca
{
    class Instance {...};

}

namespaces std {

    template<> hash<Instance> { ... };

}

namespace ca {

    class InstanceManager
    {
        // ... some other things.
        private unordered_set<Instance>;
    }
}

One drawback is that you can have funny name lookup interference when passing a std::hash<ca::Instance> to other functions. The reason is that the associated namespace (ca) of all the template arguments of std::hash can be used during name lookup (ADL). Such errors are a bit rare, but if they occur they can be hard to debug.

See this Q&A for more details.

Passing your hash to unordered_set

struct MyInstanceHash { ... };

using MyUnorderedSet = std:unordered_set<Instance, MyInstanceHash>;

Here, you simply pass your own hash function to the container and be done with it. The drawback is that you have to explicitly type your own container.

Using hash_append

Note, however, there is the N3980 Standard proposal is currently pending for review. This proposal features a much superior design that uses a universal hash function that takes an arbitrary byte stream to be hashed by its template parameter (the actual hashing algorithm) 

template <class HashAlgorithm>
struct uhash
{
    using result_type = typename HashAlgorithm::result_type;

    template <class T>
    result_type
    operator()(T const& t) const noexcept
    {
        HashAlgorithm h;
        using std::hash_append;
        hash_append(h, t);
        return static_cast<result_type>(h);
    }
};

A user-defined class X then has to provide the proper hash_append through which it presents itself as a byte stream, ready to be hashed by the univeral hasher.

class X
{
    std::tuple<short, unsigned char, unsigned char> date_;
    std::vector<std::pair<int, int>>                data_;

public:
    // ...
    friend bool operator==(X const& x, X const& y)
    {
        return std::tie(x.date_, x.data_) == std::tie(y.date_, y.data_);
    }

    // Hook into the system like this
    template <class HashAlgorithm>
    friend void hash_append(HashAlgorithm& h, X const& x) noexcept
    {
        using std::hash_append;
        hash_append(h, x.date_);
        hash_append(h, x.data_);
    }
}

For more details, see the presentation by the author @HowardHinnant at CppCon14 (slides, video). Full source code by both the author and Bloomberg is available.

Upvotes: 4

Jonathan H
Jonathan H

Reputation: 7953

Do not specialise std::hash, instead write your own hash function object (see Edge_Hash below) and declare your unordered_set with two template arguments.

#include <unordered_set>
#include <functional>

namespace foo
{
    // an edge is a link between two nodes
    struct Edge
    {
        size_t src, dst;
    };

    // this is an example of symmetric hash (suitable for undirected graphs)
    struct Edge_Hash
    {
        inline size_t operator() ( const Edge& e ) const
        {
            static std::hash<size_t> H;
            return H(e.src) ^ H(e.dst);
        }
    };

    // this keeps all edges in a set based on their hash value
    struct Edge_Set
    {
        // I think this is what you're trying to do?
        std::unordered_set<Edge,Edge_Hash> edges;
    };
}

int main()
{
    foo::Edge_Set e;
}

Related posts are, eg:

Upvotes: 1

John Smith
John Smith

Reputation: 201

Thanks to everyone.

I have found the reason and solved the problem somehow: visual studio accepted the InstanceHash when I was defining instances_. Since I was changing the use of set to unordered_set, I forgot to specify InstanceHash when I tried to get the const_iterator, so this time the compiler tried to use the std::hash<> things and failed. But the compiler didn't locate the line using const_iterator, so I mistakenly thought it didn't accept InstanceHash when I was defining instances_.

I also tried to specialize the std::hash<> for class Instance. However, this specialization requires at least the declaration of class ca::Instance and some of its member functions to calculate the hash value. After this specialization, the definition of class ca::InstanceManage will use it.

I now generally put declarations and implementations of almost every classes and member functions together. So, the thing I need to do is probably to split the ca namespace scope to 2 parts and put the std{ template <> struct hash<ca::Instance>{...}} in the middle.

Upvotes: 0

Related Questions