Operador que define <para una estructura

Question

A veces uso pequeñas structs como claves en los mapas, por lo que tengo que definir un operator< para ellas. Por lo general, esto termina pareciéndose a algo como esto:

struct MyStruct 
{ 
    A a; 
    B b; 
    C c; 

    bool operator<(const MyStruct& rhs) const 
    { 
     if (a < rhs.a) 
     { 
      return true; 
     } 
     else if (a == rhs.a) 
     { 
      if (b < rhs.b) 
      { 
       return true; 
      } 
      else if (b == rhs.b) 
      { 
       return c < rhs.c; 
      } 
     } 

     return false; 
    } 
}; 

Esto parece terriblemente prolijo y propenso a errores. ¿Hay una mejor manera, o de alguna manera fácil de automatizar definición de operator< para un struct o class?

Sé que algunas personas como para simplemente usar algo como memcmp(this, &rhs, sizeof(MyStruct)) < 0, pero esto puede no funcionar correctamente si hay bytes de relleno entre los miembros, o si hay char matrices de cadenas que pueden contener la basura después de que los terminadores nulos.

Answer 1

esto es muy una vieja cuestión y, como consecuencia todas las respuestas aquí son obsoletas. C++ 11 permite una solución más elegante y eficaz:

bool operator <(const MyStruct& x, const MyStruct& y) { 
    return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c); 
} 

¿Por qué es esto mejor que el uso de boost::make_tuple? Porque make_tuple creará copias de todos los miembros de datos, lo que puede ser costoso. std::tie, por el contrario, creará un envoltorio delgado de referencias (que el compilador probablemente optimizará completamente).

De hecho, el código anterior debe ahora ser considerada la solución idiomática a la implementación de un lexicográfico comparación de estructuras con varios miembros de datos.

Answer 2

La mejor manera que conozco es utilizar un boost tuple. Ofrece entre otros una comparación y constructores integrados.

#include <boost/tuple/tuple.hpp> 
#include <boost/tuple/tuple_comparison.hpp> 

typedef boost::tuple<int,int,int> MyStruct; 

MyStruct x0(1,2,3), x1(1,2,2); 
if(x0 < x1) 
    ... 

también me gusta Mike Seymors suggestion to use temporary tuples through boost's make_tuple

Answer 3

En este caso se puede usar boost::tuple<int, int, int> - operator< sus trabajos de la manera que desee.

Answer 4

Me gustaría hacer esto:

#define COMPARE(x) if((x) < (rhs.x)) return true; \ 
        if((x) > (rhs.x)) return false; 
COMPARE(a) 
COMPARE(b) 
COMPARE(c) 
return false; 
#undef COMPARE 

Answer 5

Otros han mencionado boost::tuple, que le da una comparación lexicográfica. Si desea mantenerlo como una estructura con elementos nombrados, puede crear tuplas temporales para la comparación:

bool operator<(const MyStruct& x, const MyStruct& y) 
{ 
    return boost::make_tuple(x.a,x.b,x.c) < boost::make_tuple(y.a,y.b,y.c); 
} 

En C++ 0x, esto se convierte en std::make_tuple().

ACTUALIZACIÓN: Y ahora C++ 11 está aquí, se convierte en std::tie(), para hacer una tupla de referencias sin copiar los objetos. Vea la nueva respuesta de Konrad Rudolph para más detalles.

Answer 6

Escribí un guión de Perl para ayudarme. Por ejemplo dado:

class A 
{ 
int a; 
int b; 
int c; 

emitiría:

bool operator<(const A& left, const A& right) 
{ 
    bool result(false); 

    if(left.a != right.a) 
    { 
     result = left.a < right.a; 
    } 
    else if(left.b != right.b) 
    { 
     result = left.b < right.b; 
    } 
    else 
    { 
     result = left.c < right.c; 
    } 

    return result; 
} 

de código (que es un poco largo):

#!/usr/bin/perl 

use strict; 

main: 

my $line = <>; 
chomp $line; 
$line =~ s/^ *//; 

my ($temp, $line, $temp) = split//, $line; 

print "bool operator<(const $line& left, const $line& right)\n{\n"; 
print " bool result(false);\n\n"; 

my $ifText = "if"; 

$line = <>; 

while($line) 
{ 
    if($line =~ /{/) 
    { 
     $line = <>; 
     next; 
    } 
    if($line =~ /}/) 
    { 
     last; 
    } 

    chomp $line; 
    $line =~ s/^ *//; 

    my ($type, $name) = split//, $line; 
    $name =~ s/; *$//; 

    $line = <>; 
    if($line && !($line =~ /}/)) 
    { 
     print " $ifText(left.$name != right.$name)\n"; 
     print " {\n"; 
     print "  result = left.$name < right.$name;\n"; 
     print " }\n"; 

     $ifText = "else if"; 
    } 
    else 
    { 
     print " else\n"; 
     print " {\n"; 
     print "  result = left.$name < right.$name;\n"; 
     print " }\n"; 

     last; 
    } 
} 

print "\n return result;\n}\n"; 

Answer 7

#include <iostream> 

#include <boost/fusion/include/adapt_struct.hpp> 
#include <boost/fusion/include/less.hpp> 

struct MyStruct { 
    int a, b, c; 
}; 

BOOST_FUSION_ADAPT_STRUCT(MyStruct, 
          (int, a) 
          (int, b) 
          (int, c) 
         ) 

bool operator<(const MyStruct &s1, const MyStruct &s2) 
{ 
    return boost::fusion::less(s1, s2); 
} 

int main() 
{ 
    MyStruct s1 = { 0, 4, 8 }, s2 = { 0, 4, 9 }; 
    std::cout << (s1 < s2 ? "is less" : "is not less") << std::endl; 
} 

Answer 8

bool operator <(const A& l, const A& r) 
{ 

    int[] offsets = { offsetof(A, a), offsetof(A, b), offsetof(A, c) }; 
    for(int i = 0; i < sizeof(offsets)/sizeof(int); i++) 
    { 
     int ta = *(int*)(((const char*)&l)+offsets[i]); 
     int tb = *(int*)(((const char*)&r)+offsets[i]); 

     if (ta < tb) 
      return true; 
     else if (ta > tb) 
      break; 

    } 
    return false; 
} 

Answer 9

si no se puede utilizar impulso , podrías intentar algo como:

#include <iostream> 

using namespace std; 

template <typename T> 
struct is_gt 
{ 
    is_gt(const T& l, const T&r) : _s(l > r) {} 

    template <typename T2> 
    inline is_gt<T>& operator()(const T2& l, const T2& r) 
    { 
    if (!_s) 
    { 
     _s = l > r; 
    } 
    return *this; 
    } 

    inline bool operator!() const { return !_s; } 

    bool _s; 
}; 

struct foo 
{ 
    int a; 
    int b; 
    int c; 

    friend bool operator<(const foo& l, const foo& r); 
}; 

bool operator<(const foo& l, const foo& r) 
{ 
    return !is_gt<int>(l.a, r.a)(l.b, r.b)(l.c, r.c); 
} 

int main(void) 
{ 
    foo s1 = { 1, 4, 8 }, s2 = { 2, 4, 9 }; 
    cout << "s1 < s2: " << (s1 < s2) << endl; 
    return 0; 
} 

Supongo que esto evita cualquier macro, y siempre que los tipos en la estructura sean compatibles con <, debería funcionar. Por supuesto, hay una sobrecarga para este enfoque, la construcción de ramas is_gt y luego superflous para cada parámetro si uno de los valores es mayor ...

Editar:

modifica en función de los comentarios, esta versión debe ahora cortocircuito así, ahora utiliza dos Bools para mantener el estado (no estoy seguro que hay una manera de hacer esto con una sola bool).

template <typename T> 
struct is_lt 
{ 
    is_lt(const T& l, const T&r) : _s(l < r), _e(l == r) {} 

    template <typename T2> 
    inline bool operator()(const T2& l, const T2& r) 
    { 
    if (!_s && _e) 
    { 
     _s = l < r; 
     _e = l == r; 
    } 
    return _s; 
    } 

    inline operator bool() const { return _s; } 

    bool _s; 
    bool _e; 
}; 

y

bool operator<(const foo& l, const foo& r) 
{ 
    is_lt<int> test(l.a, r.a); 
    return test || test(l.b, r.b) || test(l.c, r.c); 
} 

acaba de crear una colección de tales palabras funcionales para diversas comparaciones ..

Answer 10

Cuando se puede producir iteradores más de los elementos que definen el orden lexicográfico puede utilizar std::lexicographic_compare, desde <algorithm>.

De lo contrario, sugiero basar las comparaciones en las antiguas funciones de comparación de tres valores, p. Ej. de la siguiente manera:

#include <iostream> 

int compared(int a, int b) 
{ 
    return (a < b? -1 : a == b? 0 : +1); 
} 

struct MyStruct 
{ 
    friend int compared(MyStruct const&, MyStruct const&); 
    int a; 
    int b; 
    int c; 

    bool operator<(MyStruct const& rhs) const 
    { 
     return (compared(*this, rhs) < 0); 
    } 
}; 

int compared(MyStruct const& lhs, MyStruct const& rhs) 
{ 
    if(int x = compared(lhs.a, rhs.a)) { return x; } 
    if(int x = compared(lhs.b, rhs.b)) { return x; } 
    if(int x = compared(lhs.c, rhs.c)) { return x; } 
    return 0; 
} 

int main() 
{ 
    MyStruct const s1 = { 0, 4, 8 }; 
    MyStruct const s2 = { 0, 4, 9 }; 
    std::cout << (s1 < s2 ? "is less" : "is not less") << std::endl; 
} 

que incluía if la última y return en la función compare sólo para la generalidad. Imagino que puede ayudar a que el mantenimiento se adhiera muy rígidamente a un solo sistema. De lo contrario, podría hacer un return compared(lhs.c, rhs.c) allí (y tal vez prefiera eso).

Saludos & HTH,

-. Alf

Answer 11

Me acaban de aprender el truco boost::tuple, gracias, @ Mike Seymour!

Si usted no puede permitirse Boost, mi lenguaje favorito es:

bool operator<(const MyStruct& rhs) const 
{ 
    if (a < rhs.a) return true; 
    if (a > rhs.a) return false; 

    if (b < rhs.b) return true; 
    if (b > rhs.b) return false; 

    return (c < rhs.c); 
} 

que me gusta porque pone todo en estructura paralela que comete errores y omisiones más fáciles de detectar.

Pero, por supuesto, usted está probando esto de todos modos, ¿verdad?

Answer 12

Si las comparaciones tripartitas son más costosas que las bidireccionales, y si las porciones más significativas de las estructuras a menudo serán iguales, puede ser útil definir funciones de comparación de campo con un parámetro 'sesgo', tal que si 'sesgo' es falso, devolverá verdadero cuando a> b, y cuando el sesgo sea verdadero, devolverá verdadero si a> = b. Entonces uno puede saber si a> b haciendo algo como:

 
    return compare1(a.f1,b.f1, compare2(a.f2,b.f2, compare3(a.f3,b.f3,false))); 

Tenga en cuenta que se llevarán a cabo todas las comparaciones, incluso si a.f1 <> b.f1 comparaciones, pero será de dos vías en lugar de tres -camino.

Answer 13

Creo que la manera más fácil es seguir con el operador < para todas las comparaciones y no utilizar> o ==.A continuación se muestra el patrón sigo, y usted puede seguir para todas sus estructuras

typedef struct X 
{ 
    int a; 
    std::string b; 
    int c; 
    std::string d; 

    bool operator <(const X& rhs) const 
    { 
     if (a < rhs.a) { return true; } 
     else if (rhs.a < a) { return false; } 

     // if neither of the above were true then 
     // we are consdidered equal using strict weak ordering 
     // so we move on to compare the next item in the struct 

     if (b < rhs.b) { return true; } 
     if (rhs.b < b) { return false; } 

     if (c < rhs.c) { return true; } 
     if (rhs.c < c) { return false; } 

     if (d < rhs.d) { return true; } 
     if (rhs.d < d) { return false; } 

     // if both are completely equal (based on strict weak ordering) 
     // then just return false since equality doesn't yield less than 
     return false; 
    } 
}; 

Answer 14

por lo general poner en práctica orden lexicográfico de esta manera:

bool operator < (const MyObject& obj) 
{ 
    if(first != obj.first){ 
     return first < obj.first; 
    } 
    if(second != obj.second){ 
     return second < obj.second; 
    } 
    if(third != obj.third){ 
     return third < obj.third 
    } 
    ... 
} 

mente que se necesita una consideración adicional para los valores de punto flotante (advertencias G ++), para los que algo como esto sería mejor:

bool operator < (const MyObject& obj) 
{ 
    if(first < obj.first){ 
     return true; 
    } 
    if(first > obj.first){ 
     return false; 
    } 
    if(second < obj.second){ 
     return true; 
    } 
    if(second > obj.second){ 
     return false; 
    } 
    ... 
}