c++ - ordenamiento stl-estricto ordenamiento débil

algorithm strict-weak-ordering

Question

¿Por qué funciona STL con una función de comparación que es un ordenamiento estricto y débil ? ¿Por qué no puede ser orden parcial?

Answer 1

Citando la respuesta dada here :

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

Si usó <= para implementar el operador menor que, entonces lo anterior devolverá falso cuando a == b . Un chequeo de igualdad roto arruinará casi cualquier algoritmo.

Del mismo modo, implementan "no es igual a" como (a < b) || (b < a) (a < b) || (b < a) , y una vez más, si implementó el operador < utilizando <= , devolverá verdadero cuando sean iguales entre sí, cuando en realidad no son iguales. Así que el chequeo de igualdad se rompe en ambas direcciones.

El objetivo de limitar la biblioteca a un operador menor que es que todos los operadores lógicos pueden implementarse en términos de:

• <(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) : (b < a)
• >=(a, b) !(a < b)

Esto funciona siempre que su operador proporcionado cumpla con las condiciones de un estricto ordenamiento débil. Los operadores estándar <= y >= no lo hacen.

Answer 2

No se puede realizar una búsqueda binaria con orden parcial. No puede crear un árbol de búsqueda binario con orden parcial. ¿Qué funciones / tipos de datos del algoritmo necesitan ordenación y pueden funcionar con ordenamiento parcial?

Answer 3

Simplemente, un ordenamiento estricto débil se define como un ordenamiento que define una relación de equivalencia (computable) . Las clases de equivalencia están ordenadas por el ordenamiento estricto débil: un ordenamiento estricto débil es un ordenamiento estricto en las clases de equivalencia .

Un orden parcial (que no es un ordenamiento estricto débil) no define una relación de equivalencia, por lo que cualquier especificación que use el concepto de "elementos equivalentes" no tiene sentido con un ordenamiento parcial que no es un ordenamiento estricto débil. Todos los contenedores asociativos de STL utilizan este concepto en algún momento, por lo que todas estas especificaciones carecen de sentido con un pedido parcial que no es un pedido débil estricto.

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

Dado

• un conjunto matemático S
• un pedido parcial < sobre S
• un valor x en S

puede definir una partición de S (cada elemento de S está 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 se clasifica de acuerdo con < iff para cada x en la secuencia, los elementos de L(x) aparecen primero en la secuencia, seguidos de los elementos de I(x) , seguidos de los elementos de G(x) .

Una secuencia se clasifica topológicamente 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 estar ordenada.

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

Si < es un ordenamiento estricto, y x<y entonces cualquier elemento de L(x) UI(x) es menor que cualquier elemento I(y) UG(y) : cualquier elemento que no sea mayor que x es menor que cualquier elemento no menos que y . Esto no necesariamente es válido para un pedido parcial.

Answer 4

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