c++ - set を使用した less または less_equal

Question

関数を (少ない) 演算子として、、、、、... などの STL データ構造に渡すことが<できsetます。multisetmappriority_queue

<=関数が(less_equal)のように動作する場合、問題はありますか?

Answer 1

はい、問題があります。

正式には、比較関数は厳密な弱い順序付けを定義する必要がありますが、それは行い<=ません。

より具体的には、<は等価性を判断するためにも使用されます (xとyは等価 iff!(x < y) && !(y < x)です)。これは当てはまりません(その演算子を使用すると、セットはオブジェクトが決して同等ではない<=と信じます)

Answer 2

有効な STL から -> 項目 21. 等しい値に対して常に比較関数が false を返すようにします。

less_equal が比較タイプであるセットを作成し、10 をセットに挿入します。

set<int, less_equal<int> > s; // s is sorted by "<="
s.insert(10); //insert the value 10

もう一度 10 を挿入してみてください:

s.insert(10);

この挿入呼び出しでは、セットは 10 がすでに存在するかどうかを判断する必要があります。そうであることを私たちは知っています。しかし、セットは乾杯のようにばかげているので、チェックする必要があります。セットがこれを行うときに何が起こるかを理解しやすくするために、最初に挿入された 10 を 10A と呼び、挿入しようとしている 10 を 10B と呼びます。 10Bを挿入します。最終的には、10A と同じかどうかを確認するために 10B をチェックする必要があります。連想コンテナの「同じ」の定義は同等であるため、セットは 10B が 10A と同等かどうかをテストします。このテストを実行するとき、当然セットの比較機能が使用されます。この例では、set の比較関数として less_equal を指定したため、これは operator<= であり、less_equal は演算子を意味します。

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence

10A と 10B はどちらも 10 なので、10A <= 10B は明らかに真です。同様に明らかに、10B <= 10A です。したがって、上記の式は次のように単純化されます。

!!(true)&&!(true)

そして、それは次のように単純化されます

false && false

これは単に誤りです。つまり、セットは、10A と 10B は同等ではなく、したがって同じではないと結論付け、したがって、10B を 10A と一緒にコンテナーに挿入します。技術的には、このアクションは未定義の動作をもたらしますが、ほぼ普遍的な結果は、セットが値 10 の 2 つのコピーで終わることであり、それはもはやセットではないことを意味します。比較型として less_equal を使用することで、コンテナーが破損しました! さらに、等しい値が true を返す比較関数は、同じことを行います。等しい値は、定義上、等価ではありません!

Answer 3

確かに問題があります。

比較関数は厳密な弱い順序付けを満たす必要がありますが、そうではあり<=ません。