我试图创建一个以std::pair为键的std::unordered_map，并返回size_t作为值。对我来说棘手的部分是，我想为我的映射定制散列函数，以忽略键std::pair成员的顺序。即:
std::pair<int,int> p1 = std::make_pair<3,4>;
std::pair<int,int> p2 = std::make_pair<4,3>;
std::unordered_map<std::pair<int,int>, int> m;
m[p1] = 3;
// m[p2] should now also return 3!
这不是一个明确的MWE，但它是我试图在我的程序中做的一个切割:
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <memory>
#include <unordered_map>
#include <functional>
class Point
{
public:
static size_t id_counter;
size_t id;
Point()=default;
~Point()=default;
bool operator==(const Point& rhs)
{
return id == rhs.id;
}
friend std::ostream& operator<<(std::ostream& os, Point& P);
};
size_t Point::id_counter = 0;
class Hasch_point_pair
{
public:
size_t operator()(const std::pair<Point*, Point*>* p) const
{
// XOR hash. We don't care about collision we're FREAKS
auto h1 = std::hash<size_t>()(p->first->id);
auto h2 = std::hash<size_t>()(p->second->id);
return h1^h2;
}
};
int main(int argc, char const *argv[])
{
auto p1 = std::make_unique<Point>();
auto p2 = std::make_unique<Point>();
auto p3 = std::make_unique<Point>();
auto p4 = std::make_unique<Point>();
std::unordered_map<std::pair<Point*, Point*>*, size_t*, Hasch_point_pair> m;
auto p = std::make_unique<std::pair<Point*, Point*>>(p1.get(),p2.get());
auto p_hmm = std::make_unique<std::pair<Point*, Point*>>(p2.get(),p1.get());
size_t value = 3;
m[p.get()] = &value;
std::cout << "m[p] = " << m.at(p.get()) << std::endl;
std::cout << "m[p_hmm] = " << m.at(p_hmm.get()) << std::endl;
}
我的一个想法是比较每个点的id，并始终使用最大id成员变量的点作为第一个哈希，但我还没有得到它的工作。这有意义吗?
class Hasch_point_pair
{
public:
size_t operator()(const std::pair<Point*, Point*>* p) const
{
if (p->first->id > p->second->id)
{
auto h1 = std::hash<size_t>()(p->first->id);
auto h2 = std::hash<size_t>()(p->second->id);
return h1^h2;
}
else
{
// Note switched order of hash1 and hash2!
auto h2 = std::hash<size_t>()(p->first->id);
auto h1 = std::hash<size_t>()(p->second->id);
return h1^h2;
}
}
};
使用自定义类进行相等性测试:
class Equal_point_pair
{
public:
bool operator(
const std::pair<Point *, Point *> p1,
const std::pair<Point *, Point *> p2) const
{
// Verify if both pair are in the same order
const bool p1Asc = p1->first-> id < p1->second-> id;
const bool p2Asc = p2->first-> id < p2->second-> id;
// If both point are in same order, compare same members
// Otherwise, compare swaped members...
return p1Asc == p2Asc ?
*p1->first == *p2->first && *p1->second == *p2->second :
*p1->first == *p2->second && *p1->second == *p2->first;
}
};
注意，上面的代码做了我认为你想做的…我还没有测试代码。
那么你的map将被这样声明:
using PointMap = std::unordered_map<
std::pair<Point*, Point*>*,
size_t*,
Hasch_point_pair,
Equal_pointPair>;
PointMap m;
顺便说一下，不确定为什么要使用(嵌套)指针…
当drew告诉你你的问题是operator==而不是std::hash时，他指出了问题所在。那么，如何解决呢?
好吧，显而易见的解决方案是定义自己的类型(可以从std::pair继承)，它定义operator==以您需要的方式工作。比如:
template <typename T> struct my_pair : std::pair <T, T>
{
using std::pair<T, T>::pair;
bool operator== (const my_pair &other)
{
using std::swap;
std::pair p1 = *this;
std::pair p2 = other;
if (p1.first < p1.second)
swap (p1.first, p1.second);
if (p2.first < p2.second)
swap (p2.first, p2.second);
return p1 == p2;
}
};
注意，这段代码假设first和second使用相同的类型(因为在我看来这是必要的)。它也可以被改进以做更少的工作，但我想让事情保持简单(参见Deduplicator的评论以获得更好的版本)。