比較の背後にある数学 #1:等価関係と等価関係

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

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

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

このパートでは、等価関係と等価関係について説明します。2 つのオブジェクトが等しいとはどういう意味ですか?満たす必要がある数学的プロパティと C++ セマンティクスは何ですか?C++ で適切な等価比較を実装するにはどうすればよいですか?

次の部分では、順序関係、新しい 3 者間比較、およびさまざまな順序での並べ替えや検索などのアルゴリズムについて説明します。

基本用語

operator== のセマンティクスを定義するために数学を使用したい と operator< .そのためには、C++ を数学に変換する必要があります。そのために、Elements of Programming の用語を (少し変更して) 使用します。

値は、エンティティの抽象的な数学的概念です。数値 42 値、または文字列 "Hello World!" です .それらは抽象的で不変であり、数学を使用して値について話すことができます.一方、オブジェクトは実際にC++で処理する具体的なものです.オブジェクトはメモリのどこかに値を保存し、現在保存されている値を変更できます.格納され、どの値を格納できるかは、オブジェクトのタイプによって制御されます。可能な値のセットと、メモリ内のそれらの値の表現という 2 つのことを定義します。

例えば ​​int i = 42; タイプ int の新しいオブジェクトを作成します 現在値 42 を保持しています .これは (通常) 42 の符号付き 2 の補数として格納されます 4 バイトを使用します。short j = 42;42 も格納します しかし、2 バイトしか使用しないため、メモリ内での表現が異なります。後で ++i を実行すると、 オブジェクト i の値を変更します 43 まで は変更しませんでした 42 .

operator== C++ では、同じ型の 2 つのオブジェクトを受け取り、それらが等しいかどうかを返す関数です。

数学における等価性は、セットの 2 つの要素を取り、それらが等しいかどうかを返す何らかの「演算」です。オブジェクトの値を使用して operator== について話すことができます。 C++ で数学を使用:値が等しい場合、2 つのオブジェクトは等しくなります。

数学における平等をさらに詳しく見てみましょう。

二項関係

等価 (および比較) は二項関係として一般化されます。二項関係 R セット A 以上 は単なるペアのセットです。これらは、相互に関連するすべての要素です。

たとえば、色のセット C := {yellow, red, green, blue, cyan, magenta} を考えてみましょう .「の補数である」二項関係を定義できます (または ) 補色のすべてのペアをリストする:↔ := {(yellow, blue), (blue, yellow), (red, cyan), (cyan, red), (green, magenta), (magenta, green)} .

セット a, b ∈ A の 2 つの要素がある場合 a R b と書きます ("a b に関連しています R で定義されているとおり ") (a, b) ∈ R の場合 .

例えば ​​yellow ↔ blue なぜなら (yellow, blue) ∈ ↔ .

同値関係

平等について話すとき、私たちは当然二項関係から特別な性質を期待します:

  • すべての要素はそれ自体と等しくなければなりません。そのプロパティとの関係は再帰的と呼ばれます。
  • If a b に等しい 、次に b a と等しくなければなりません .そのプロパティとの関係は対称的です。
  • そして最後に要素が 2 つ a の場合 と b b と等しい 他の要素 c と等しい 、そして当然 a c と等しくなければなりません 同じように。そのプロパティとの関係は推移的と呼ばれます。

再帰的、対称的、および推移的なすべての二項関係は、等価関係と呼ばれます。このような関係は、ある種の等価性を定義し、「等価」の一般化された形式です。

私たちの is_complement_of 関係は同値関係ではありません:

  • 再帰的ではありません。それ自体を補完する色はありません。
  • 推移的ではありません:3 つの色がある場合 a, b, c どこで a ↔ bb ↔ c 、次に a = c すべての色には独自の補色があるため.しかし a ↔ a 再帰的ではないため、false です。
  • しかし、これは左右対称です。すべてのペアを順番を逆にして意図的に入れ直しました。

そして当然古典的な = 数学の真の平等です。それは次のように定義された関係です:= := {(a, a) | a ∈ A} 、つまり、ペア (a, a) のみで構成されます セット A のすべての要素 .つまり:すべての要素はそれ自体と等しいが、のみ

カラーセット C の場合 したがって、同等性は次のように定義されます = := {(yellow, yellow), (red, red), (green, green), (blue, blue), (cyan, cyan), (magenta, magenta)} .

同等性は、あなたが想像できる最も厳密な同等性関係です:同等性関係として認定するにはかろうじて十分です.

たとえば、色の等価関係を I として定義できます。 それらが表示されます:cyan 醜い blue です .だから、他の等式に加えて、cyan blue と同等です .

数学的には、この同値関係 (≅ と呼びましょう) は次の集合です:≅ := {(yellow, yellow), (red, red), (green, green), (blue, blue), (cyan, cyan), (cyan, blue), (blue, cyan), (magenta, magenta)} .

(cyan, blue) を追加しました と (blue, cyan) これは、関係が依然として対称であるため必要でした (2 つの異なる要素のみが同等であるため、推移について心配する必要はありません)。

現在 blue ≅ blueblue ≅ cyan も .

C++ での等価関係の設計

ここまでは数学的なものです。

C++ では、セットを扱うのではなく、型を扱います。これらの型は、セット、つまり値のセットを間接的に定義するだけです。

いくつかの型では、どのような値を持っているかが非常に単純です。この型は、カラー セット C を明確に定義します。 以前から:

enum class color
{
    yellow,
    red,
    green,
    blue,
    cyan,
    magenta
};

他のタイプの場合、実際の値が何であるかはあまり明確ではありません。foo を検討してください。 :

struct foo
{
    int* ptr;
    int size;
};

その値は、ポインタとサイズのペア、つまり foo のいずれかです。 次の std::span<int> のようになります .または、その値は size の配列である可能性があります 整数、つまり foo std::vector<int> のようになります .それはすべて、追加のセマンティクスに依存します。

型の正確な値がわからない場合、これは型の比較を追加すべきではないことを示す良い指標です。

一般に、C++ には 2 種類の型があります。コンテナー、整数、さらには std::optional のような数学的構成要素をエンコードするだけの型があります。 .通常は図書館にあります。

そして、GUI やビジネス ロジック クラスなど、動作とアクションをエンコードする型があります。button を検討してください。 クラス、その値は?

ここには良い答えはありません。確かに、数学的には位置、ラベル、クリック状態、およびコールバックのタプルであると言えますが、それは実際には button の本質を捉えていません。 .それはその部分の合計以上のものです.したがって、このタプルで等価関係を定義しても実際には機能しません.

この 2 番目のタイプのカテゴリは、数学的な方法で簡単に説明できないタイプです。これができない場合、等価関係を指定することも困難です。

タイプがコピー可能ではない (移動のみ可能) 場合、これは別の指標です。通常、リソースに対する一意の所有者です。所有者は 1 人しかいないため、2 つのオブジェクトが実際に等しいことはありません。

これは次のルールにつながります:

ルール: 型の値がわからない場合は、等値関係を実装しないでください。

特に、operator== を追加しないでください。 タイプをハッシュテーブルに入れたい、または std::find() を使用したいという理由だけで 、たとえば。代わりに、カスタム比較述語を提供するか、 std::find_if() を使用します .もちろん、それらは some を比較する等価関係である必要があります 値、検索している/ルックアップに使用したい値。ただし、これはオブジェクト全体の値とは異なる値である可能性があります。たとえば、ボタンのラベルを使用してルックアップしたい場合があります.

明確な値があれば、この値のセットに対して数学的な等価関係を定義できます。数学ではペアのセットにすぎませんが、C++ では 2 つのオブジェクトを取り、bool を返す関数です。 .特に、operator== のいずれかになります。 または名前付き関数。

いつどれを使うべきですか?

ルール: 真の等価である値の等価関係を実装する場合 (つまり、値はそれ自体と等しいだけです)、この関数に operator== という名前を付けます 一致する operator!= を提供します .値のより弱い等価関係を実装する場合 (つまり、私の色の等価性のようなもの)、この関数に意味のある名前を付けてください not operator== .

つまり、 operator== のみを実装します 実際に真の平等を実装している場合 、より弱い等価物ではありません .それには 2 つの理由があります。

1 つ目は、最小の驚きの原則です。ユーザーは、あなたの operator== を期待しています。 は、2 つのオブジェクトが等価であるだけでなく、真に等しいかどうかを返します。数学を知らなくても、彼らは直感的に把握できます。さらに、等価は 1 つだけですが、多くの等価があります。特別な名前ですか?特別な名前を付けることで、それがどの同等物であるかが明確になります。

もう 1 つの理由は、より数学的なものです:operator== を持つ これは、真の等価性とは、ほとんどの関数が正規であることを意味します。正規の関数とは、等しい入力で呼び出すと、等しい出力が得られる関数です。

std::string を検討してください 例として std::string の正規関数 operator[] です :等しい入力 (つまり、等しい文字列とインデックス) で呼び出すと、等しい出力 (つまり、同じ文字) が得られます。std::string::c_str() 一方、規則的ではありません。等しい文字列の指す先は同じ文字列になりますが、異なるメモリアドレスを指している可能性があります。ポインタが等しくありません。

仮定の ci_string を考えてみましょう . std::string のようです 、しかしその operator== 大文字と小文字を区別しない比較を行います。これは真の等価性を実装していません:等しくない一連の文字は等価である可能性があります (大文字と小文字が異なるために等しくない場合)。ただし、これは operator[] を意味します は通常の関数ではなくなりました:

ci_string a = "hello";
ci_string b = "HELLO";
assert(a == b);
assert(a[0] == b[0]); // fails!
// even though we're calling the function with equal inputs

ci_string を変更すると operator[] を変更するたびに、常にすべての文字を小文字に変換するようにします。 突然通常になります。常に小文字を返します。しかし、ci_string の値を変更したため、これは予期されたものです。 .以前は std::string のような「文字列」でした .今度は「小文字の並び」と operator== 真の平等を実装します。

等価セマンティクスは、型の値の定義に大きく依存します。そのため、型が持つ値の種類を正確に知ることが非常に重要です。

色の場合は operator== が必要です 値の等価性を実装する = および名前付き関数 foonathan_thinks_its_equal() の実装 .一貫性を保つために、operator!= も追加する必要があります。 operator== を否定する (名前付き関数には必要ありません)。

bool operator==(color a, color b);
bool operator!=(color a, color b);

bool foonathan_thinks_its_equal(color a, color b);

等価性のない等価関係を持つことは理にかなっている可能性があることに注意してください。これは、真の等価演算はコストが高すぎるため、誤って呼び出される可能性のある演算子で行うべきではないことが原因である可能性があります。または、真の等価性を実装することは不可能です。同等性が弱いだけです。ただし、operator== を指定しないでください。 より弱い同等にする代わりに。

C++ での等価関係の実装

モデル化する値のセット、実装する同値関係、および実装のインターフェースを決定しました。どのように記述しますか?

最初に真の等価性に取り組みましょう。次に、現在の値が等しい場合に限り、2 つのオブジェクトが等しいと言えます。では、オブジェクトから値を取得するにはどうすればよいでしょうか?

等価演算を実装する場合、複合型を扱います。 struct または class 直接的または間接的に複数のプロパティを持つことができます。直接的プロパティは型のメンバー変数であり、間接的プロパティは直接的または間接的なプロパティであるポインターから到達できるオブジェクトです。または、プロパティは新しいプロパティを計算する関数です。他のプロパティの値に基づきます。

例:std::vector<T> メモリへのポインタ、サイズ、および容量の 3 つの直接プロパティがあります。また、間接プロパティは、それが指すメモリ内のすべてのオブジェクトです。ただし、直接プロパティとして 3 つのポインタを持ち、それらを減算してサイズと容量を計算することもできます。ただし、これはベクトルの値と同等です。

すべてのプロパティがオブジェクトの値の一部であるとは限りません。たとえば、std::shared_ptr の値 は、コントロール カウントではなく、間接的なプロパティであるポインティーでもなく、所有するポインターです。したがって、2 つの共有ポインターを比較するには、ポインターのみを比較する必要があります。

一方、std::vector の場合 値は、ベクトルに格納された要素のシーケンスです。したがって、2 つのベクトル要素を比較すると、間接プロパティである要素が比較されます。ポインタ自体は比較されませんが、ポインタが指すオブジェクトが比較されます。

値の一部であるプロパティを顕著と呼びましょう。他のプロパティは顕著ではありません.2 つのオブジェクトは、それらのすべての顕著プロパティが等しい場合に等しくなります.

プロパティの比較は通常、等しいかどうかで行われますが、オーバーライドする必要がある場合もあります。これは、ポインター (またはポインターのように動作するもの) の場合に最も顕著です。場合によっては、ポインティ自体の同等性が必要なため、提供された operator== を使用できません ただし、カスタム コードを記述する必要があります。

ルール: 同等性を実装する、つまり operator== 、実際に値を形成するプロパティを比較します。それらは、直接のメンバーまたはポインターから間接的に到達可能な他のオブジェクトである可能性があります。

同等性を実装する方法がわかったら、それに従って、より厳密でない等価関係を実装できます:true も返すだけです。 値を構成するプロパティを比較することにより、同等であるが等しくないオブジェクトの場合。

色の場合、等価関係は次のようになります:

bool foonathan_thinks_its_equal(color a, color b)
{
    if (a == b)
        // trivial case due to the reflexive property
        return true;
    else if (a == color::cyan && b == color::blue
          || a == color::blue && b == color::cyan)
        // in addition blue is equivalent to cyan
        return true;
    else
        // but no other colors are equal
        return false;
}

等価関係だけがあり等価性がない場合でも、それを行うことができます。等価性の定義は、等価性の実装にインライン化されます。

コピーと平等の関係

最後に、コピー操作と等価性の関係に簡単に触れたいと思います:コピー演算はオブジェクトの値を別のオブジェクトにコピーし、等価演算は 2 つの値を比較します。

これは次のことを意味します:

ルール: コピーは常に等しくなければなりません。

さらに、それらの実装は密接に関連しています:等値演算は、通常は operator== とすべての顕著なプロパティを比較します。 プロパティの、しかし時々それを上書きします (例えば、ポインターのアドレスだけでなく、ポインティング先の比較を行うため)。たとえば、ポインターだけでなく、ポインティング先のコピーを作成します)。

シャロー コピーという用語を使用しているのと同じです。ポインタをコピーするだけでポインティをコピーしない型、浅い等価という用語も使用できます。ポインタのみを比較し、ポインティを比較しない型。反対側には、ディープ コピーとディープ イコールもあります。

これは次のルールにつながります:

ルール: ディープ コピーがある場合は、ディープ イコールも実装する必要があります。シャロー コピーがある場合は、浅いイコールも実装する必要があります。

そうすれば、操作が一貫して自然に機能します。std::vector を検討してください。 もう一度:std::vector<T>::data() ベクトルの値の一部ではないため、コピー操作では保持されません (コピーは新しいメモリ data() を使用するため) は別のポインターを返します)。そして当然のことながら、std::vector<T> の深い等号 比較しません:

std::vector<int> a = …;
std::vector<int> b = a;
assert(a == b); // succeeds
assert(a.data() == b.data()); // fails

capacity() でも 非顕著な:値を変更せずに変更できます。

b.reserve(b.capacity() * 2); // this just changes the capacity, not the elements
assert(a == b); // so they are still equal
assert(a.capacity() == b.capacity()); // but with different capacities

実際の要素は顕著であり、それらを変更すると値が変更されます:

b.front()++; // change the value
assert(a != b); // so they are different

ルール: 顕著なプロパティを変更すると、オブジェクトは以前のオブジェクトと等しくなります。

標準ライブラリには、これらの規則に完全に従わない型があります:std::string_view .浅いコピー (ポインタをコピーするだけ) ですが、深い等価性 (文字列全体を比較する) があります。これは、上記の等価性の規則に違反していることを意味します:

std::string str = "Hello World!";

std::string_view view = str;
std::string_view copy = view;
assert(view == copy); // this is true

str[0] = 'h'; // changing a salient property (according to equality)
assert(view == copy); // but this is still true!

std::string_view の値は? ?

コピー操作を尋ねると、「その値はポインタとサイズです」と表示され、等価性を尋ねると「その値は文字のシーケンスです」と表示されます。この値の二重定義は混乱を招く可能性がありますが、幸いなことにその結果はstd::string_view は文字のシーケンスをそれ自体で変更することはできず、その最も一般的な使用法ではこのエラーが発生することはありません。詳細については、Abseil ブログのこのエッセイをお読みください。

そして最後に、通常の型に言及せずに平等について語ることはできませんが、このブログ投稿はすでに非常に長いため、それらについて読んでみる (または、プログラミングの要素を購入する) ことをお勧めします。

結論

operator== のセマンティクスの決定 基本的に、オブジェクトの値が実際に何であるかを決定することです。次に、コピー操作を実装して値をコピーし、比較演算子を実装して、数学的な等価性のために 2 つの値を比較します。その後、より弱い等価性、つまり等価性を実装する必要がある場合は、名前付き関数として実行してください。

オブジェクトの値がよくわからない場合は、operator== を定義しないでください。 .その大きな兆候は、型のコピー操作を実際に持っていないか、それが数学的なものではないことです.