menos o less_equal Utilizando el montaje

Question

Nos puede pasar una función como < operador (menos) a las estructuras de datos STL como set, multiset, map, priority_queue, ...

¿Hay un problema si nuestra función actúa como <= (menos_equal)?

Answer 1

desde STL eficaz -> TEMA 21. Siempre tienen funciones de comparación return false por la igualdad de valores.

Crear un conjunto donde less_equal es el tipo de comparación, a continuación, insertar 10 en el conjunto:

set<int, less_equal<int> > s; // s is sorted by "<=" 
s.insert(10); //insert the value 10 

Ahora intenta insertar 10 de nuevo:

s.insert(10); 

Para la presente convocatoria para insertar, el conjunto tiene para averiguar si 10 ya está presente. Sabemos que es. pero el conjunto es tonto como una tostada, por lo que tiene que comprobar. Para que sea más fácil de entender lo que sucede cuando el conjunto hace esto, vamos a llamar a los 10 que inicialmente fue insertada 10A y los 10 que estamos tratando de insertar 10B.The conjunto se ejecuta a través de sus estructuras internas de datos en busca de la lugar para insertar 10B. Finalmente tiene que verificar 10B para ver si es igual a 10A. La definición de "el mismo" para contenedores asociativos es la equivalencia, por lo que el conjunto prueba si 10B es equivalente a 10A. Al realizar esta prueba, naturalmente usa la función de comparación del conjunto. En este ejemplo, ese es el operador < =, porque especificamos less_equal como la función de comparación del conjunto, y less_equal significa operadores. El conjunto lo tanto comprueba si esta expresión es verdadera:

!(10A<= 10B)&&!(10B<= 10A) //test 10Aand 10B for equivalence 

Bueno, 10A y 10B son ambos de 10 años, por lo que es claramente cierto que < 10A = 10B. Igualmente claro, 10B < = 10A. La expresión anterior se simplifica así a

!!(true)&&!(true) 

y que se simplifica a

false && false 

que es simplemente falso. Es decir, el conjunto concluye que 10A y 10B no son equivalentes, por lo tanto, no la misma, y ​​por lo tanto se va sobre la inserción 10B en el recipiente junto 10A. Técnicamente, esta acción produce un comportamiento indefinido, pero el resultado casi universal es que el conjunto termina con dos copias del valor 10, y eso significa que no es un conjunto por más tiempo. Al usar less_equal como nuestro tipo de comparación, hemos corrompido el contenedor . Además, cualquier función de comparación donde los valores iguales devuelvan verdadero hará lo mismo. Los valores iguales son, por definición, ¡no equivalentes!

Answer 2

De hecho, hay un problema.

La función de comparación debe satisfacer strict weak ordering cuales <= no.

Answer 3

Sí, hay un problema.

Formalmente, la función de comparación debe definir un estricto orden débil, y <= no hace eso.

más específicamente, la < también se utiliza para determinar la equivalencia (x y y son equivalentes si y sólo si !(x < y) && !(y < x)). Esto no es válido para <= (usar ese operador haría que su conjunto creara que los objetos son nunca equivalente)