c++ - Operador<y estricto orden débil

strict-weak-ordering

Question

¿Cómo definir operator< en n-tuple (por ejemplo en 3-tuple) para que satisfaga el concepto estricto de orden débil ? Sé que la biblioteca de impulso tiene una clase de tupla con un operator< correctamente definido operator< pero por algunas razones no puedo usarlo.

Answer 1

estricto orden débil

Este es un término matemático para definir una relación entre dos objetos.
Su definición es:

Dos objetos xey son equivalentes si ambos f (x, y) yf (y, x) son falsos. Tenga en cuenta que un objeto es siempre (por la irreflexividad invariante) equivalente a sí mismo.

En términos de C ++, esto significa que si tiene dos objetos de un tipo determinado, debe devolver los siguientes valores en comparación con el operador <.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

La forma en que defines equivalente / menos depende totalmente del tipo de tu objeto.

Verifique la página de SGI sobre el tema:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

Answer 2

El flujo básico debería estar en la línea de: si los elementos Kth son diferentes, el retorno que es más pequeño va al siguiente elemento . El siguiente código supone que no tiene una tupla boost, de lo contrario, debería usar get<N>(tuple) y no tener el problema para comenzar.

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

Answer 3

Incluso si no puede usar la versión de refuerzo, debería poder copiar el código. Lo corté de std :: pair - una 3 tupla será similar, supongo.

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

Editar: Como han señalado algunas personas, si robas código de la biblioteca estándar para usar en tu código, debes cambiar el nombre de las cosas que tienen caracteres de subrayado en el frente ya que estos nombres están reservados.

Answer 4

Simplemente podría usar vectores de tres elementos, que ya tendrán el operador <() adecuadamente definido. Esto tiene la ventaja de que se extiende a N-elements sin que tengas que hacer nada.

Answer 5

... una nueva respuesta a una pregunta muy antigua, pero la respuesta existente omite la solución fácil de C ++ 11 ...

Solución C ++ 11

C ++ 11 en adelante proporciona std::tuple<T...> , que puede usar para almacenar sus datos. tuple tienen un operator< coincidente operator< que inicialmente compara el elemento situado más a la izquierda, luego trabaja a lo largo de la tupla hasta que queda claro el resultado. Eso es adecuado para proporcionar el ordenamiento débil estricto esperado, por ejemplo, std::set y std::map .

Si tiene datos en algunas otras variables (por ejemplo, campos en una struct ), puede incluso usar std::tie() para crear una tupla de referencias , que luego se puede comparar con otra tupla. Eso hace que sea fácil escribir operator< para campos de datos de miembros específicos en un tipo de class / struct definido por el usuario:

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

Answer 6

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

Esto ordena que los elementos sean a1 más significativos y a3 menos significativos.

Esto puede continuarse hasta el infinito, también podrías aplicarlo a un vector de T, iterando sobre comparaciones de a [i] <a [i + 1] / a [i + 1] <a [i]. Una expresión alternativa del algoritmo sería "omitir mientras es igual, luego comparar":

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Por supuesto, si la comparación es costosa, es posible que desee almacenar en caché el resultado de la comparación.

[edit] eliminado el código incorrecto