How can I make an unordered set of pairs of integers in C++?

Question

The following program does not compile an unordered set of pairs of integers, but it does for integers. Can unordered_set and its member functions be used on user-defined types, and how can I define it?

#include <unordered_set>
...

class A{
...
private: 
    std::unordered_set< std::pair<int, int> > u_edge_;
};

Compiler error:

error: no matching function for call to 'std::unordered_set >::unordered_set()'

Solution 1

Your code compiles on VS2010 SP1 (VC10), but it fails to compile with GCC g++ 4.7.2.

However, you may want to consider boost::hash from Boost.Functional to hash a std::pair (with this addition, your code compiles also with g++).

#include <unordered_set>
#include <boost/functional/hash.hpp>

class A
{
private: 
    std::unordered_set< 
        std::pair<int, int>, 
        boost::hash< std::pair<int, int> > 
    > u_edge_;
};

Solution 2

There is no standard way of computing a hash on a pair. Add this definition to your file:

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

Now you can use it like this:

std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

This works, because pair<T1,T2> defines equality. For custom classes that do not provide a way to test equality you may need to provide a separate function to test if two instances are equal to each other.

Of course this solution is limited to a pair of two integers. Here is a link to an answer that helps you define a more general way of making hash for multiple objects.

Solution 3

As already mentioned in most of the other answers on this question, you need to provide a hash function for std::pair<int, int>. However, since C++11, you can also use a lambda expression instead of defining a hash function. The following code takes the solution given by Sergey as basis:

auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);

Code on Ideone

I'd like repeat Sergey's disclaimer: This solution is limited to a pair of two integers. This answer provides the idea for a more general solution.

Solution 4

OK here is a simple solution with guaranteed non collisions. Simply reduce your problem to an existing solution i.e. convert your pair of int to string like so:

 auto stringify = [](const pair<int, int>& p, string sep = "-")-> string{
    return to_string(p.first) + sep + to_string(p.second);
 }

 unordered_set<string> myset;
 myset.insert(stringify(make_pair(1, 2)));
 myset.insert(stringify(make_pair(3, 4)));
 myset.insert(stringify(make_pair(5, 6)));

Enjoy!

Solution 5

You need to provide a specialization for std::hash<> that works with std::pair<int, int>. Here is a very simple example of how you could define the specialization:

#include <utility>
#include <unordered_set>

namespace std
{
    template<>
    struct hash<std::pair<int, int>>
    {
        size_t operator () (std::pair<int, int> const& p)
        {
            // A bad example of computing the hash, 
            // rather replace with something more clever
            return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
        }
    };
}

class A
{
private:
    // This won't give you problems anymore
    std::unordered_set< std::pair<int, int> > u_edge_;
};

View more solutions

Comments

[Alex Chamberlain]

Your functor should exten std::unary_function

[juanchopanza]

@AlexChamberlain I thought that stuff was deprecated.

[Mike Seymour]

@AlexChamberlain: Why should it do that? This class meets all the hash requirements.

[Alex Chamberlain]

@juanchopanza Fair enough, though I'm still working with C++03 at work.

[Alex Chamberlain]

@MikeSeymour Because you don't know who else will use your functors.

[juanchopanza]

@AlexChamberlain I know the feeling! But since the question deals with std::unordered_set I think it is safe to assume OP wants an C++11 solution.

[Brad Larson]

Comments are not for extended discussion; this conversation has been moved to chat.