要素のコレクションを並べ替えるには、ある要素が他の要素よりも小さい場合を判断する並べ替え述語を提供する必要があります。この述語は、cppreference.Wait に従って、「等価クラスで厳密な合計順序付けを誘導する」必要があります。 P>
今後の C++ 宇宙船オペレーターは、3 者間比較を実装します。 06 の結果を返すことができる単一の関数です 、 12 と 22 しかし、これに関連する「強い等式」や「弱い順序付け」などの用語は、数学の知識がないと多少混乱します。
このシリーズでは、等号と順序付けの背後にある数学について説明し、比較演算子と宇宙船演算子を実装するための具体的なガイドラインを示します。
前の部分は非常に数学的な内容でしたが、必要でした:リレーションの順序付けに関する数学用語を紹介しました.これで、最終的にそれが C++ にどのように適用されるかについて話すことができます.
リレーションの順序付けのための C++ メカニズム
簡単にまとめると:2 つの要素がある場合、それらは等しいか、同等であるか、一方が他方よりも小さい/大きいか、または比較不可能である可能性があります。
数学では、この関係は、何らかの形式の 30 を実装できるバイナリ関係で指定されます。 または 47 の何らかの形式 .C++ には次のオプションがあります:
- 比較演算子
52をオーバーロードします 、67、79、82 - 名前付き述語を実装する (
98-returning) 対応する数学的関係を実装する関数 - 宇宙船オペレーター
102をオーバーロードします
次のパートで宇宙船演算子について詳しく説明するので、最初の 2 つのオプションだけに焦点を当てましょう。しない 順序関係が必要です。
順序付けされていない型
最初の部分の用語を覚えていれば、型は一連の値を定義します。しかし、一部の型では、この一連の値は明らかではありません。私は 119 を使用しました 例として、数学的な方法で実際に話すことはできません.そして、それができない場合、これは、平等であることの意味を本当に理解していないという大きな兆候です.
ここにも同じことが当てはまります:
ルール: 型の値がわからない場合は、順序関係を実装しないでください。
順序関係は本質的に数学的構造であるため、タイプの数学的表現を知る必要があります。違いについては、最初の部分で詳しく説明します。
結果: 型に同値関係がない場合は、順序関係を提供しないでください。
しかし、数学で自分のタイプについて話すことができるからといって、それを順序付けする必要があるわけではありません:
ルール: 実際に意味がある場合にのみ、型の順序付け関係を実装します .
たとえば、各メンバーを順番に比較するだけで、任意のタイプの順序付けを簡単に定義できます。これは、文字列の順序付けに似ているため、辞書式比較と呼ばれます。つまり、各文字を順番に比較します。
ただし、ほとんどのタイプではあまり意味がありません。
120 を検討してください :基本的には、実部と虚部の 2 つの浮動小数点型のペアです。したがって、最初に実部を比較し、それらが等しい場合は虚部を比較することで、全体的な順序付けを実装できます。
しかし、この順序付けは、複素数の数学的性質とはうまく調和しません。たとえば、任意の実数 135 に対して .But 142 .そして 152 161 未満です これは、残念ながらこのプロパティがないことを意味します。
したがって、174 はありません 184 で .
ただし、順序付けが必要な標準ライブラリの部分があります。198 202 を実行する必要があります ルックアップ、217 実際にソートする必要がありますが、 228 がありません 237 で 問題ありません:240 に入れる必要がある場合 、辞書式比較を記述し、それを比較述語として提供することもできます。実際には、注文に派手なプロパティがあるかどうかは関係ありません。合計である限り、より高速なルックアップが得られます。複素数のシーケンスは、通常、とにかく何かカスタムを念頭に置いています.
結果: 一部の (標準) ライブラリ コンテナーまたはアルゴリズムがそれを必要とするという理由だけで、型の一般的な順序関係を実装しないでください。代わりにカスタム述語をそれらに渡します。
悲しいことに、標準ライブラリ自体は別のアドバイスに従っているようです。多くの型には、オーバーロードされた演算子 250 があります。 、たとえば、すべてのコンテナはそのように辞書式比較を実装します.For 263 理にかなっていますが、277 の場合 ?私はそうは思いません:便利で便利かもしれませんが、あまり意味がありません.
私は個人的に次の経験則に従っています:
ガイドライン: ほとんどの型に対して比較演算子を提供しないでください。
疑わしい場合は、実行しないでください。
実際に順序付けが初めて必要になったときは、それを述語として実装し、一般的に提供するのに十分有用かどうかを検討してください。ほとんどの型では、実際には順序付けが必要になることはありません。
C++ での順序関係の設計
さて、順序付けを提供する必要があることが確実な型ができました:どのインターフェイスを提供する必要がありますか?比較演算子のオーバーロードまたは述語関数?
まず、オーバーロードされた比較演算子に関するいくつかの基本的なルールを理解しましょう:
ルール: 288 のいずれかをオーバーロードした場合 、 299 、 301 、 310 、他のすべてをオーバーロードして、それらが同じ順序を実装するようにする必要があります。
これは言うまでもありません。演算子は数学的な意味を持つ数学的構成要素であり、意味を表すことができる絵文字ではありません。
ルール: 比較演算子は全順序付けを実装する必要があります。
このルールに従わない場合、カスタム比較述語を指定せずに、set または sort アルゴリズムで誤って型を使用する可能性があります。コードはコンパイルされますが、アルゴリズムは完全な順序付けを想定しているため、機能しません。この間違いを防ぐために、比較は合計である必要があります。
ルール: 比較演算子は、等価性だけでなく、等価性を誘導する順序付けを実装する必要があります。
このルールはより微妙です:アルゴリズムは同等性と同等性を気にしません。どちらも機能します.ただし、 326 これは 339 と同等でなければなりません .そして、最初の投稿で述べたように、343 同等ではなく同等を意味する必要があります.So 356 同等性だけでなく、平等を誘導する必要があります。
これは次のことも意味します:
ルール: 型に比較演算子のオーバーロードがある場合は、等価演算もオーバーロードします。比較演算子によって生成される等価は、等価演算によって実装される等価と一致する必要があります。
360 を使用して合計注文を実装した場合 、あなたは同等性も定義しました。したがって、その事実をユーザーから隠しても意味がありません。そのため、379 をオーバーロードする必要があります。 と 387 その等価性をチェックします。繰り返しになりますが、両方の演算子で同じ等価性を実装する必要があることは言うまでもありません。
したがって、比較演算子は、一致する 393 を使用して、(厳密な) 全体の順序付けを実装する必要があります。 と 405 .しかし、タイプは複数の合計注文を持つことができます:
ルール: 比較演算子は、型の直感的で明白な合計順序を実装する必要があります。
存在しない場合は、比較演算子をオーバーロードしないでください。
これにより、非直感的な全順序付けとその他の順序付け関係の述語関数が残されます。しかし、415 同等または 425 同等ですか?
ルール: 436 を返す名前付き述語関数を記述して、事前注文または部分注文を実装します。 2 つの引数が以下の場合。
選択の余地はありません:443 で予約注文 / 部分注文を実装することはできません :同等性を推測することはできません。したがって、 451 を使用する必要があります .
ルール: 完全予約注文または厳密な弱い注文を実装する場合は、463 を返す名前付き比較関数を提供します。 最初の引数が 2 番目の引数より厳密に小さい場合 (つまり、厳密な弱い順序)。
同等性ではなく同等性を提供する完全な順序関係 (完全な先行順序、厳密な弱い順序) の場合、479 を実装できます。 または 481 バージョン。ただし、491 を実装する場合 比較を必要とするアルゴリズムの述語として関数を直接使用できます。
要約すると:
- 明らかな全順序付け:すべての比較演算子と等価演算をオーバーロードする
- あまり明白でない全順序付け:
504を実装する名前付き述語 - 総予約注文 / 厳密な弱い注文:
515を実装する名前付き述語 - 部分注文または予約注文:
525を実装する名前付き述語
C++ での順序関係の実装
前回の等価関係と同様に、オブジェクトを数学的構造に変換する必要があります。これは、オブジェクトの値について話し、値のセットに順序関係を実装することによって行われます。
そして、これは等価関数の実装のように行われます:顕著なプロパティを比較することで、オブジェクトの値を比較します。
最も簡単なケースは複合型で、必要なのは顕著なプロパティの辞書編集的な比較だけです:比較、比較で 548 を連鎖 .すべてのメンバーが合計注文を持っている場合、自動的に合計注文があることに注意してください。
たとえば、単純なペアを考えてみましょう:
template <typename T, typename U>
struct pair
{
T first;
U second;
};
等式は非常に簡単です:
template <typename T, typename U>
bool operator==(const pair<T, U>& lhs, const pair<T, U>& rhs)
{
return lhs.first == rhs.first && lhs.second == rhs.second;
}
ここでは比較の順序は重要ではありませんが、ショート サーキットのため、最も頻繁に異なるメンバーを最初に比較する必要があります。これは、551 などのジェネリック型には適用されません。
560 の場合 比較の順序は重要です。ユーザーにとってはそれほど重要ではありませんが、順序を変更すると型の順序が変更されるため、重大な変更になります。したがって、ペアの従来の順序では次のようになります。 /P>
template <typename T, typename U>
bool operator<(const pair<T, U>& lhs, const pair<T, U>& rhs)
{
if (lhs.first != rhs.first)
// sort by first member if they're not equal
return lhs.first < rhs.first;
else
// sort by second member
return lhs.second < rhs.second;
}
多くのメンバーがいる場合、これを手動で書くのは面倒です。トリックとして、 577 を使用することもできます 583 を作成する メンバーへの参照の場合、提供された 594 を使用します タプルの:
return std::tie(lhs.first, lhs.second) < std::tie(rhs.first, rhs.second);
同じタイプのメンバーがいる場合は、 608 を使用できます
単純な辞書式の比較が必要ない場合は、もう少し手作業が必要です。たとえば、613 を考えてみましょう。 624 の :637 の新しいソート順を作成します (空のオプション) は他のすべての 649 の前に来ます オブジェクト。
653 次のようになります:
template <typename T>
bool operator<(const optional<T>& lhs, const optional<T>& rhs)
{
if (!lhs)
// empty optional less than all non-empty
return !rhs.empty();
else if (!rhs)
// left hand side is never less than an empty optional
return false;
else
// otherwise compare the members
return lhs.value() < rhs.value();
}
しかし、一度 665 を取得したら 、他のものを実装するのは簡単です:
bool operator<=(const T& lhs, const T& rhs)
{
// (lhs ≤ rhs) iff (lhs < rhs or lhs == rhs)
// and (lhs == rhs) iff !(lhs < rhs) and !(rhs < lhs)
return !(rhs < lhs);
}
bool operator>(const T& lhs, const T& rhs)
{
// (lhs > rhs) iff !(lhs <= rhs) iff rhs < lhs
return rhs < lhs;
}
bool operator>=(const T& lhs, const T& rhs)
{
// (lhs >= rhs) iff (lhs > rhs or lhs == rhs),
// (lhs > rhs) iff (rhs < lhs)
// and (lhs == rhs) iff !(lhs < rhs) and !(rhs < lhs)
return !(lhs < rhs);
}
他の順序付けの述語関数の実装も同様です。非合計の順序付けでは、比較不可能な等価プロパティを正しく取得するためにもう少し考える必要がありますが、私が提供できる一般的なアドバイスはありません。ケースバイケースで解決する必要があります。場合に基づいて、注文が必要な公理を満たしていることを確認してください。
結論
比較演算子は、明らかな 等価性だけでなく、等価性を誘導する全体的な順序付け。他の順序付け関係については、673 を実装します。 名前付き述語関数としてのバージョン。
疑わしい場合は、比較演算子をオーバーロードしないでください。コンテナーまたはアルゴリズムで必要な場合は、手動で述語を使用してください。
宇宙船のオペレーターが到着すると、このアドバイスは少し変わることに注意してください。それについては、次のパートで説明します。