7

【SGI公式ドキュメント】

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

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

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

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

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

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

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

4

1 に答える 1

9

部分的な順序付けは、本質的に、<=. と の両方の場合、a <= bそれb <= aはaと同等であると言えますb。a <= bしかし、どちらでもない可能性もありますb <= a- 2 つの要素は比較にならないものです。その結果、std::sort部分的な順序関係を持つセットに (必要になるような) 全順序を課すことはできません。せいぜい、トポロジカル ソートを行うことができます。また、同値関係を導き出すこともできません。繰り返しますが、比較できない要素が存在する可能性があります。

厳密な弱い順序付けは のようなもの<です。と の両方a < bを使用することはできません。また、b < aどちらa < bでもない場合は、と を同等b < aに発音できます。ab

全体的な順序付けは、2 つの要素が等しい場合にのみ等価である単純な厳密な弱い順序付けです (これは、より少ない述語に加えて等しい比較述語があり、両方を使用する C++ 標準ライブラリ アルゴリズムがない場合にのみ意味があります)。同時に、この問題はこの文脈ではほとんど意味がありません)。

于 2013-09-13T13:21:42.787 に答える