Следующая программа не компилирует неупорядоченный набор пар целых чисел, но это делает для целых чисел. Можно ли использовать unordered_set и его функции-члены для пользовательских типов, и как я могу его определить?
#include <unordered_set>
...
class A{
...
private:
std::unordered_set< std::pair<int, int> > u_edge_;
};
Ошибка компилятора:
ошибка: нет подходящей функции для вызова 'std :: unordered_set> :: unordered_set()'
Ваш код компилируется на VS2010 SP1 (VC10), но он не скомпилируется с GCC g++ 4.7.2.
Однако вы можете рассмотреть boost::hash от Boost.Functional до хэша a std::pair (с этим дополнением ваш код компилируется также с 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_;
};
Нет стандартного способа вычисления хэша на паре. Добавьте это определение в свой файл:
struct pair_hash {
inline std::size_t operator()(const std::pair<int,int> & v) const {
return v.first*31+v.second;
}
};
Теперь вы можете использовать его следующим образом:
std::unordered_set< std::pair<int, int>, pair_hash> u_edge_;
Это работает, потому что pair<T1,T2> определяет равенство. Для пользовательских классов, которые не обеспечивают способ проверки равенства, вам может потребоваться предоставить отдельную функцию для проверки, если два экземпляра равны друг другу.
Конечно, это решение ограничено парой из двух целых чисел. Вот ссылка на ответ, которая поможет вам определить более общий способ создания хэша для нескольких объектов.
Проблема заключается в том, что std::unordered_set использует std::hash для вычисления хэшей для своих записей, а для пар нет специализации std::hash. Поэтому вам придется сделать две вещи:
std::hash для вашего типа ключа (std::pair<int, int>) с помощью этой функции.Вот простой пример:
#include <unordered_set>
namespace std {
template <> struct hash<std::pair<int, int>> {
inline size_t operator()(const std::pair<int, int> &v) const {
std::hash<int> int_hasher;
return int_hasher(v.first) ^ int_hasher(v.second);
}
};
}
int main()
{
std::unordered_set< std::pair<int, int> > edge;
}
Вам необходимо предоставить специализацию std::hash<>, которая работает с std::pair<int, int>. Вот очень простой пример того, как вы могли бы определить специализацию:
#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_;
};
Вам не хватает хэш-функции для std::pair<int, int>>. Например,
struct bad_hash
{
std::size_t operator()(const std::pair<int,int>& p) const
{
return 42;
}
};
....
std::unordered_set< std::pair<int, int>, bad_hash> u_edge_;
Вы также можете выделить std::hash<T> для std::hash<std::pair<int,int>>, и в этом случае вы можете опустить второй параметр шаблона.
Все остальные ответы здесь предлагают создать хеш-функцию, которая каким-то образом объединяет ваши два целых числа.
Это будет работать, но выдает неуникальные хеши. Хотя это хорошо для использования unordered_set, для некоторых приложений это может быть неприемлемо. В вашем случае, если вы выбрали плохую хеш-функцию, это может привести к множеству ненужных коллизий.
Но вы можете создавать уникальные хеши!
int обычно 4 байта. Вы можете сделать это явным образом используя int32_t.
Тип хеш-типа: std::size_t. На большинстве машин это 8 байтов. Вы можете проверить это после компиляции.
Поскольку пара состоит из двух типов int32_t, вы можете поместить оба числа в std::size_t чтобы создать уникальный хеш.
Это выглядит так (я не могу без посторонней помощи вспомнить, как заставить компилятор обрабатывать подписанное значение, как если бы оно было беззнаковым для битовых манипуляций, поэтому я написал следующее для uint32_t.):
#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>
struct IntPairHash {
std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
assert(sizeof(std::size_t)>=8); //Ensure that std::size_t, the type of the hash, is large enough
//Shift first integer over to make room for the second integer. The two are
//then packed side by side.
return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
}
};
int main(){
std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
uset.emplace(10,20);
uset.emplace(20,30);
uset.emplace(10,20);
assert(uset.size()==2);
}
Как уже упоминалось в большинстве других ответов на этот вопрос, вам нужно предоставить хеш-функцию для std::pair<int, int>. Однако, начиная с С++ 11, вы также можете использовать лямбда-выражение вместо определения хеш-функции. Следующий код принимает решение, данное dasblinkenlight в качестве основы:
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);
Я хотел бы повторить отказ от ответственности dasblinkenlight: это решение ограничено парой из двух целых чисел. Этот ответ дает идею для более общего решения.
Хорошо, вот простое решение с гарантированными не столкновениями. Просто сведите вашу проблему к существующему решению, то есть конвертируйте вашу пару int в string следующим образом:
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)));
Наслаждайтесь!