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

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

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

  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.