Implementación preferida de '<' para estructuras multivariables

Question

Inicialmente, esto puede parecer demasiado abstracto o filosófico, pero estoy realmente interesado en ver si alguien tiene un argumento convincente a favor de una implementación sobre la otra.

Dada operator< para std::pair<T1, T2>, que sería la mejor aplicación:

return x.first < y.first || 
     x.first == y.first && x.second < y.second; 

o:

return x.first < y.first || 
     !(y.first < x.first) && x.second < y.second; 

Mi entendimiento es que las dos implementaciones resultados equivalentes. ¿Se prefiere este último porque está definido únicamente en términos de operator<? ¿O es legítimo suponer que un tipo que es menos que comparativo también debe ser comparable a la igualdad? ¿Alguien más ve otro punto que lo influenciaría entre uno y otro?

Naturalmente, cualquier respuesta debe ser tanto genérica como extensible. Entonces, ¿cuál usarías y por qué? ¿Hay una implementación diferente que sea incluso mejor que la anterior?

Answer 1

No es legítimo suponer que para cualquier tipo , si es menor de lo comparable, es también la igualdad comparables, ya que uno puede sobrecargar operator< pero no sobrecargar operator==.

Por lo tanto, si prevé tener que manejar tipos definidos por el usuario, es preferible el segundo enfoque. Sin embargo, debe agregar algunos paréntesis para aclarar el orden de las operaciones:

return x.first < y.first || 
     (!(y.first < x.first) && x.second < y.second); 

Answer 2

La implementación no son equivalentes si el operador < representa un ordenamiento débil. Por ejemplo, imagine que los objetos de T1 son nodos en un dígrafo y T1a < T1d significa que "T1a es un ancestro de T1b en el gráfico" (esta no es una notación tan poco común).

Entonces: !(T1b < T1a) significaría "T1b no es un antepasado de T1a" así que o:

1. T1a es un antepasado de T1b (descartado por la primera prueba)
2. T1a es el mismo nodo que T1b
3. T1a y T1b no son comparables (es decir, que son hermanos)

Este tercer caso es realmente importante. En ese caso, es probable que desee que el operador < devuelva falso en el par, pero puede que no.

(A pedido débil en un conjunto de elementos significa que a <= b y b <= a tanto puede ser falsa.)

Personalmente, no soy aficionado a la sobrecarga de operadores, especialmente cuando se usa con los genéricos. Los programadores tienden a asumir buenas propiedades "aritméticas" que no siempre se mantienen.

Answer 3

¡Utilizaría el segundo, porque eso es lo que especifica el estándar!

Las dos definiciones son, como ya se ha mencionado, equivalentes, siempre que < defina un pedido total en ambos tipos y == sea coherente con <.Pero cuando ninguna de las dos es verdadera, la diferencia es observable y si usaste la primera definición no estarías cumpliendo.

EDIT: La definición estándar es mejor que su primera definición en un sentido: si < define un ordenamiento estricto débil tanto en T1 y T2, entonces la definición estándar da un estricto orden débil sobre pair<T1, T2>. Su primera definición no, y esto puede causar problemas reales. Por ejemplo, supongamos que tenemos xey de modo que ni x < y ni y < x. Luego considere la matriz de pares a[3] = {P(x, 2), P(y, 1), P(x, 1)}. Claramente deberíamos decir que este conjunto es no ordenado en orden ascendente, porque a[2] < a[0]. Pero si usamos su primera definición, std::is_sorted concluiría que la matriz es ordenada, porque no hay dos elementos consecutivos comparables. El hecho de que la primera definición no sea un orden estricto y débil rompe el algoritmo. Según la definición estándar, P(y, 1) < P(x, 2), el algoritmo detecta que la matriz no está ordenada como se desea.

(Esta respuesta tenía previamente un análisis totalmente incorrecto de esta situación - lo siento)