比較の背後にある数学 #4:3 者間比較

要素のコレクションを並べ替えるには、ある要素が他の要素よりも小さい場合を判断する並べ替え述語を提供する必要があります。この述語は、cppreference.Wait に従って、「等価クラスで厳密な合計順序付けを誘導する」必要があります。 P>

今後の C++ 宇宙船オペレーターは、3 者間比較を実装します。 < の結果を返すことができる単一の関数です、 == と > しかし、これに関連する「強い等式」や「弱い順序付け」などの用語は、数学の知識がないと多少混乱します。

このシリーズでは、等号と順序付けの背後にある数学について説明し、比較演算子と宇宙船演算子を実装するための具体的なガイドラインを示します。

同等性と順序関係の両方について説明したので、最後に宇宙船演算子と 3 者間比較について説明します。

注: <=> の C++ 言語規則この投稿を書いてから変更されました。現在のルールについては、https://jonathanmueller.dev/talk/cppcon2019/ を参照してください。このブログ投稿は古くなっています。

三元比較

2 番目の部分で説明したように、2 つの要素が次の順序関係のいずれかにある可能性があります。

どちらも同じです。
どちらも同等です。
一方は他方より厳密に小さい/大きい
比類のないものです。

しかし、数学的には関係は単なる集合であり、ブール値の結果しか得られないことを意味します。そのため、数学者は 1 つの関係を選択する必要があり、その結果 ≤ の背後にある理論が生まれました。および <

しかし、3 者間比較は、1 回のクエリで関係全体が得られる関数です。伝統的に strcmp() はそのような関数です。2 つの文字列が与えられると、< 0 の整数が返されます。最初の文字列が == 0 より小さいことを意味します両方が等しく、> 0 の場合最初の文字列の方が大きい場合。3 つの結果のいずれかが得られるため、3 者間比較になります。

他の言語 (および C++20) には、3 者間比較を行う比較演算子があります。通常は <=> と綴られています。 < の結果が得られるため、 == と >

数学的関係に対する 3 者間比較の利点は単純です。 !(a < b) && !(b < a) 全体を実行する代わりにまたは a <= b && b <= a 2 つの要素が等しいかどうかを判断するために踊る必要がある場合は、それを直接尋ねることができます。ユーザーは述語を 1 つだけ記述する必要があります。

注文の比較カテゴリ

≤ と < 注文は 2 つの次元に基づいて分類されます:

注文は一部ですか、それとも全部ですか?
平等とは、実際に平等を意味するのか、それとも単に等価を意味するのか?

3 者間比較も、これらの次元に基づいて分類できます。2 つの要素の場合 a そして b 次の結果が得られます:

	合計	一部
同等	小さい、同等、大きい	少ない、同等、多い、順不同
平等	少ない、等しい、多い	小さい、等しい、大きい、順不同

これらのセマンティックの違いにより、C++ TIE インターセプターオーバーロードの戻り値の型は単純な int ではありません。、代わりに異なるタイプ これらのディメンションに基づく — 順序カテゴリ:

	合計	一部
同等	`std::weak_ordering`	`std::partial_ordering`
平等	`std::total_ordering`	なし

真の等価性を提供する半順序付けの型はありません。 ⊆ 代わりに弱い std::partial_ordering これは大きな問題ではありません。順序付けに関する実際のアルゴリズムは、等価性と等価性を考慮せず、全体順序付けと部分順序付けのみを考慮します (これについては、次のパートで詳しく説明します)。

これらの型は直感的に変換され、0 と比較できることに注意してください。 std::strcmp の結果を使用するのと同じ方法で .しかし、私は本当に この部分のように—それらはのみです文字どおりの数値 0 と同等、1 ではありません、 42 または何らかの整数変数!

3 者間比較の最も優れた点:operator<=> を取得したら、オーバーロードが順序付け型の 1 つを返す場合、コンパイラはすべての比較演算子もサポートします! a < b を書き換えるだけであることに注意してください。 a <=> b < 0 まで、実際には operator< を合成しませんオーバーロード。

平等の比較カテゴリ

しかし、std::complex のように、順序がなく等価性のみを持つ型はどうでしょうか。 ?それらのための特別なカテゴリがあります。

パート 1 で学んだように、2 種類の等価関係があります:真の等価と等価です。そして、それらのそれぞれが 2 つの結果のうちの 1 つを与えることができます:

種類	値
同等	同等、同等でない
平等	等しい、等しくない

一致するカテゴリは次のとおりです:

種類	カテゴリ
同等	`std::weak_equality`
平等	`std::strong_equality`

ただし、それ以外は順序付けカテゴリのように動作します。

オーバーロードされた operator<=> がある場合等値型を返す場合、コンパイラは operator== をサポートしますおよび operator!= a == b をマッピングすることでそれを行います。 a <=> b == 0 へ .

`<=>` を使用した順序付けと等式の設計

<=> の提案タイプに適したカテゴリを選択するための次の設計ガイドを提供します:

代替可能性?	平等のみ	フルオーダー
はい	`std::strong_equality`	`std::strong_ordering`
いいえ	`std::weak_equality`	`std::weak_ordering`

ここで代用可能性とは a == b かどうかを意味します f(a) == f(b) を意味します .

この表では std::partial_ordering が除外されていることに注意してください、これは良いことです:パート 3 で説明したように、比較演算子は常に全体の順序付けを実装する必要があります。

ただし、operator<=> が必要になるとは思いません。 weak_* を返す type:このような比較演算子は a == b を意味します必ずしも等しいとは限らないオブジェクトに当てはまります通常のタイプなどのトピックに触れるかなり複雑な質問であるため、最初の部分で詳しく説明しました.

ここで別の議論をさせてください:提案は CaseInsensitiveString を使用しています弱い等価性を持つ型の例として。これはです標準的な例であり、率直に言って、私が思いつくことができる唯一のものです.デフォルトの比較として、型の弱い順序付けと等価性は実際には必要ありません .

operator<=> の戻り値の型を選択するためのガイドラインを示します。 :

ガイドライン: 型に完全な順序付けが必要な場合は、std::strong_ordering を返します operator<=> から .それ以外の場合、型が等しいだけである必要がある場合は、std::strong_equality を返します .それ以外の場合は、operator<=> をオーバーロードしないでください .

これは、他のカテゴリタイプは役に立たず、大文字と小文字を区別しない文字列比較を行う方法がないということですか?

いいえ、もちろん違います。operator<=> として使用しないでください。 !代わりに std::weak_ordering case_insensitive_compare(const std::string& lhs, const std::string& rhs) を実装する必要がありますこれは、他の Unicode の等価性に対する比較関数と組み合わせることができます。私の意見では、これは優れたアプローチです。

ガイドライン :他の順序付けタイプのいずれかが必要な場合は、名前付き関数で実装してください。しない operator<=> .

このような関数をアルゴリズムで使用する方法については、シリーズの次の最後の部分で詳しく説明します。

C++20 での順序関係の実装

コンパイラの魔法のおかげで、operator<=> をオーバーロードするだけで済みます。他のものは無料で入手できます。

前回の投稿では pair を使用しました全順序付けの例としての型であり、operator== を実装する必要がありましたと operator< メンバーの比較を連鎖させてから、これら 2 つの観点から他の演算子を無意識に実装します。しかし、必要なのは operator<=> だけです。メンバーの連鎖を行います:

template <typename T, typename U>
struct pair
{
    T first;
    U second;

    // it's a total order with true equality, so std::strong_ordering
    std::strong_ordering operator<=>(const pair& other) const
    {
        if (auto first_comp = first <=> other.first;
            first_comp != 0)
            // sort by first member if they're not equal
            return first_comp;
        else
            // sort by second member
            return second <=> other.second; 
    }
};

はい、お気付きです:メンバー です function.Free 関数にする必要はありません。コンパイラは自動的に正しいことを行います。

ただし、この実装にはいくつかの問題があります:

1. `T` の場合または `U` `<=>` をサポートしていませんしかし、「古い」オペレーターだけですか?

残念ながら、コンパイラは <=> を合成しません。 == に基づくと < 、その逆です。

しかし、ヘルパー関数 std::compare_3way() があります可能な実装は次のようになります:

// types that only have an `operator==`
struct equal_only {};

template <typename T, typename U>
constexpr auto compare_3way_impl(equal_only, const T& lhs, const U& rhs)
-> decltype(lhs == rhs, std::strong_equality::equal)
{
    if (lhs == rhs)    
        return std::strong_equality::equal;
    else
        return std::strong_equality::nonequal;
}

// types that have an `operator==` and `operator<`
struct equal_and_less : equal_only {};

template <typename T, typename U>
constexpr auto compare_3way_impl(equal_and_less, const T& lhs, const U& rhs)
-> decltype(lhs == rhs, lhs < rhs, std::strong_ordering::equal)
{
    if (lhs == rhs)    
        return std::strong_ordering::equal;
    else if (lhs < rhs)
        return std::strong_ordering::less;
    else
        return std::strong_ordering::greater;
}

// types that have an `operator<=>`
struct spaceship : equal_and_less {};

template <typename T, typename U>
constexpr auto compare_3way_impl(spaceship, const T& lhs, const U& rhs)
-> decltype(lhs <=> rhs)
{
    return lhs <=> rhs;
}

// the generic function dispatching to the others
template <typename T, typename U>
constexpr auto compare_3way(const T& lhs, const U& rhs)
{
    return compare_3way_impl(spaceship{}, lhs, rhs);
}

「通常の」比較演算子に関する実装では、常に std::strong_ordering が推測されることに注意してください。、決して他の型の 1 つではありません。これは、オーバーロードされた比較演算子は常に真の等価性を持つ全順序を実装する必要があるという私のガイドラインに従っています。

operator== の実装にも注意してください。と operator< そうしないと、結果に一貫性がなくなります。これは、パート 3 で示した別のガイドラインです。

だから私たちの operator<=> 次のようになります:

std::strong_ordering operator<=>(const pair& other) const
{
    if (auto first_comp = std::compare_3way(first, other.first);
        first_comp != 0)
        // sort by first member if they're not equal
        return first_comp;
    else
        // sort by second member
        return std::compare_3way(second, other.second); 
}

すべて 汎用コードは (std::)compare_3way() を使用する必要があります <=> を使用する代わりにこれは残念なことです。

2. `T` の場合または `U` `std::strong_ordering` を持っていない ?

標準ライブラリは、そのためのヘルパーも提供します:型特性 std::common_comparison_category T のカテゴリに基づいて正しいカテゴリを計算しますと U .これは返却できます。

標準ライブラリは確かにそのような型を気にする必要がありますが、私のコードではそうしません。私のガイドラインに従って、std::strong_ordering のみを返します。 operator<=> から、決して別の順序タイプではありません。

3. `T` の場合または `U` `std::strong_equality` しかありません ?

ああ、でもこれは私自身のガイドラインに従っているので、気にする必要があります.pair<int, std::complex<double>> 比較:それは単に順序付けではなく、等しいだけです。

operator<=> は使いたくないので std::strong_ordering 以外を返すまたは std::strong_equality ,std::common_comparison_category は使えません

代わりに、独自のヘルパーを定義する必要があります:

template <typename ... CompCategories>
struct common_strong_comparison_category
{
    using type = std::conditional_t<(std::is_same_v<CompCategories, std::strong_equality> || ...), std::strong_equality, std::strong_ordering>;
};

いずれかのカテゴリが std::strong_equality の場合、順序は等しいだけです。それ以外の場合、順序は std::strong_ordering です .(カテゴリはそのいずれかであると仮定します)

これは、最終的な std::pair を意味します operator<=> 次のようになります:

auto ordering operator<=>(const pair& other) const
-> common_strong_comparison_category_t<decltype(std::compare_3way(first, other.first)), decltype(std::compare_3way(second, other.second))>
{
    if (auto first_comp = std::compare_3way(first, other.first);
        first_comp != 0)
        // sort by first member if they're not equal
        return first_comp;
    else
        // sort by second member
        return std::compare_3way(second, other.second); 
}

戻り値の型のみを変更する必要があることに注意してください!比較カテゴリのロジックと変換のおかげで、他のすべては正常に機能します.これは、int だけでなく、適切な型を返すことの真の力です。

デフォルトの順序と平等

これですべて問題ありませんが、最も重要な点をお伝えできませんでした:単純にこれを行うことができます:

auto operator<=>(const pair& other) = default;

コンパイラは、メンバーごとの比較チェーンを行う実装を生成し、適切な戻り値の型を自動的に推測します。

ただし、落とし穴があります:以前と同様、a <=> b == を使用しようとしませんまたは < 道 std::compare_3way() ここでもそうです。

default しかできませんすべてのメンバーが operator<=> を持っている場合しかし、組み込み型には 1 つがあり、標準ライブラリ型の提案があるため、将来のほとんどの型は 1 つを取得します。これは、「3 方向比較」の一般的なスペルが std::compare_3way() しない operator<=> .

= default に注意してください実装は、たとえば、弱い順序付けも推測します。それを防ぐことは、読者の課題として残されています。

しかし、それ以外の場合は、ほとんどの場合、これが必要な順序ですが、すべての型に対して盲目的にそれを配置しないでください!実際に意味のある場合にのみ、順序付けまたは等価性を提供する必要があります。前の部分を参照してください。

カスタムオーダーと平等

デフォルトの順序付けを使用できない場合は、示されているように手動で実装する必要があります。参考までに、これは std::optional の順序付けです、以前に使用したのと同じ例:

auto operator<=>(const optional& other) const
-> decltype(std::compare_3way(value(), other.value())) // again, should really constrain that
{
    if (!*this && !other)
        // both empty
        // ::equal implicitly converts to std::strong_equality::equal as well
        return std::strong_ordering::equal;
    else if (!*this)
        // empty optional less than non-empty
        // ::less converts to std::strong_equality::unequal
        return std::strong_ordering::less;
    else if (!other)
        // non-empty optional greater than empty
        // ::greater converts to std::strong_equality::unequal
        return std::strong_ordering::greater;
    else
        // forward to value
        return std::compare_3way(value(), other.value());
}

これらの暗黙的な変換の威力に注目してください!常に正しいことを行います。等価比較または順序付けのどちらを実装するかは問題ではありません。

以前と同様に、より弱い比較を行う可能性のある名前付き比較述語を実装することは、原理的には同じです。戻り値の型として適切なカテゴリを持つ関数を記述し、メンバーを使用して比較を実装します。アルゴリズム std::lexicographical_compare_3way() ) operator<=> を使用して配列を比較するために使用できます .ただし、実際に適切な順序付けを実装していることに注意してください。

C++20 標準ライブラリでの順序関係の実装

operator<=> 実際には std::strong_ordering のみを返す必要がありますまたは std::strong_equality .これは operator== の動作と一致していますと operator< std::compare_3way() で決定 .

しかし、それはすべての operator<=> の動作とも一致していますか? 標準ライブラリ用に提案されているもの!他の型の比較をラップする型を無視します (std::pair など) または std::vector )、それらはすべて std::strong_ordering を提供しますまたは std::strong_equality .

EqualityComparable のような比較の概念または LessThanComparable operator== のいずれかで動作します /operator< または適切な operator<=> .それらは弱い順序付けまたは等価性のみを必要とします.それについては最後の部分で詳しく説明します.

結論

operator<=> の導入により順序付けと等価関係の設計と実装の両方が簡素化されました。タイプがサポートする順序付け/等価関係の種類を記述する良い方法があり、多くの場合実装は = default です。 .std::strong_ordering のみを使用することを忘れないでくださいと std::strong_equality operator<=> の比較カテゴリとして、他の順序付けは名前付き関数で実装する必要があります。

operator<=> を使用する一般的なコードには注意が必要です < を使用し続ける必要があります。と == または std::compare_3way() 3 者間比較が必要な場合。

詳細については、こちらをご覧ください:

元の提案
新しいヘッダー (実際には #include <=> であるべきでした) ..)
Simon のハイレベルな紹介

このシリーズの次の最終回では、最大値の検索や検索など、順序付けが必要なアルゴリズムを見ていきます。