3

介绍

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

这是我的第一个问题，我已经尝试遵守规则。如果我做错了什么，请支持，我会尽我所能把事情整理好。谢谢你的支持！

4

3 回答 3

1

让我们试着解决这个等价的问题：写一个函数f : (Z, Z) -> Z，其中N是整数集，这样如果你从0原点开始写数字，然后逆时针向外螺旋，则在 处的数字(x,y)将是f(x,y)。

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

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

f使用上述内容，您可以根据哪个坐标定义梯级来提出分段描述。因此，您有一个恒定时间方法来计算f. 在功能上，您可以定义less( (x1,y1), (x2,y2) ) = less(f(x1,y1), f(x2,y2)).

于 2014-07-05T03:45:33.580 回答
0

这是使用 C++11 功能的完整且有效的解决方案。

我为. radius()_ “半径”使用最大范数使方环与原点的距离相等。对于极角，我使用 中的角度约定。标准库数学函数给出了范围内的结果，所以我添加了否定结果。angle()Point max(abs(x), abs(y))[0, 2 pi]atan2[-pi, +pi]2 pi

与其在std::less内部专门化namespace std，不如定义自己的operator<for更容易，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 等）。

于 2014-07-05T15:16:37.077 回答
0

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

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

于 2014-07-05T06:02:30.353 回答