使用std::less创建绕原点的std::map

Question

介绍

你好！我正在编写一个在非平凡空间中运行的模拟系统。该系统占据了以原点为中心的一定数量的空间。当前，我正在实现一个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
        }
    }
}

这是我的第一个问题，我已经尽力遵守规则。如果我有什么做错了的地方，请给予支持，我会尽力整理好。感谢您的支持！

- user1684306

---

你需要一个函数，它接受一个X,Y对并将其转换为表示其在螺旋周围位置的序数。如果你的序列有间隔，那么没关系，但不能有重叠。所以我会先找到你的点所在的“环”（abs(x-center)和abs(y-center)中较大的那个），然后从该环内的每个环的面积作为基础值开始（类似于(ring-1)^2），然后加上你沿着当前环的序数（找出你在哪条边上以及你在其中的位置）。当你按照这个序数排序时，它们将按螺旋顺序排列。 - Dithermaster

Answer 1

让我们尝试解决这个等价问题：编写一个函数 f：（Z，Z） -> Z，其中 N 是整数集，使得如果您从原点开始以逆时针外螺旋形式编写数字，并且在（x，y）处，数字将是f（x，y）。

我们将使用以下观察结果：

1. 螺旋的第k圈的最后一个元素（k，-k）满足f（k，-k）=（2k + 1）^ 2-1。
2. 对于k>0，每个“臂”都有k + 1个元素。
3. （x，y）位于第 max（| x |，| y |）圈上。

使用上述方法，您可以根据哪个坐标定义了梯子来为f提出逐段描述。因此，您有一种计算f的常数时间方法。在功能上，您可以定义less((x1,y1),(x2,y2)) = less(f(x1,y1),f(x2,y2))。请保留html标签。

- Pradhan

Answer 2

这里提供了一个完整且可行的解决方案，使用了C++11的特性。

我为Point定义了radius()和angle()成员函数。 "半径"使用最大范数max(abs(x), abs(y))来给予等距离于原点的正方形环。对于极角，我使用[0, 2 pi]中的角度约定。标准库数学函数atan2在[-pi, +pi]范围内给出结果，因此我为负结果添加了2 pi。

与其在namespace std中专门化std::less，不如为Point定义自己的operator<，因为这将自动适用于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等）。

- TemplateRex

---

这绝对比代码的简洁性更不重要。我喜欢你的回答。它是一个简单而有效的答案，具有明确的解释和一个可以在浏览器上编译和运行的C++11实现！我非常感激。 - user1684306

很高兴能够帮助！ - TemplateRex

@sammy 不是的，请看http://en.wikipedia.org/wiki/Maximum_norm 一般来说，p-范数定义为norm_p(x) = (sum_i (x_i^p))^(1/p)。当p=2时，你得到传统的半径（勾股定理），当p=1时，曼哈顿“出租车”范数，当p=inifinity时，你得到一个正方形环作为半径。例如，参见http://en.wikipedia.org/wiki/Lp_space - TemplateRex

@sammy，你能给一个违反范数公设的例子吗？我通过用范数和角度定义<来区分具有相同"半径"的类型。 - TemplateRex

从OP的问题陈述中，我理解为这是一个正方形螺旋而不是圆形螺旋，并且OP没有表明其他。因此，使用我的最大范数，(4, 4) < (0, 5)。如果您想要一个圆形螺旋，确实使用传统半径，这些点将翻转其顺序，但代码的其余部分保持不变。 - TemplateRex

Answer 3

一个经常使用的解决方案是转换为极坐标。

您可以定义一个小于运算符，首先按到中心的距离排序，然后按角度排序。

- Sam

---

我喜欢它！我的第一个想法涉及到距离的平方，然后按象限划分 - 但我在象限内部的反射处遇到了碰撞。 - user1684306