¿Cómo se escribe un operador() o menos que functor más limpio que una función de comparación de trivalo

Question

Escribir un operador <() para una estructura parece ser más claro que escribir la comparación trivalente clásica.

por ejemplo, para ordenar el siguiente

struct S { 
    int val; 
}; 

puede escribir un operador <()

bool operator< (const S &l, const S &r) { 
    return l.val < r.val; 
} 

o, un función trivalue (generalmente de la siguiente manera)

int compare(const S &l, const S &r) { 
    if(r.val > l.val) return 1; 
    if(r.val < l.val) return -1; 
    return 0; 
} 

La primera es más clara, por lo tanto, puede decir que hay mejor calidad de código. Esto último le obliga a pensar en 3 casos, lo que complica el código.

Pero este pensamiento es un poco engañoso en estructuras más complejas:

struct S { 
    int x; 
    int y; 
}; 

la siguiente es clara, y begginners tienden a escribirlo como tal

bool operator< (const S &l, const S &r) { 
    if(l.x < r.x) return true; 
    if(l.y < r.y) return true; 
    return false; 
} 

pero es mal! ¡No puedes ordenar correctamente con esto!

Y se necesita algo de tiempo para pensar que que realmente tiene que escribirlo así como

bool operator< (const S &l, const S &r) { 
    if(l.x < r.x) return true; 
    if(l.x > r.x) return false; 
    if(l.y < r.y) return true; 
    if(l.y > r.y) return false; 
    return false; 
} 

para que funcione correctamente.

¿Puede usted, y hacer escribir este tipo de función de comparación de una manera más agradable/más clara? La función de comparación trivalue anterior al menos le "forzó" a pensar en>, < y == casos.

Answer 1

La cosa es que usted está muy bien con sólo declarar una trivalue comparar función si AutoGenerate todos los operadores usando: http://en.wikipedia.org/wiki/Barton%E2%80%93Nackman_trick

Answer 2

me gusta hacerlo de esta manera:

bool operator< (const S &l, const S &r) 
{ 
    if(l.x != r.x) return l.x < r.x; 
    else return l.y < r.y; 
} 

EDIT: tenga en cuenta que esta también es una característica útil de std::pair, ya lo define para que no pueda cometer el error.

Answer 3

En el caso int simplemente hay que escribir:

return l.x < r.x || (l.x == r.x && l.y < r.y); 

Sólo de la que está hablando acerca de un tipo que no tiene == con el comportamiento correcto hacerlo es necesario utilizar algo más complejo, incluso entonces es No está mal.

return l.x < r.x || (!(r.x < l.x) && l.y < r.y); 

se extiendan a más miembros:

si se puede organizar a sus miembros a estar en una matriz o cualquier otro recipiente que puede utilizar std::lexicographical_compare.

Answer 4

Una cosa que hice una vez que me pareció una expresión útil fue escribir una función de comparación que devuelve un booleano dado toma dos argumentos más un booleano llamado "bias". La función devuelve verdadero si el primer argumento es mayor, o si se establece "bias" y los dos argumentos son iguales. Por lo tanto, un comparar cuyo resultado dependía de dos sub-comparaciones serían:

 
    if (compare(a.part1,b.part1,compare(a.part2,b.part2,bias))) 
    ... 

Tenga en cuenta que esto va a hacer comparaciones 'extra', ya parte2 de serán comparados incluso si el part1 comparar sería suficiente para producir una respuesta, pero si evita las pruebas redundantes de igualdad.

De lo contrario, usando la lógica tri-valor, se podría hacer algo como:

 
    int result; 

    if ((result = compare(a.part1,b.part1)) != 0) return result; 
    if ((result = compare(a.part2,b.part2)) != 0) return result; 

Esta última forma se evita comparaciones innecesarias, y es fácilmente extensible a cualquier número de campos.

Answer 5

Si no se preocupan por el rendimiento o compilador arrojan, que tienden a utilizar esto:

return make_tuple(l.x, l.y, ...) < make_tuple(r.x, r.y, ...); 

Y por un poco menos caro en términos de la versión copias:

return tie(cref(l.x), cref(l.y), ...) < tie(cref(r.x), cref(r.y), ...); 

Por cierto, la segunda versión también funciona con lvalues.

Answer 6

Por primera tri-valor compare() función

int compare(const S &l, const S &r) { 
    return r.val - l.val; 
} 

Por la tarde

bool operator< (const S &l, const S &r) { 
    return (l.x < r.x) || ((l.x == r.x) && (l.y < r.y)); 
} 

Answer 7

Esto no es más clara o más corto que el último ejemplo, pero tiene la ventaja de no requiriendo cualquier cosa que no sea operator< en los miembros.

bool operator< (const S &l, const S &r) { 
    if(l.x < r.x) return true; 
    if(r.x < l.x) return false; 
    if(l.y < r.y) return true; 
    if(r.y < l.y) return false; 
    return false; 
} 

El último caso siempre se puede simplificar, lamentablemente los casos anteriores siempre deben ser de forma más larga.

bool operator< (const S &l, const S &r) { 
    if(l.x < r.x) return true; 
    if(r.x < l.x) return false; 
    return l.y < r.y; 
}