stl 順序付け - 厳密な弱い順序付け

StackOverflow https://stackoverflow.com/questions/1293231

質問

STL が次のような比較関数で機能するのはなぜですか? 厳密な弱い順序付け?なぜ部分的な順序付けができないのでしょうか?

役に立ちましたか？

解決

A 半順序には、ソートアルゴリズムのようないくつかのアルゴリズムを実装するのに十分ではないであろう。半順序集合は必ずしもセットのすべての要素間の関係を定義していないので、どのように半順序内の順序関係を持たない2つの項目のリストを並べ替えるでしょうか？

他のヒント

単純に、厳密な弱い順序付けは、次のような順序付けとして定義されます。 (計算可能な)等価関係を定義します. 。同値クラスは厳密な弱い順序付けに従って順序付けされます。 厳密な弱い順序付けは、等価クラスに対する厳密な順序付けです。.

部分的な順序付け (厳密な弱い順序付けではない) は同値関係を定義しないため、 「同等の要素」の概念を使用する仕様は、厳密な弱い順序付けではない部分的な順序付けでは意味がありません。 すべての STL 連想コンテナーは、ある時点でこの概念を使用するため、厳密な弱い順序付けではない部分順序付けでは、これらの仕様はすべて無意味になります。

部分的な順序付け (厳密な弱い順序付けではない) は必ずしも厳密な順序付けを定義するわけではないため、部分的な順序付けに従って常識的に「要素を並べ替える」ことはできません (できるのは、より弱いプロパティを持つ「トポロジカルな並べ替え」だけです) ）。

与えられた

  • 数学的集合 S
  • 部分的な順序付け < 以上 S
  • 価値 x で S

のパーティションを定義できます S (のすべての要素 S どちらかに入っている L(x), I(x) または G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

シーケンスは次に従ってソートされます < もし すべてのための x シーケンス内の要素 L(x) シーケンスの最初に表示され、その後に次の要素が続きます。 I(x), 、その後に次の要素が続きます G(x).

シーケンスはトポロジー的にソートされます もし あらゆる要素に対して y 別の要素の後に表示される x シーケンスでは、 y 未満ではありません x. 。これは、並べ替えよりも弱い制約です。

のすべての要素を証明することは簡単です。 L(x) は、のどの要素よりも小さいです G(x). 。の要素間に一般的な関係はありません L(x) と要素 I(x), 、または要素間 I(x) と要素 G(x). 。ただし、 < のすべての要素よりも厳密な弱い順序付けです。 L(x) は、のどの要素よりも小さいです I(x), 、そして、のどの要素よりも I(x) は、のどの要素よりも小さいです G(x).

もし < は厳密な弱い順序付けであり、 x<y 次に、の任意の要素 L(x) U I(x) どの要素よりも小さい I(y) U G(y):以下の要素 x どの要素よりも小さく、それ以上ではない y. これは、部分的な順序付けには必ずしも当てはまりません。

与えられた回答を引用すると、 ここ:

これらのアルゴリズムは内部的に「等しい」を次のように実装しているためです。 !(a < b) && !(b < a).

使用した場合 <= より少ないオペレーターを実装するために、上記は a == b. 。壊れた平等チェックは、ほぼすべてのアルゴリズムを台無しにします。

同様に、「等しくない」を次のように実装します。 (a < b) || (b < a)、そしてもう一度、あなたが実装した場合、 < オペレータが使用する <=, 、それから彼らが互いに等しいとき、それは実際にはそれらが等しくないときに真実に戻ります。したがって、等価性チェックは両方向で失敗します。

ライブラリをより少ないオペレーターに制限することの全体的なポイントは、すべての論理演算子をそれに関して実装できることです。

  • <(a, b): (a < b)
  • <=(a, b): !(b < a)
  • ==(a, b): !(a < b) && !(b < a)
  • !=(a, b): (a < b) || (b < a)
  • >(a, b): (b < a)
  • >=(a, b): !(a < b)

これは、提供されたオペレーターが厳格な弱い順序の条件を満たしている限り機能します。標準 <= そして >= オペレータはそうではありません。

あなたは半順序でバイナリ検索を実行することはできません。あなたは半順序でのバイナリ検索ツリーを作成することはできません。どのような機能/ のアルゴリズムのからのデータ型は、順序付けを必要とし、半順序で作業することができますか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top