Использование 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
}
}
}
Это мой первый вопрос, и я пытался следовать правилам. Если я сделал что-то не так, пожалуйста, поддержите меня, и я сделаю все возможное, чтобы навести порядок. Спасибо за вашу поддержку!
Решение
Вот полное и рабочее решение с использованием функций 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 и т. Д.).
Другие решения
Давайте попробуем решить эту эквивалентную проблему: написать функцию 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)),
Часто используемым решением является преобразование в полярные координаты.
Вы можете определить менее оператора для заказа сначала по расстоянию до центра, а затем по углу.