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番目のラング (k>0 の場合)のすべての「アーム」にはk+1要素があります。
  3. (x,y)max(|x|, |y|)- 番目のラングにあります。

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内部で特殊化する代わりに、独自のfornamespace stdを定義する方が簡単です。これは、 で自動的に機能するからです。operator<Pointstd::less

比較を実装するために、別の C++11 機能を使用します。つまり、構造体forward_as_tupleを受け取り、Pointこれを に変換しstd::tuple<int, int>ます。std::tuple正しいことを行う が既にあるため(指定した順序でメンバーを辞書式に比較する)、最初に半径を使用し、2 番目に角度を使用し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,

注:これを 3 番目のリングに拡張する場合、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 に答える