commande stl - stricte commande faible

Question

Pourquoi fonctionne STL avec une fonction de comparaison qui est commande stricte faible? Pourquoi ne peut-il être un ordre partiel?

Answer 1

ne serait pas suffisante ordre partiel pour mettre en œuvre des algorithmes, comme un algorithme de tri. Depuis un ensemble partiellement ordonné ne définit pas nécessairement de lien entre tous les éléments de l'ensemble, comment voulez-vous trier une liste de deux éléments qui n'ont pas une relation d'ordre dans l'ordre partiel?

Answer 2

Simplement, un ordre strict faible est défini comme étant un ordre qui définit une relation d'équivalence (calculable) . Les classes d'équivalence sont ordonnées par l'ordre strict faible. une commande faible stricte est un ordre strict sur les classes d'équivalence

Un ordre partiel (soit pas un ordre faible strict) ne définit pas une relation d'équivalence, de sorte toute spécification utilisant le concept d ' « éléments équivalents » n'a pas de sens avec un ordre partiel qui ne soit pas un ordre faible strict. tous les conteneurs associatifs STL utilisent ce concept à un moment donné, donc toutes ces spécifications sont sans signification avec un ordre partiel qui n'est pas un ordre strict faible.

Parce qu'un ordre partiel (ce n'est pas un ordre faible strict) ne définit pas nécessairement un ordre strict, vous ne pouvez pas « trier les éléments » dans le bon sens selon un ordre partiel (tout ce que vous pouvez faire est un « tri topologique » qui a des propriétés plus faibles).

Étant donné

• un S mathématique ensemble
• un < de commande partielle sur S
• une x de valeur dans S

vous pouvez définir une partition de S (chaque élément de S est soit dans L(x), I(x) ou 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

Une séquence est triée selon la < iff pour chaque x dans la séquence, les éléments de L(x) apparaissent en premier dans la séquence, suivie par des éléments de I(x), suivis par des éléments de G(x).

Une séquence est triée topologiquement iff pour chaque y élément qui apparaît après une autre x d'élément dans la séquence, y est pas inférieure à x. Il est une contrainte plus faible que d'être triés.

Il est trivial de prouver que chaque élément de L(x) est inférieur à tout élément de G(x). Il n'y a pas de relation générale entre les éléments de L(x) et des éléments de I(x), ou entre les éléments de I(x) et des éléments de G(x). Toutefois, si < est un ordre strict faible, que tous les éléments de L(x) est inférieur à tout élément de I(x), et que tout élément de I(x) est inférieur à tout élément de G(x).

Si < est un ordre strict faible, et x<y alors tout élément de L(x) U I(x) est à moins de tout élément I(y) U G(y): tout élément non supérieur à x est inférieure à tout élément non moins que y. Cela ne tient pas nécessairement un ordre partiel.

Answer 3

Citant la réponse :

  

Parce que l'interne, ces algorithmes mettent en œuvre "est égal à" comme !(a < b) && !(b < a).

     

Si vous avez utilisé <= pour mettre en œuvre le moins que l'opérateur, le ci-dessus   retournerait faux quand a == b. Une vérification de l'égalité cassée bousiller   presque tout algorithme.

     

De même, ils mettent en œuvre « est pas égal à » comme (a < b) || (b < a)   , Et encore une fois, si vous avez implémenté l'opérateur < utilisant <=, il   retourne vrai quand ils sont égaux entre eux, alors qu'en fait ils   ne sont pas égaux. Ainsi, le contrôle de l'égalité est brisée dans les deux sens.

     

Le point essentiel de limiter la bibliothèque à un opérateur inférieur est   que tous les opérateurs logiques peuvent être mis en œuvre en termes de celui-ci:

     

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

     

Cela fonctionne aussi longtemps que votre opérateur fourni remplit les conditions d'un   ordre strict faible. Les opérateurs standard <= et >= ne le font pas.

Answer 4

Vous ne pouvez pas effectuer une recherche binaire avec ordre partiel. Vous ne pouvez pas créer un arbre de recherche binaire avec ordre partiel. Quelles sont les fonctions / types de données de algorithme besoin de commande et peut travailler avec ordre partiel?