std::map with cv::Point as key

Question

I need to create std::map<cv::Point, double>. cv::Point is a type of a point from OpenCV library. It has fields like: x and y.

cv::Point does not have < operator of course. Do you have any idea how to define it to have optimal access to element in std::map?

In other words. I have for example 20000 points. I need quite fast access to every point.

For example:

std::map<cv::Point, double> myMap;

Point p(10, 234);
int value = 777;
myMap[p] = value; // I need this operation quite fast so I decided to use std::map

But cv::Point does not have < operator. I can prepare < operator like (it comparing for example only x coordinate):

bool operator<(const cv::Point a, const cv::Point b)
{
    return a.x < a.x;
}

But I guess it is not good operator. Many points has the same value of x.

How to prepare efficient operator in this case?

The key needs to be copyable and assignable: http://stackoverflow.com/questions/6573225/what-requirements-must-stdmap-key-classes-meet-to-be-valid-keys — EdChum, Oct 21 '14 at 09:35
I can't find any type called `cv::Point` in the documentation. I only see `Point_`, which is a template. — Jan Hudec, Oct 21 '14 at 09:37
Are the coordinates integral or floating point? If the later, are you aware that rounding errors may render numbers you expected to be equal not be? — Jan Hudec, Oct 21 '14 at 09:38
@JanHudec does the OP not need to wrap a `CV::Point` and implement the `<` operator or define a functor in order to use it as a key? — EdChum, Oct 21 '14 at 09:39
@EdChum: No, they don't need to **wrap** anything! They need to define `operator<` _for_ the existing type. — Jan Hudec, Oct 21 '14 at 09:39
@Jan Hudec: There are typedefs: typedef Point_ Point2i; typedef Point2i Point; — peter55555, Oct 21 '14 at 09:39
@Jan Hudec: I don't understand. I have pasted typedefs from OpenCV library (core.hpp file) and I'd like to use Point in my map as a key (in other words: I'd like to use Point_). — peter55555, Oct 21 '14 at 09:44
Why this question is marked as duplicated??? I can write comparator but I don't know how do it the best. — peter55555, Oct 21 '14 at 09:48
@peter55555 Then maybe you should clarify what exactly you are having problems with. — juanchopanza, Oct 21 '14 at 09:49
Do you have any use for the fact that `std::map` is ordered? Would [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map) (or it's boost precursor) be more suitable? — Jan Hudec, Oct 21 '14 at 10:21
@Jan Hudec: I haven't thought about it. You're right. I've forgotten about std::unordered_map. Thanks a lot. :) — peter55555, Oct 21 '14 at 10:25

score 12 · Accepted Answer · answered Oct 21 '14 at 11:16

12

According to this documentation, cv::Point represents a two dimensional datapoint. For this, you can define your operator < via standard lexicographic ordering:

bool operator<(cv::Point const& a, cv::Point const& b)
{
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}

EDIT: As you considered using an unordered_map: although it might be more appropriate here, it is a bit more complicated to implement as you have to combine the two hash-values of x and y. For this you can use boost::hash_combine or figure out something reasonable on your own, but you see it becomes more complicated.

answered Oct 21 '14 at 11:16

davidhigh

14,652
2
44
75

Thanks a lot. I think about `unordered_map`. Is is very hard to write hash function. :( My points are points from rectangle (all points of rectangle). I decided to use std::map. – peter55555 Oct 21 '14 at 11:44
@peter55555: It is **trivial** to write has function. Something like `x ^ y` will do just fine! The only problem is that `std::hash` is a `struct` template that you have to specialize. The boost version has default implementation that calls unqualified `hash_value` _function_, which works more like the operator. I don't know why that was not included in standard. – Jan Hudec Oct 21 '14 at 12:48
@Jan Hudec: right, one will surely find something which is about to work. However, I don't want to determine which binary function of two `size_t` is about to do fair/good/best ... thats the kind of decision one usually tries to avoid by using the standard library. So I agree: either `hash_combine` should be in the standard, or even better specializations of `std::hash` for `std::array` and `std::tuple`. – davidhigh Oct 21 '14 at 13:37

std::map with cv::Point as key

1 Answers1