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

Question

I have written a map like this:

unordered_multimap<Point, int, StrHash, StrCompare> map

StrHash() is to create hashcode and StrCompare() is to solve the hashcode collision. but I want to do something as follow:

A and B have different hashcode value,but A equal to B, then run the StrCompare() method. how can I do that,just like Point A(220,119) and Point B(220,220) have different hashcode. Can I overload hashcode equal method to make A == B? In my case, I want to get the Points,which compare with each others (abs(a.x - b.x) + abs(a.y - b.y) < 3). just like, Point(220,220)(220,119)(220,118)(220,220) my code is as follow:

#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

Got to say this as it's so much easier if your error tolerance will allow it: you could just round your values to the nearest multiple of 2 or 3.

---

MarkB's suggestion of using a vector is excellent... just listing some others for the intellectual interest.

---

It is possible to get the functionality you want using an unordered_map, but not very cleanly: you'll need the map-using code to orchestrate the logic for approximate equality. First, the equality function must check for actual equality:

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

Then, you'll need a support function like this:

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

Then, you can use the returned iterator to see if Point you're thinking of inserting will be a duplicate, as well as for lookup, eraseing etc..

Note that the performance will not be great. Each approx_find is effectively searching around the Point argument as follows:

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

All up, that's 13 lookups - scattered more-or-less randomly around the hash table's buckets so not particularly cache friendly - instead of the usual 1.

---

A completely different option is to use an unordered_multimap to keep track of the Points in a general area of the graph - close enough that they might satisfy the <3 proximity test. For example:

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

For each of the four around[] entries, do a find in the multimap to see if there's an exact or approximate match: that reduces the 13 table probes to just 4. Each multimap key won't ever map to more than 2 entries, as the only non-approximate-clash would be for two Points at opposite corners of an area.

Answer 2

This isn't how hash maps/unordered_map work. By definition if the hashes are unequal the objects are unequal. Not only that, but your "equality" operator allows things like A(220,119), B(220,220), C(220, 222) where A == B and B == C but A != C. I can't see any way to accomplish what you ask in this question, but is there perhaps a real problem you're trying to solve?

Based on your comments, it sounds like you want std::vector instead of std::unordered_map. Then you just use std::find to find the element you care about instead of going through the indirection of having a no-op hash.