Custom Class std::map Weird Behavior

Question

I'm getting a weird behavior when searching for a key in a map with a custom class I created as keys.

It seems that it doesn't find the keys although they are present in the map.

Anyone knows the reason for this?

Code (can run it here):

#include <iostream> #include <map> using namespace std; typedef short int dimension; class Point { public: Point() : m_x(0), m_y(0) {} Point(const Point &other) : m_x(other.m_x), m_y(other.m_y) {}; Point(dimension x, dimension y) : m_x(x), m_y(y) {} bool operator<(const Point &other) const { if (m_x < other.m_x) return true; return (m_y < other.m_y); } private: dimension m_x; dimension m_y; }; int main() { map<Point, bool> points = {{Point(0, 2), true}, {Point(1, 1), true}, {Point(2, 4), true}}; cout << (points.find(((points.begin())->first)) == points.end()) << endl; cout << (points.find((next(points.begin()))->first) == points.end()) << endl; cout << (points.find((next(next(points.begin())))->first) == points.end()) << endl; cout << (points.find(Point(0, 2)) == points.end()) << endl; cout << (points.find(Point(1, 1)) == points.end()) << endl; cout << (points.find(Point(2, 4)) == points.end()) << endl; return 0; }

Output:

1 0 0 0 1 0

Your < is not a strict weak ordering; you have both {3,4} < {4,2} and {4,2} < {3,4}, and they can't both be ordered before the other — molbdnilo
– molbdnilo, Commented Nov 30, 2020 at 15:37
FWIW, when writing a comparator for yourself, use std::tie to wrap the members in a tuple so the code becomes return std::tie(lhs.mem1, lhs.mem2, ..., lhs.memN) op std::tie(rhs.mem1, rhs.mem2, ..., rhs.memN); — NathanOliver
– NathanOliver, Commented Nov 30, 2020 at 15:37

463035818_is_not_an_ai · Accepted Answer · 2020-11-30 15:48:31Z

Your operator< is flawed:

bool operator<(const Point &other) const { if (m_x < other.m_x) return true; return (m_y < other.m_y); }

For example

 {0, 3} < {1, 2} -> true

but

 {1, 2} < {0,3} -> true

The operator< must implement a strict weak ordering. You forgot to consider the case when (m_x > other.m_x) which should result in false.

A neat trick to avoid such problem is to use std::tie and make use of std::tuple::operator<:

bool operator<(const Point &other) const { return std::tie(m_x,m_y) < std::tie(other.m_x,other.m_y); }

Collectives™ on Stack Overflow

Custom Class std::map Weird Behavior

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related