1

Предположим у меня есть структура:

struct Point {
    int x, y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

Я хочу создать словарь

map<Point, vector<Point>> adj;

Что для этого надо сделать? Это будет использоваться в спортивном программировании, поэтому я бы хотел узнать самую простую реализацию

2
  • 1
    Главное - написать и передать соответствующий компаратор, который сравнивает структуры Point. Можете просто дописать оператор < для Point. Только чтобы семантически был верным...
    – Harry
    10 мар 2021 в 8:00

1 ответ 1

4

Для того, что бы 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;
}
4
  • 1
    Пофиксил. Теперь и по углу сравниваем
    – KoVadim
    10 мар 2021 в 8:52
  • о, и тут минусаторы подбежали.
    – KoVadim
    10 мар 2021 в 9:33
  • 1
    уже не вернет..
    – KoVadim
    10 мар 2021 в 9:55
  • А ещё и комментарии подтерли... Ну как так. И теперь мои комментарии выглядят немного странно.
    – KoVadim
    10 мар 2021 в 10:53

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.