Для того, что бы map работал, нужно что бы ключи можно было сравнивать (так он устроен внутри). Для сложных структур бывает сложно написать корректный оператор сравнения. Главное, что бы обеспечить вот такое условие
- если a < b истинно, то b < a ложно
- если ложно a<b и b<a, то a==b.
Я знаю три способа написать такой оператор
Простой и примитивный:
bool operator<(const Point& a, const Point& b) {
if (a.x < b.x) return true;
if (a.x > b.x) return false;
return (a.y < b.y);
}
У этого способа есть одна модификация, которая делает код проще (но не факт, что быстрее, но clang генерирует очень хороший код, не хуже предыдущего)
bool operator<(const Point& a, const Point& b) {
return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}
У этого способа просто громадный плюс - его легко написать и сложно ошибиться. Также, если в структуре будет не две переменных, а десяток, то все равно легко справится.
Второй - сравниваем по длине вектора. А если длины одинаковые - сравниваем по углу.
bool operator<(const Point& a, const Point& b) {
long long a1 = a.x*a.x + a.y*a.y;
long long b1 = b.x*b.x + b.y*b.y;
if (a1 < b1) return true;
if (a1 > b1) return false;
return std::atan2(a.x,a.y) < std::atan2(b.x,b.y);
}
и третий, для спортивного программирования - так как тут два int (32 бита), складываем их в один 64битный лонг и сравниваем. Специалисты могут завернуть исходную структуру в union и закрыв глаза на UB, сделать код проще. Но ещё раз - это только для очень грязного программирования!!!
bool operator<(const Point& a, const Point& b) {
return (((long long)a.x<<32)+a.y) < (((long long)b.x << 32) + b.y);
}
Ну и хорошо сразу определить оператор равенства. Он точно пригодится.
bool operator==(const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}
Point
. Можете просто дописать оператор<
дляPoint
. Только чтобы семантически был верным...