How to Make an Unordered Set of Pairs of Integers in C++

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

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));

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

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.

---

Related Topics