[C++, OpenCV] std::set<std::pair<double, cv::Point>> - problem with insert

[peter55555]

Hi,
I'd like to create std::set<std::pair<double, cv::Point>>.
My requirements:

1) Sort ordering: first value (lhs.first < rhs.first).
2) Elements are treats as equal where first and second value of the pair are equal (lhs.first == rhs.first && lhs.second == rhs.second).

So I defined my set as:

std::set<std::pair<double, cv::Point>, QComparator> s;

where QComparator is:

struct QComparator
{
bool operator() (const std::pair<double, cv::Point>& lhs, const std::pair<double, cv::Point>& rhs) const
{
return lhs.first < rhs.first;
}
};

It works in some sense (elements are sorted and I can't insert twice the same element) but I don't understand why I cannot do this:

Q.insert(std::make_pair(10, cv::Point(11, 11));
Q.insert(std::make_pair(10, cv::Point(10, 10)));

It treats this two elements as equal and I cannot add the second one. :(

[MiiNiPaa]

It treats this two elements as equal

Not equal, equivalent.
Elements a and b are equivalent if a < b == false and b < a == false .
Set by definition disallows equivalent elements from being stored.

Just ask yourself: which one of those two pairs should be first? And how your program will know this.

You might consider adding second part of pair to be used in comparison (like pair does by default) or use multiset instead

[peter55555]

Is it possible to write proper comparator for this task? I have no idea how to do that...

[MiiNiPaa]

Is it possible to write proper comparator for this task?

Yes. Firstly you need to define how two points are going to be ordered (in other words in which situations one point is less than other) and think about possible collisions.

Simpliest way is to threat pont as pair of coords:

//I do not remember how to get coords from cv::Point, so it is something that you have to look yourself
struct QComparator
{
    bool operator() (const std::pair<double, cv::Point>& lhs, const std::pair<double, cv::Point>& rhs) const
    {
        if (lhs.first != rhs.first)
            return lhs.first < rhs.first;
        else if (lhs.second./*getX*/ != rhs.second./*getX*/)
            return lhs.second./*getX*/ < rhs.second./*getX*/;
        else 
            return lhs.second./*getY*/ < rhs.second./*getY*/;
    }
};

//Or
struct QComparator
{
    bool operator() (const std::pair<double, cv::Point>& lhs, const std::pair<double, cv::Point>& rhs) const
    {
        return std::tie(lhs.first, lhs.second./*getX*/, lhs.second./*getY*/) <
               std::tie(rhs.first, rhs.second./*getX*/, rhs.second./*getY*/) ;
    }
};

[peter55555]

Thank you very much. I used version with std::tie - it works great!

Thanks a lot. You've helped me a lot. :)

Best regards
Peter