Why does defining a struct with an operand< function that isn't const break things if you use it as a key in a Map?

Question

I use a map and within that map, the type of the key is Coordinates:

struct Coordinates
{
    int x;
    int y;

    Coordinates() 
    {
        x = -1;
        y = -1;
    };
    Coordinates(int a, int b) : x(a), y(b) {};

    bool operator<(const Coordinates& otherCords) const
    {
        int thisSize;
        int otherSize;

        if (x >= y)
        {
            thisSize = x - y;
        }
        else
        {
            thisSize = y - x;
        }

        if (otherCords.x >= otherCords.y)
        {
            otherSize = otherCords.x - otherCords.y;
        }
        else
        {
            otherSize = otherCords.y - otherCords.x;
        }

        return thisSize < otherSize;
    }

};

Took my quite a while to realize my operand function wasn't being detected by the map because it wasn't const. Why is that so?

Answer 1

Short answer: because that's the requirement of the map class.

Longer answer: The keys of a map are const and cannot be modified (because this could break the sort order the map relies on). Since the keys are constant values, any comparison function used with them needs to be const.

Answer 2

It must be const since you're not allowed to change the value of the key while it's in the map. In order to change a key, you must extract the element and reinsert it with a new key.

A bigger problem is that your operator< does not fulfill the strict weak ordering requirement - and many coordinates are likely to get rejected when you try to enter them into the map because an equal coordinate already exists. According to your function:

{0,0} == {1,1} == {2,2} == {3,3} // all where std::abs(x-y) == 0 are equal
{0,1} == {1,0} == {1,2} == {2,1} // all where std::abs(x-y) == 1 are equal
{0,2} == {2,0} == {1,3} == {3,1} // all where std::abs(x-y) == 2 are equal
...and so on...

One remedy could be to change the comparison function to:

    bool operator<(const Coordinates& otherCords) const {
        if(x==otherCords.x) return y < otherCords.y;
        return x < otherCords.x;
    }

Or simpler:

#include <tuple>
...
    bool operator<(const Coordinates& otherCords) const {
        return std::tie(x,y) < std::tie(otherCords.x, otherCords.y);
    }