演算子<と厳密な弱い順序付け

StackOverflow https://stackoverflow.com/questions/979759

  •  13-09-2019
  •  | 
  •  

質問

定義方法 operator< n タプル (たとえば 3 タプル) で次の条件を満たすようにします。 厳密な弱い順序付け コンセプト ？ブーストライブラリに正しく定義されたタプルクラスがあることはわかっています operator< しかし、何らかの理由で使用できません。

役に立ちましたか？

解決 

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

これは、ほとんどのsiginificantとA3最下位であることa1で要素を順序付け。

これは、例えばまた、無限の可能性が継続することができます[I] <[I] <[I + 1] / [I + 1]の比較を反復、Tのベクトルに適用します。

「と等しい場合、比較しながら、スキップ」アルゴリズムの代替表現は次のようになり 
while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];
比較が高価である場合は、

もちろん、あなたは、比較結果をキャッシュする場合があります。

<時間>

[編集]削除間違ったコード

<時間>

[編集]ちょうどoperator<以上が利用可能な場合、私はパターンを使用する傾向がある。

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

他のヒント

厳しい弱い順序付け

この2つのオブジェクト間の関係を定義するための数学的な用語である。
その定義は次のとおりです。

  双方のF（x、y）とF（Y、X）がfalseである場合は、

2つのオブジェクトxおよびyは等価です。オブジェクトが（irreflexivity不変量により）常にそのものと等価であることに注意してください。

Cの面では++これは、あなたが指定したタイプの2つのオブジェクトを持っている場合はオペレータ<と比較したとき、あなたは次の値を返す必要がありますを意味します。

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

どのように/少ない同等のものを定義することはあなたのオブジェクトのタイプに完全に依存している。

正式な定義：
厳格な弱い発注する

コンピュータサイエンス：
厳格な弱い注文する

どのように事業者に関する：
コンパレータの

...非常に古い質問に対する新しい回答ですが、既存の回答には C++11 の簡単な解決策が欠けています...

C++11 ソリューション

C++11 以降では、 std::tuple<T...>, 、データを保存するために使用できます。 tuple一致するものがあります operator< これは最初に左端の要素を比較し、結果が明らかになるまでタプルに沿って動作します。を提供するのに適しています。 厳密な弱い順序付け 例によって期待されます std::set そして std::map.

他の変数にデータがある場合 (例:のフィールド struct)、使用することもできます std::tie() タプルを作成します 参考文献の, 、その後、別のそのようなタプルと比較できます。そうすれば書きやすいですよ operator< ユーザー定義の特定のメンバーデータフィールド用 class/struct タイプ：

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

あなたは、単にすでに適切）（<演算子を持っています3要素ベクトルを、使用することができます 定義されました。これは、あなたが何かをすることなく、N-要素にまで及ぶという利点があります。

基本的な流れは、の線に沿ってする必要があります：K番目の要素が異なる場合は、の、小さいそれ以外でリターンはの次の要素にアクセスしてください。次のコードは、を想定していないのブーストタプルがそうでなければ、そもそも問題を抱えているget<N>(tuple)を使用していないだろうしています。

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

たとえブースト版が使えなくても、コードにニックネームをつけることはできるはずです。これを std::pair から抜粋しました。3 タプルも似たものになると思います。

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

編集：何人かの人が指摘したように、標準ライブラリからコードを盗んでコードで使用する場合は、先頭にアンダースコアが付いている名前は予約されているため、名前を変更する必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top