問題タブ [strict-weak-ordering]

【SGI公式ドキュメント】

非反射性と推移性のため、operator< は常に半順序の定義を満たします。厳密な弱順序の定義はより厳密であり、全順序の定義はさらに厳密です。

また、ドキュメントの厳密な弱い順序付けの定義も読みました: StrictWeakOrdering

最初の 3 つの公理、非反射性、反対称性、および推移性は、半順序の定義です。等価性の推移性は、厳密な弱い順序付けの定義によって必要とされます。全順序付けは、さらに強い条件を満たすものです: 同等性は同等性と同じでなければなりません。

これらの定義についてはよくわかりません。主な質問:

1.半順序付けは暗黙的に同値を定義しますか?

2.厳密な弱順序付けと全順序付けについてはどうですか?

3.STL はソート アルゴリズムで厳密な弱い順序付けを必要としますが、なぜ部分的順序付けまたは全体的順序付けではないのですか? この質問について、非反射性、反対称性、半順序付けの定義である推移性の 3 つの公理を満たすことを証明することによって、有効な比較規則を証明するいくつかの教科書を読みました。ドキュメントでは、演算子 < は常にこの定義を満たすことを参照しています。部分的な順序付けを使用して、または同等に演算子を使用してオブジェクトを比較できないのはなぜですか

次の問題があります: この (簡略化された) 構造を考えてみましょう:

今、私はすべてのタスクのセットを持ち、それを使っていくつかの作業をしたいと思っています. したがって、すべての要素が等しいことを確認する等価演算子があります。

このために、正常に機能する std::unordered_set を使用しました。

しかし今、これらのタスクを優先度順に並べ替えて（最も優先度の高いタスクを取得するために）セットに入れたいと思っています。明らかに、これは std::unordered_set では不可能なので、次の less 演算子を使用して std::set を試しました。

しかし、これは厳密な弱い順序付けによって、優先度が等しい場合に2つのタスクが等しいことを意味します。これは望ましくありません(同等性チェックのために isEqual メソッドを維持したい)。

一連のタスクを達成するための最良の方法は何ですか?要素を非常に高速に挿入でき、重複するエントリ (私の isEqual 関数で定義) がなく、優先度が最も高いタスクを非常に高速に取得できますか?
私は特定のSTLコンテナに縛られていませんが、サードパーティのライブラリを使用したくありません(ブーストさえも)。

私のデータでは Field2 が常に使用できるとは限らないため、ワイルドカード値 0 を使用することがあります。これは、field1 が一致する任意の値に一致する可能性があります。ワイルドカード値を持つ要素を挿入せず、セット内でのみ検索する場合、これは C++ で有効ですか? この場合、私のコードではめったに発生しない値を返す find 関数で問題ありませんが、繰り返し呼び出されたときに同じ値になることを願っています。

仕様によると、ルックアップを実行するときにデータ構造で使用される唯一のアルゴリズムである binary_search には厳密な弱い順序付けは必要ないようです。または、ここで心配する必要がある未定義の動作がありますか?

25.4 並べ替えと関連操作

... 25.4.3 で説明されているもの以外のアルゴリズムが正しく機能するためには、comp は値に対して厳密な弱い順序付けを誘導する必要があります...

25.4.3 二分探索

私は STL コンテナーとそれらがサポートする比較関数/ファンクターをいじっていますが、priority_queue が通常の厳密な弱い順序付けに従っていないことがわかりました。理由を理解しようとしていますが、それを理解することはできません。ポインターが役立ちます。

また、このブログでは、priority_queue が厳密な弱い順序付けに従っていないことにも言及しました。ここにリンクの説明を入力

順序付けが推移的なPython2 の既存の実装はありますか? つまり、ユーザー定義型を作成せずにこの動作を確認することは不可能です。

この反例のため、CPython は推移的ではありません

ただし、CPython でのこの順序付けは、実装の詳細としてのみ 文書化されています。

私は、c++ コンパレータの厳密な弱い順序付けに従う必要があることを知っています。そして主な理由は、それ!(a > b) && !(b > a)が等価演算子として機能することです。

しかし、問題は、等価演算子 not like を必要としない場所でのみソートすることですstd::set。

たとえば、セットのベクトルがあり、セット A が B の適切なサブセットである場合、並べ替え後、セット A のインデックスはセット B のインデックスよりも小さくなければなりません。

したがって、このようにコンパレーターを書くと仮定します

ではstd::sort、このコンパレータは常にトポロジカル ソートのように機能しますか?

プラス）

不足している情報を提供してくれた Oliver Charlesworth に感謝します。

このようなコンパレータが、トポロジカル ソートとしてクイック ソートや挿入ソート (いくつかの有名な比較ベースのソート アルゴリズム) と連携することを本当に知りたいです。