stl Ordnung - strenge schwache Ordnung

Question

Warum funktioniert STL Arbeit mit einer Vergleichsfunktion, die strenge schwache Ordnung ist? Warum kann es nicht teilweise Ordnung sein?

Answer 1

partielle Ordnung würde nicht ausreichen, einige Algorithmen zu implementieren, wie ein Sortieralgorithmus. Da eine teilweise geordnete Menge nicht notwendigerweise eine Beziehung zwischen allen Elementen des Satzes definieren, wie würden Sie eine Liste aus zwei Elementen sortieren, die in der Teilordnung keine Auftrag Beziehung haben?

Answer 2

Einfach gesagt, eine strenge schwache Ordnung wird als Bestell definiert, dass definiert eine (berechenbare) Äquivalenzrelation . Die Äquivalenzklassen werden durch die strenge schwache Ordnung bestellt. eine strenge schwache Ordnung ist eine strenge Ordnung auf Äquivalenzklassen

Eine partielle Ordnung (das keine strenge schwache Ordnung ist) wird nicht definiert, eine Äquivalenzbeziehung, so jede Spezifikation, das Konzept der „äquivalenter Elemente“ ist bedeutungslos, mit einer partiellen Ordnungs verwenden, die keine strenge schwache Ordnung ist. Alle STL assoziativen Container verwenden dieses Konzept an einem gewissen Punkt, so dass all diese Spezifikationen sind bedeutungslos, mit einer partiellen Ordnung, die keine strenge schwache Ordnung ist.

Da eine partielle Ordnung (das ist keine strenge schwache Ordnung) nicht unbedingt jede strenge Ordnung definieren, können Sie nicht „Elemente sortieren“ im herkömmlichen Sinne nach partieller Ordnung (alles, was Sie tun können, ist eine „topologische Sortierung“, die hat schwächere Eigenschaften).

Da

• ein mathematischer Satz S
• eine partielle Ordnung < über S
• ein Wert x in S

Sie eine Partition von S definieren können (jedes Element von S ist entweder in L(x), I(x) oder 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

Eine Sequenz sortiert nach < iff für jede x in der Sequenz, die Elemente der L(x) erscheinen zuerst in der Sequenz, die von Elementen der I(x), gefolgt von Elementen der G(x).

Eine Sequenz topologisch sortiert ist iff für jedes Element y, die nach einem anderen Element x in der Folge erscheint, ist y nicht weniger als x. Es ist eine schwächere Einschränkung als die sortiert werden.

Es ist trivial zu beweisen, dass jedes Element von L(x) weniger als jedes Element von G(x). Es gibt keine allgemeine Beziehung zwischen den Elementen von L(x) und Elementen von I(x) oder zwischen den Elementen von I(x) und Elementen der G(x). Wenn jedoch < ist eine strenge schwache Ordnung, als jedes Element von L(x) weniger als jedes Element von I(x), und als jedes Element von I(x) weniger als jedes Element von G(x).

Wenn < eine strenge schwache Ordnung ist, und x<y dann jedes Element von L(x) U I(x) weniger als jedem Elemente I(y) U G(y): jedes Element nicht größer als x ist weniger als jedes Element nicht weniger als y. Dies bedeutet nicht unbedingt für eine partielle Ordnung halten.

Answer 3

Zitiert die Antwort gegeben hier :

  

Da intern, diese Algorithmen implementieren "gleich", wie !(a < b) && !(b < a).

     

Wenn Sie verwenden <= die weniger als Operator zu implementieren, dann der oben   würde return false wenn a == b. Eine gebrochene Gleichheitsprüfung wird vermasseln   fast jeder Algorithmus.

     

Und sie implementieren „ist nicht gleich“ wie (a < b) || (b < a)   Und noch einmal, wenn Sie den < Operator implementiert <= verwendet wird, dann   gibt true zurück, wenn sie einander gleich sind, wenn sie in der Tat   sind nicht gleich. So ist die Gleichheitsprüfung wird in beiden Richtungen gebrochen.

     

Der springende Punkt, die Bibliothek zu einem der Begrenzung weniger als Betreiber   dass alle logischen Operatoren können in Bezug auf die sie umgesetzt werden:

     

  
• <(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)
  

     

Das funktioniert, solange Sie bereitgestellt Betreiber die Bedingungen a erfüllen   strenge schwache Ordnung. Die Standard-<= und >= Betreiber dies nicht tun.

Answer 4

Sie können nicht binäre Suche mit teilweise Ordnung durchzuführen. Sie können nicht einen binären Suchbaum mit teilweise Ordnung schaffen. Welche Funktionen / Datentypen von Algorithmus müssen Ordnung und kann mit teilweise Ordnung arbeiten?