CODEWITHSUNDEEP
c++stdstdmap
Uriya Harpeness
Uriya Harpeness

Reputation: 628

Custom Class std::map Weird Behavior

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

Upvotes: 0

Views: 75

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122133

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

Upvotes: 6

Related Questions