Использование std :: less для создания std :: map Обтекание источника

Question

Использование std :: less для создания std :: map Обтекание источника

Здравствуйте! Я пишу симулятор, который работает в нетривиальном пространстве. Эта система занимает неопределенное количество пространства вокруг центрированного начала. Прямо сейчас я реализую класс точек xy ‘Pos’, чтобы соединить мои координаты и действовать как ключ для моих контейнеров (содержащих конечные блоки данных). Я бы хотел, чтобы данные вокруг источника были пространственно согласованными в памяти.

Моя цель для этого вопроса — написать специализацию для std :: less, чтобы, если (интегральные) позиции были вставлены в карту, они были бы упорядочены в соответствии с порядком намотки против часовой стрелки.

Я представляю, что клетки:

4 3 2
5 0 1
6 7 8 9

станет

0, 1, 2, 3, ….

Как мне сосредоточиться на написании std :: less, чтобы я мог обернуть мои точки вокруг, как это? Как я могу понять, как следует решение строгий слабый порядок и избегает других подводных камней?
Наконец, как бы вы лучше всего подошли или написали эту функцию с помощью инструментов, доступных в C ++ 11?

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

Я учился, осуществляя наивные попытки, но я считаю, что для меня было бы лучше решить это с помощью обсуждения и здравого объяснения, чем удачи.

Вот немного контекста.

struct Pos
{
short x;
short y;
Pos(short x, short y);
Pos(const Pos& p);
void operator=(const Pos& p);
~Pos() = default;
};
namespace std {
template<> struct less<Pos> {
bool operator()(const Pos& p1, const Pos& p2) const {
//Implementation
}
}
}

Это мой первый вопрос, и я пытался следовать правилам. Если я сделал что-то не так, пожалуйста, поддержите меня, и я сделаю все возможное, чтобы навести порядок. Спасибо за вашу поддержку!

3

c++c++11 cartesian-coordinates stdmap

Решение

Другие решения

Давайте попробуем решить эту эквивалентную проблему: написать функцию f : (Z, Z) -> Z, где N это набор целых чисел, так что если вы начали писать числа из 0 начиная с начала координат и направляясь по спирали наружу против часовой стрелки, число в (x,y) было бы f(x,y),

Мы будем использовать следующие наблюдения:

Последний элемент kая ступенька спирали, (k, -k) удовлетворяет f(k, -k) = (2k+1)^2 - 1,
Каждая «рука» k-я ступенька (для k> 0) имеет k+1 элементы.
(x,y) лежит на max(|x|, |y|)-я ступенька

Используя вышесказанное, вы можете придумать пошаговое описание f в зависимости от того, какая координата определяет ступеньку. Таким образом, у вас есть метод постоянного времени для расчета f, Функционально вы можете определить less( (x1,y1), (x2,y2) ) = less(f(x1,y1), f(x2,y2)),

2

Часто используемым решением является преобразование в полярные координаты.

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

1

Источник

Accepted Answer

Вот полное и рабочее решение с использованием функций C ++ 11.

Я определяю radius() а также angle() функции-члены для Point, «Радиус» использует максимальная норма max(abs(x), abs(y)) чтобы дать квадратным кольцам равное расстояние до начала координат. Для полярного угла я использую соглашение углов в [0, 2 pi], Математическая функция стандартной библиотеки atan2 дает результаты в [-pi, +pi] диапазон, поэтому я добавляю 2 pi за отрицательные результаты.

Вместо того, чтобы специализироваться std::less внутри namespace stdпроще определить свой operator< за Point потому что это будет автоматически работать с std::less,

Для осуществления сравнения я использую другое средство C ++ 11, а именно forward_as_tuple который занимает Point структурировать и преобразует это в std::tuple<int, int>, Так как std::tuple уже есть operator< что делает правильно (лексикографическое сравнение его членов в порядке, который вы предоставили), сравнение между Point теперь выполняется с использованием первого радиуса и второго угла.

Код следует ниже (и который печатает точки в правильном порядке).

#include <cmath>        // abs, atan, atan2, max
#include <iostream>     // cout
#include <map>          // map
#include <tuple>        // forward_as_tuple

struct Point
{
int x, y;

int radius() const
{
// block-wise radius, use Pythagoras for ring-wise radius
return std::max(std::abs(x), std::abs(y));
}

double angle() const
{
// result of atan2 in [-pi, +pi]
auto a = std::atan2(y, x);

// we want result in [0, 2 pi]
if (a < 0)
a += 8 * std::atan(1); // add 2 pi
return a;
}

friend bool operator<(Point const& L, Point const& R)
{
// delegate to operator< of std::tuple
return
std::forward_as_tuple(L.radius(), L.angle()) <
std::forward_as_tuple(R.radius(), R.angle())
;
}

friend std::ostream& operator<<(std::ostream& os, Point const& p)
{
return os << "{" << p.x << ", " << p.y << "}";
}
};

int main()
{
auto point_map = std::map<Point, int> {
{{-1, 1}, 4}, {{ 0, 1}, 3}, {{ 1, 1}, 2},
{{-1, 0}, 5}, {{ 0, 0}, 0}, {{ 1, 0}, 1},
{{-1,-1}, 6}, {{ 0,-1}, 7}, {{ 1,-1}, 8}
};

for (auto&& elem : point_map)
std::cout << elem.second << ",";
std::cout << "\n";
}

Живой пример что печатает

0,1,2,3,4,5,6,7,8,

НОТА: Если вы продлите это до третьего кольца, 9 не будет смежным с 8, вместо этого вы получите немного другую спираль

15 14 13 12 11
16  4  3  2 10
17  5  0  1  9
18  6  7  8 24
19 20 21 22 23

Причина в том, что угол 0 будет первым элементом нового кольца. Вы можете настроить это, но код для angle() быстро станет очень грязным (зависимым от кольца среди других). С другой стороны, числа от начала отсчета справа являются нечетными квадратами таким образом (1, 9, 25 и т. Д.).

1