Unordered Set of Pairs, Compilation Error

Unordered set of pairs, compilation error

That error message appears when you have failed to specialise std::hash or provide a hasher type for your unordered container (see e.g. Using C++11 unordered_set in Visual C++ and clang). The XCode error in this case is particularly unfriendly!

C++11 does not provide a hash for pairs (or tuples), even of hashable types. This discussion indicates that this was primarily due to a lack of time to get anything better in; however I'm not aware whether there will be anything better in C++14.

Specialising std::hash<std::pair<int, int>> is probably not a good idea (and is not permitted by the language; specialising std templates is only allowed for user-defined types), so you'll have to provide a hasher:

struct MoveHasher {
    std::size_t operator()(const std::pair<int, int> &val) const { ... }
};
typedef std::unordered_set<Move, MoveHasher> Set;

See How do I combine hash values in C++0x? for how to write the hash function.

Alternatively, you could make Move a user-defined class (probably a good idea!) and then specialising std::hash will be fine.

Why can't I use pair as key of unordered_set / unordered_map?

The unordered_* containers need a hash function. By default, they use std::hash but there is no specialization of std::hash for std::pair<T1,T2> provided in the standard library. On the other hand, the ordered containers rely on std::less (by default) and std::pair does have operator< provided. That's why it just works.

In order to have an unordered container with a pair, you will have to provide a hash functor yourself. For example:

struct SimpleHash {
    size_t operator()(const std::pair<int, int>& p) const {
        return p.first ^ p.second;
    }
};

std::unordered_set<std::pair<int, int>, SimpleHash> S;
S.insert(std::make_pair(0, 1));

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

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_;
};

Compilation error related to map and unordered_map: attempting to reference a deleted function

Following on from @JohnZwinck's (excellent) answer, I would say that using std::unordered_map with a vector as a key is usually a bad idea, because of the likely high cost of implementing any kind of effective hashing function.

The link John gave expands on this, but, essentially, the hash function has to inspect every element in the vector every time anything needs to be hashed. If the vector is large, well, ouch!

So std::map is likely to be a better choice here, because std::less (-> operator<) is likely to be cheap - as soon as we hit an element of the vector whose value differs between the two operands, we are done. Worst case, it is no more expensive (although it's true that std::unordered_map is more efficient than std::map when a cheap and effective hashing function does exist, especially, for example, if the key is something like an int).

Multimap with key as unordered set and value as integer pair - unable to call find member function

Like others said, you're

missing a hash implementation
using a pretty inefficient key type

I'd simplify on both accounts:

Live On Compiler Explorer

#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>
#include <boost/functional/hash.hpp>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <fmt/ranges.h>

using Key   = boost::container::flat_set<int, std::less<>,
                                       boost::container::small_vector<int, 4>>;
using Value = std::pair<int, int>;

template <> struct std::hash<Key> {
    size_t operator()(Key const& s) const { return boost::hash_range(s.begin(), s.end()); }
};

using user_type_mmap       = std::unordered_multimap<Key, Value>;
using user_type_mmap_entry = user_type_mmap::value_type;

bool ensure(user_type_mmap& uom, Key key, Value val) {
    if (uom.find(key) == uom.end()) {
        uom.emplace(std::move(key), std::move(val));
        return false;
    } else {
        return true;
    }
}

int main(){
    user_type_mmap uom{
        {{2, 3}, {8, 9}},
        {{3, 4}, {9, 10}},
    };

    fmt::print("1: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, {4, 5}));
    fmt::print("2: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, {4, 8}));
    fmt::print("3: {}\n", uom);
}

Prints

1: {({3, 4}, (9, 10)), ({2, 3}, (8, 9))}
insertion: false
2: {({1, 4}, (4, 5)), ({2, 3}, (8, 9)), ({3, 4}, (9, 10))}
insertion: true
3: {({1, 4}, (4, 5)), ({2, 3}, (8, 9)), ({3, 4}, (9, 10))}

This also makes the key type not use any dynamic allocation when the set is small enough.

BONUS IDEA

It looks a bit like you're manually shoe-horning additional key restrictions into standard containers. Consider using MultiIndex:

Live On Compiler Explorer

#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>

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

#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index_container.hpp>

#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <iostream>

namespace bmi = boost::multi_index;

using Key = boost::container::flat_set<int, std::less<>,
                                    boost::container::small_vector<int, 4>>;

template <> struct boost::hash<Key> {
    size_t operator()(Key const& k) const {
        return boost::hash_range(k.begin(), k.end());
    }
};

struct Record {
    Key key;
    int a, b; // the pair

    friend std::ostream& operator<<(std::ostream& os, Record const& r)
    {
        fmt::format_to(std::ostreambuf_iterator<char>(os), "{{ k:{} a:{} b:{} }}", r.key, r.a, r.b);
        return os;
    }
};

using Table = bmi::multi_index_container<
    Record,
    bmi::indexed_by< //
        //bmi::ordered_non_unique<bmi::tag<struct byKey>,
                                //bmi::member<Record, Key, &Record::key>>,
        bmi::hashed_non_unique<bmi::tag<struct byKeyHash>,
                                bmi::member<Record, Key, &Record::key>>,
        bmi::ordered_unique<
            bmi::tag<struct byFull>,
            bmi::composite_key<Record, //
                            bmi::member<Record, Key, &Record::key>,
                            bmi::member<Record, int, &Record::a>,
                            bmi::member<Record, int, &Record::b> //
                            >>>>;

bool ensure(Table& uom, Key key, int a, int b) {
    return uom.insert(Record{std::move(key), a, b}).second;
}

int main(){
    Table uom{
        {{2, 3}, 8, 9},
        {{3, 4}, 9, 10},
    };

    fmt::print("1: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 5));
    fmt::print("2: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 8));
    fmt::print("3: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 5));
    fmt::print("4: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
}

Prints

1: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }]
insertion: true
2: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:5 }] count {1,4}:1
insertion: true
3: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:8 }, { k:[1, 4] a:4 b:5 }] count {1,4}:2
insertion: false
4: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:8 }, { k:[1, 4] a:4 b:5 }] count {1,4}:2

incomplete type for std::unordered_set compiling error in g++5, compiles in clang++

It is undefined behavior to instantiate a standard library container with an incomplete type. [res.on.functions]/1, 2.5:

1 In certain cases (replacement functions, handler functions,
operations on types used to instantiate standard library template
components), the C++ standard library depends on components supplied
by a C++ program. If these components do not meet their requirements,
the Standard places no requirements on the implementation.

2 In particular, the effects are undefined in the following cases:

[...]

if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for
that component.

Both implementations are correct.

There is currently a proposal to add incomplete type support to some containers, but it is limited to vector, list and forward_list.

Why can't I compile an unordered_map with a pair as key?

You need to provide a suitable hash function for your key type. A simple example:

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

This will work, but not have the best hash-properties^†. You might want to have a look at something like boost.hash_combine for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.

For real world use: Boost also provides the function set hash_value which already provides a hash function for std::pair, as well as std::tuple and most standard containers.

^†More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.

Can't use lambda as hash for unordered_set of pairs?

You need to compile with C++20 mode, i.e. with the option -std=c++2a.

Before C++20 lambda closure types have no default constructor.

Closure types are not DefaultConstructible. Closure types have no default constructor (until C++20)
If no captures are specified, the closure type has a defaulted default constructor. (since C++20)

Unordered Set of Pairs, Compilation Error