Сохранение координат отсортировано

Question

У меня есть некоторые координаты (x, y), и мне нужно, чтобы эти координаты были отсортированы и сохранять их отсортированными.После того, как я сортирую их, каждая координата меняется с (x, y) на (x + 1, y) или (x-1, y) или (x, y-1) или (x, y + 1), поэтому координатыбольше не сортируется.

Есть ли лучший способ решения этой проблемы, кроме того, сортировка координат, изменение координат, повторная сортировка координат, изменение координат, повторная сортировка координат на основе условия, что каждая координата изменяется с +-1

Answer 1

Вы можете поддерживать отсортированный порядок при обновлении координаты, перемещая координату в правильное место после обновления.

Если вы выполняете (x+1, y) или (x, y+1), тогда координата будет где-то впередиего текущей позиции в векторе.Если вы делаете (x-1, y) или (x, y-1), то координата будет где-то позади его текущей позиции в векторе.

(Существует также вероятность того, что координате не нужно менять позицию, если она все ещеисправить по отношению к другим элементам в векторе).

Используя это, вы можете искать впереди (или позади) позицию, в которой должна идти обновленная координата.При поиске вы можете скопировать элементы назад (или вперед), чтобы закрыть зазор, оставленный вашим текущим элементом.

|   a   |   b   |   c   |   d   |
| {1,1} | {1,2} | {2,0} | {2,2} |

В приведенном выше примере рассмотрим, что мы обновляем c до {1,0},Мы движемся назад, проверяя c < b, что верно, поэтому мы перетасовываем b вперед:

|   a   |       |   b   |   d   |
| {1,1} |       | {1,2} | {2,2} |

Мы снова движемся назад, проверяя c < a, что также верно, поэтому мы перемешиваем a forward.

|       |   a   |   b   |   d   |
|       | {1,1} | {1,2} | {2,2} |

В этот момент мы достигли начала вектора, поэтому мы знаем, что c должен перейти в эту позицию.

|   c   |   a   |   b   |   d   |
| {1,0} | {1,1} | {1,2} | {2,2} |

Другой терминальный случайкогда c больше не меньше проверяемого элемента.

Это работает аналогично в прямом направлении.

Некоторый код, демонстрирующий эту идею:

#include <algorithm>
#include <ctime>
#include <iostream>
#include <random>
#include <vector>

struct Point {
    int x;
    int y;

    void Adjust(int i) {
        switch (i) {
            case 0: x++; return;
            case 1: y++; return;
            case 2: x--; return;
            case 3: y--; return;
        }
    }

    bool operator<(const Point & rhs) {
        if (x == rhs.x)
            return y < rhs.y;

        return x < rhs.x;
    }

    bool operator>(const Point & rhs) {
        if (x == rhs.x)
            return y > rhs.y;

        return x > rhs.x;
    }
};

int main() {
    std::vector<Point> points;

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j)
            points.push_back({i,j});
    }

    std::sort(std::begin(points), std::end(points));

    std::default_random_engine rng{std::time(nullptr)};
    std::uniform_int_distribution<int> distrib{0, 3};

    for (int i = 0; i < 10000; ++i) {
        for (auto iter = std::begin(points); iter != std::end(points); ++iter) {
            auto p = *iter;
            int adjustment = distrib(rng);

            p.Adjust(adjustment);

            auto current = iter;

            if (adjustment < 2) {
                auto next = std::next(current);

                while (next != std::end(points) && p > *next) {
                    *current = *next;
                    current = next;
                    next = std::next(current);
                }

                *current = p;
            }
            else if (current != std::begin(points)) {
                auto prev = std::prev(current);

                while (p < *prev) {
                    *current = *prev;
                    current = prev;

                    if (current != std::begin(points))
                        prev = std::prev(current);
                    else
                        break;
                }

                *current = p;
            }
        }
    }

    for (auto && p : points)
        std::cout << "{" << p.x << "," << p.y << "}\n";

    std::cout << "is_sorted = "
        << std::is_sorted(std::begin(points), std::end(points))
        << std::endl;

    return 0;
}

Пример в реальном времени

Отказ от ответственности: я не измерял производительность этого решения.Это может быть медленнее, чем просто сортировка вектора после всех обновлений из-за тасования, которое происходит при каждом обновлении элемента.

Answer 2

A std::set справится со всем этим для вас.В частности, содержимое по своей сути сортируется функцией operator< членов набора, поэтому при вставке новых элементов вам не нужно выполнять какую-либо сортировку самостоятельно.Сложность вставки составляет O (log (N)).

Что касается правильной сортировки координат, вы можете использовать тот факт, что std::pair определяет operator< примерно так:

If lhs.first<rhs.first, returns true. Otherwise, if rhs.first<lhs.first, returns false. Otherwise, if lhs.second<rhs.second, returns true. Otherwise, returns false.

- это то, что вы хотите сказать.

Итак, подведя итог, вы можете сделать:

#include <utility>
#include <set>

using coordinate = std::pair<int, int>;
std::set<coordinate> stored_coordinates;

где первый член std::pair, представляющий coordinate, равен x, а второй - y.

Наконец, если вы хотите связать элемент данных с каждой координатой, используйте вместо этого map, с std::pair как ключ.