在我的例子中，如何重载 equal 方法以使不同的对象在 unordered_multimap 中具有相同的哈希码值

Question

我写过这样的地图：

unordered_multimap<Point, int, StrHash, StrCompare> map

StrHash()是创建hashcode，StrCompare()是解决hashcode冲突。但我想做如下事情：

A和B有不同的hashcode值，但是A等于B，那么运行StrCompare()方法。我该怎么做，就像点 A(220,119) 和 Point B(220,220) 具有不同的哈希码一样。我可以重载哈希码等于方法吗制作A == B？在我的例子中，我想得到 Points，它们相互比较 (abs(a.x - b.x) + abs(a.y - b.y) < 3)。就像，Point(220,220)(220,119)(220,118)(220,220) 我的代码如下：

#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <iostream>
#include <math.h>
#include <string>

using std::string;
#include <unordered_map>
using std::unordered_multimap;
using namespace std;
using namespace cv;
class StrHash{
public:
    size_t operator()(const Point a) const {

        return a.x * 1000 + a.y;
    }
};
class StrCompare{
public:
    bool operator()(const Point& a, const Point& b) const {

        if (abs(a.x - b.x) + abs(a.y - b.y) < 3) {
            return true;
        }
        else
            return false;
    }

};

int main()
{
    unordered_multimap<Point, int, StrHash, StrCompare> map;
    map.insert(make_pair(Point(30, 120), 1));
    map.insert(make_pair(Point(220, 120), 2));
    map.insert(make_pair(Point(220, 120), 3));
    map.insert(make_pair(Point(220, 120), 4));
    map.insert(make_pair(Point(220, 119), 5));
    map.insert(make_pair(Point(30, 120), 6));
    unordered_multimap<Point, int, StrCompare>::iterator iter1;
    unordered_multimap<Point, int, StrCompare>::iterator iter2;
    for (iter1 = map.begin(); iter1 != map.end();)//
    {
        int num = map.count((*iter1).first);
        iter2 = map.find((*iter1).first);
        if (num > 2) {
            for (int i = 1; i <= num; i++)
            {
                cout << (*iter2).first << "  " << i << endl;
                iter2++;
            }
            iter1++;
        }
        else {

            iter1++;

        }

    }

}

Answer 1

这不是哈希映射/unordered_map 的工作方式。根据定义，如果哈希值不相等，则对象不相等。不仅如此，您的 "equality" 运算符还允许 A(220,119)、B(220,220)、C(220, 222) 之类的操作，其中 A == B 和 B == C 但 A != C。我可以看不出有什么方法可以完成您在这个问题中提出的问题，但是您是否正在尝试解决真正的问题？

根据您的评论，您似乎想要 std::vector 而不是 std::unordered_map。然后你只需使用 std::find 来找到你关心的元素，而不是通过无操作散列的间接方式。

Answer 2

必须这样说，因为如果您的容错能力允许的话，事情会容易得多：您可以将您的值四舍五入到最接近的 2 或 3 的倍数。

MarkB 关于使用 vector 的建议非常好...只是出于知识兴趣列出了其他一些。

使用 unordered_map 可以获得您想要的功能，但不是很干净：您需要使用地图的代码来编排近似相等的逻辑。首先，相等函数必须检查 actual equality:

struct PointCompare{
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};

那么，你需要这样的支持函数：

template <class Map>
auto approx_find(Map& map, const Point& point) -> decltype(map.begin())
{
    decltype(map.end()) it;
    for (int x_offset = -2; x_offset <= 2, ++x_offset)
        for (int y_offset = -2; y_offset <= 2, ++y_offset)
            if (abs(x_offset) + abs(y_offset) < 3 &&
                (it = map.find({point.x + x_offset, point.y + y_offset})) != map.end())
            return it;
    return map.end();
}

然后，您可以使用返回的迭代器来查看您要插入的 Point 是否重复，以及查找、eraseing 等。

请注意，性能不会很好。每个 approx_find 都有效地搜索 Point 参数，如下所示：

       <------------- X axis -------------->
  ^
  |                   0,-2
  |             -1,-1 0,-1 1,-1
Y axis      -2,0 -1,0 0,0  1,0, 2,0
  |              -1,1 0,1  1,1
  |                   0,2
  v

总共有 13 次查找 - 或多或少随机散布在散列 table 的桶周围，因此不是特别缓存友好 - 而不是通常的 1.

一个完全不同的选择是使用 unordered_multimap 来跟踪图表的一般区域中的 Points - 足够接近以至于它们可能满足 <3 接近度测试。例如：

std::unordered_multimap<Point, Point> areas;

Point p = { ...whatever... }; 

// keys for nearby points:
Point around[] = { { (p.x - 2) / 3 * 3, (p.y - 2) / 3 * 3 }, 
                   { (p.x + 2) / 3 * 3, (p.y - 2) / 3 * 3 },
                   { (p.x - 2) / 3 * 3, (p.y + 2) / 3 * 3 },
                   { (p.x + 2) / 3 * 3, (p.y + 2) / 3 * 3 } };

对于四个 around[] 条目中的每一个，在 multimap 中执行 find 以查看是否存在完全匹配或近似匹配：这减少了 13 table仅探测到 4 个。每个 multimap 键永远不会映射到超过 2 个条目，因为唯一的非近似冲突是在一个区域的对角处的两个 Points。

在我的例子中，如何重载 equal 方法以使不同的对象在 unordered_multimap 中具有相同的哈希码值

How can I overload equal method to make different objects have same hashcode value in unordered_multimap in my case

c++

hashcode

multimap