54

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

4

6 に答える 6

63

厳密な弱順序

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

f（x、y）とf（y、x）の両方が偽の場合、2つのオブジェクトxとyは同等です。オブジェクトは常に（非反射性不変量によって）それ自体と同等であることに注意してください。

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

同等/以下をどのように定義するかは、オブジェクトのタイプに完全に依存します。

正式な定義：
厳密な弱順序

コンピュータサイエンス：
厳密な弱順序

オペレーターとの関係：
コンパレータ

補足として、厳密な弱順序を手動で実装できます。std::tupleしかし、私たちはあなたのためにそれを実装したを使用してそれを簡単に行うことができます。オブジェクトをコピーせずにタプルを作成するだけです。

struct S
{
     ThingA   a;
     ThingB   b;
};
bool operator<(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}

注：これは、厳密な弱順序thingAをすでに実装していることを前提としています。thingB

同じ方法で平等を実装することもできます。

bool operator==(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b);
}

繰り返しになりますが、これは、平等thingAをすでに実装していることを前提としています。thingB

于 2009-06-11T14:05:00.930 に答える
45 
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

これにより、a1 が最も重要で a3 が最も重要ではないという順序で要素が並べられます。

これは無限に続けることができます。たとえば、a[i] < a[i+1] / a[i+1] < a[i] の比較を反復して、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;

...
于 2009-06-11T07:24:39.787 に答える
33

...非常に古い質問に対する新しい回答ですが、既存の回答には C++11 からの簡単な解決策がありません...

C++11 ソリューション

C++11 以降ではstd::tuple<T...>、データの保存に使用できる が提供されます。 s には、最初に最も左の要素を比較tupleするマッチングがあり、結果が明確になるまでタプルに沿って機能します。これは、たとえばandによって期待される厳密な弱い順序付けoperator<を提供するのに適しています。std::setstd::map

他の変数 (例: a のフィールドstruct) にデータがある場合は、 を使用してreferencestd::tie()のタプルを作成することもできます。これを別のそのようなタプルと比較することができます。これにより、ユーザー定義の/型で特定のメンバー データ フィールドを簡単に記述できます。operator<classstruct

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_);
}
于 2016-05-17T06:54:55.343 に答える
6

すでにoperator<（）が適切に定義されている3要素のベクトルを使用するだけで済みます。これには、何もしなくてもN要素に拡張できるという利点があります。

于 2009-06-11T07:31:55.987 に答える
5

基本的な流れは、次のようになります。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;
于 2009-06-11T08:33:33.147 に答える
2

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

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

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

于 2009-06-11T08:10:27.860 に答える