2

キーにが付いたSTLマップを使用してstructいます。マップの定義は次のとおりです。 std::map<Coord2<uint8_t>, MapTile> tile_;

の定義struct：

template <typename T>
struct Coord2
{
    T x;
    T y;

    bool operator<(const Coord2<T> &coord) const { return (x < coord.x || y < coord.y); }
    bool operator>(const Coord2<T> &coord) const { return (x > coord.x || y > coord.y); }
}

比較のため、マップで問題が発生しますか？

4

3 に答える 3

14

これoperator<は、C++標準ライブラリの連想コンテナでの使用には適していません。

コンパレータは厳密な弱順序を提供する必要がありますが、これは提供されません。その不整合を示す次のオペランドを検討してください。

a = { x = 1, y = 0 }
b = { x = 0, y = 1 }

これらの入力を考えるとa < b == true、、、b < a == trueしかしb != a。

このタイプの正しい比較は次のようになります。

if (x < coord.x)
    return true;

if (coord.x < x)
    return false;

return y < coord.y;

（この正しいコードをよりコンパクトな方法で書くことは確かに可能ですが、誤って実装された厳密な弱い順序によって引き起こされる十分なエラーをデバッグしたので、それが正しいことを明確にするために、比較で非常に明示することを強くお勧めします。この実装では、値が等しいy場合にのみ値を比較することは非常に明白xです。これが私たちの望みです。）

于 2012-06-07T16:42:55.640 に答える
13

2つの値の場合、Jamesの答えは理想的です。メンバーが増えると複雑になるため、複数の値に対して厳密な弱順序を実装する簡単な方法は、それらの値のタプルを作成し、タプルを比較することです。

 return boost::tie(x, y, z) < boost::tie(coord.x, coord.y, coord.z);

それが機能するために必要なのは、各メンバーがLessThanComparableになることです。次に、各式#include <boost/tuple/tuple_comparison.hpp>に同じ順序でメンバーをリストします。tie

C ++ 11では、代わりに#include <tuple>使用できstd::tieます。

タプルの比較は辞書式比較を行うように定義されているため、最初の要素が比較され、結果がtrueの場合は比較が完了し、trueが返されます。それ以外の場合は、要素の各ペアについて同じ方法で次の要素が比較されます。これにより、各要素タイプに正しく定義されている限り、正しい厳密な弱順序が保証されoperator<ます。

于 2012-06-07T16:54:09.250 に答える
2

最初のコメント：とにかく使用するだけなのでoperator>、は必要ありません。std::mapoperator<

ただし、厳密な弱順序を定義していないため、キーoperator<には適していません。std::map実際、推移性と反対称の両方に違反するため、厳密な半順序を実装していません。次の定義を検討してください。

coord p = { 2, 2 };
coord q = { 0, 4 };
coord r = { 1, 1 };

もp < q返さtrueれません、は返されますが2 < 4、q < r返さtrueれます。したがって、推移性が侵害されます。0 < 1p < rfalse

p < qさらに、 trueを返すだけでなく、もq < p返します0 < 2。言い換えれば、あなたのオペレーターによれば、とのそれぞれは他のものよりも小さいpとq見なされます。

于 2012-06-07T16:53:14.153 に答える