STL pedido - ordenamiento débil estricto

Question

¿Por qué funciona STL con una función de comparación que es href="http://en.wikipedia.org/wiki/Strict_weak_ordering" estricta débil ordenamiento ? Por qué no puede ser ordenación parcial?

Answer 1

A orden parcial no sería suficiente para aplicar algunos algoritmos, tales como un algoritmo de clasificación. Dado un conjunto parcialmente ordenado no necesariamente define una relación entre todos los elementos del conjunto, ¿cómo ordenar una lista de dos elementos que no tienen una relación de orden dentro del orden parcial?

Answer 2

Simplemente, una estricta ordenamiento débil se define como un ordenamiento que define una relación (computable) equivalencia . Las clases de equivalencia son ordenados por el estricto ordenamiento débil:. un ordenamiento estricto débil es una ordenación estricta en clases de equivalencia

A ordenación parcial (que no es un ordenamiento débil estricto) no define una relación de equivalencia, de modo cualquier especificación utilizando el concepto de "elementos equivalentes" no tiene sentido con una ordenación parcial que no es un ordenamiento débil estricto. todos los contenedores STL asociativos utilizar este concepto en algún momento, por lo que todas estas especificaciones no tienen sentido con un orden parcial que no es un ordenamiento débil estricto.

Debido a que una ordenación parcial (que no es un ordenamiento débil estricto) no necesariamente define ningún orden estricto, no se puede "ordenar los elementos" en el sentido común de acuerdo con la ordenación parcial (todo lo que se puede hacer es una "clasificación topológica", que tiene propiedades más débiles).

Dado

• un conjunto S matemática
• a < ordenación parcial sobre S
• a x valor en S

se puede definir una partición de S (todos los elementos de S es ya sea en L(x), I(x) o 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

Una secuencia está ordenada de acuerdo con < si y sólo si para cada x en la secuencia, elementos de L(x) aparecen primero en la secuencia, seguido por elementos de I(x), seguidos por elementos de G(x).

Una secuencia se ordena topológicamente si y sólo si para cada elemento y que aparece después de otro elemento x en la secuencia, y no es menor que x. Es una restricción más débil que ser ordenados.

Es trivial para demostrar que todos los elementos de L(x) es menor que cualquier elemento de G(x). No hay relación general entre los elementos de L(x) y elementos de I(x), o entre los elementos de I(x) y elementos de G(x). Sin embargo, si < es un ordenamiento estricto débil, que todos los elementos de L(x) es menor que cualquier elemento de I(x), y que cualquier elemento de I(x) es menor que cualquier elemento de G(x).

Si < es un ordenamiento débil estricto, y x<y entonces cualquier elemento de L(x) U I(x) es inferior a cualquier elemento I(y) U G(y): cualquier elemento no es mayor que x es menor que cualquier elemento no menos que y. Esto no necesariamente válida para una ordenación parcial.

Answer 3

Citando la respuesta dada aquí :

  

Debido a que internamente, estos algoritmos implementan "es igual a" como !(a < b) && !(b < a).

     

Si ha utilizado <= para implementar el operador menor que, a continuación de lo anterior   volvería falsa cuando a == b. Una verificación de la igualdad rota arruine   casi cualquier algoritmo.

     

Del mismo modo, implementan "no es igual a" como (a < b) || (b < a)   , Y una vez más, si el operador implementado usando < <=, entonces   devolverá true cuando son iguales entre sí, cuando en realidad   no son iguales. Por lo que la comprobación de igualdad se rompe en ambas direcciones.

     

El punto de la limitación de la biblioteca a un operador menor que es   que todos los operadores lógicos se pueden implementar en cuanto a que:

     

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

     

Esto funciona siempre y cuando el usuario a que se cumpla con las condiciones de una   ordenamiento estricto débil. Los <= y >= operadores estándar no lo hacen.

Answer 4

No se puede realizar la búsqueda binaria con la ordenación parcial. No se puede crear un árbol de búsqueda binaria con la ordenación parcial. ¿Qué tipos de datos de funciones / algoritmo necesitan pedidos y puede trabajar con orden parcial?