Clasificación solo usando el operador menos que el operador en comparación con una función de comparación de trivalue

Question

En C ++/STL, la clasificación se realiza utilizando solo el operador menos que el operador. Sin embargo, no tengo idea de cómo se implementan realmente los algoritmos de clasificación, supongo que las otras operaciones se crean implicitas:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

En comparación con el uso de una función de comparación de trivalue*, como por ejemplo, Java, ¿es esto bueno para el rendimiento o por qué se tomó esta decisión de diseño?

Supongo que cualquier función de comparación de trivalue aún tiene que implementar estos comparaciones en sí mismo, lo que resulta en el mismo rendimiento.

** Por Trivalue Compare la función, me refiero a una función de comparación que devuelve -1, 0 y 1 por menos de, igual y más alto que*

Actualizar:Parece una nave espacial <=> El operador viene en C ++ 20, así que obviamente el comité pensó que había inconvenientes de usar solo operator<.

Answer 1

En cierto sentido, los otros dos están implícitos, pero más preciso sería decir que un tipo de comparación en realidad no necesitar Un comparador con valor tri, y los tipos de C ++ se implementan de una manera que no usa uno para minimizar el comportamiento requerido del comparador.

Estaría mal para std :: sort para definir y usar exclusivamente algo como esto:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... porque terminarías con un algoritmo ineficiente en términos de número de llamadas a lessthan. Si su algoritmo no hace nada útil con la diferencia entre un retorno de 1 y un retorno de 0, entonces ha desperdiciado una comparación.

C ++ se refiere a "ordenos débiles estrictos". Si < es un orden débil estricto, y !(a < b) && !(b < a), no lo hace necesariamente sigue eso a == b. Solo están "en el mismo lugar" en el pedido, y !(a < b) && !(b < a) es una relación de equivalencia. Entonces el comparador requerido por sort pedidos clases de equivalencia de objetos, no proporciona un orden total.

La única diferencia que hace es lo que dices cuando !(a < b). Para un pedido total estricto, deduciría b <= a, lea "menos o igual a". Para un orden débil estricto, no puedes definir b <= a significar b < a || b == a y que esto sea cierto. C ++ es pedante sobre esto, y dado que permite que la sobrecarga del operador sea bastante tiene que serlo, ya que las personas sobrecargan los operadores necesitan la jerga para decirle a los usuarios sobre su código lo que pueden esperar en términos de cómo se relacionan los operadores. Java habla de que el comparador y el hashcode son consistentes con iguales, que es todo lo que necesita. C ++ tiene que lidiar con <,>, ==, <=,> =, la condición posterior de la asignación, etc.

C ++ adopta un enfoque matemático bastante puro para esto en la API, por lo que todo se define en términos de la relación binaria única. Java es más amigable en algunos aspectos, y prefiere comparaciones de tres vías donde la definición de la unidad fundamental (la comparación) es un poco más compleja, pero la lógica que conduce desde ella es más simple. También significa que el algoritmo de clasificación obtiene más información por comparación, lo que ocasionalmente es útil. Para obtener un ejemplo, consulte la optimización de Quicksort "Flag", que es un beneficio cuando hay muchos duplicados "en el mismo lugar" en los datos.

En ese caso, un comparador de tres valores es una ganancia de velocidad. Pero C ++ utiliza una definición consistente de un comparador para la clasificación y también para set y map, lower_bound y así sucesivamente, que apenas se beneficia de un comparador de tres valores (tal vez guarde una comparación, tal vez no). Supongo que decidieron no complicar su interfaz general agradable en aras de las ganancias de eficiencia potencial específicas o limitadas.

Answer 2

Supongo que en C ++ se hizo solo para reducir la duplicación de código: una vez que define una OP de comparación en una clase/tipo, no solo puede comparar esos objetos simplemente escribiendo A <B, sino que también obtiene la capacidad de ordenar conjuntos de conjuntos de conjuntos de conjuntos de conjuntos de conjuntos de conjuntos de conjuntos de conjuntos tales objetos.

En cuanto a la clasificación, solo necesitamos un operador menos que un operador, ¿por qué introducir cosas adicionales? :)

Answer 3

Si se refiere a std :: sort (), su uso solo () operador porque no necesita preservar el orden relativo del elemento equivalente, por lo que necesitará menos () operador e operador implícitamente mayor ().

mientras que std :: stable_sort lo conservará, pero es más lento. Necesita menos () operador y iterador bidireccional a cambio de que el operador igual () construya la función "trivalue" de comparación