Operador https://stackoverflow.com/questions/979759

Question

¿Cómo definir operator< en n-tupla (por ejemplo, el 3-tupla) de manera que satisfaga estricta ordenación débil concepto? Yo sé que la biblioteca tiene clase impulso tupla con operator< correctamente definido, pero por alguna razón no puedo usarlo.

Answer 1

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

Esta ordena los elementos por a1 ser más siginificant y a3 menos significativo.

Esto se puede continuar hasta el infinito, que podría también, por ejemplo, aplicarlo a un vector de T, iterar sobre las comparaciones de a [i]

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 caro, es posible que desee almacenar en caché el resultado de la comparación.

---

[editar] eliminado código incorrecto

---

[editar] si algo más que operator< está disponible, tiendo a utilizar el patrón

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

Answer 2

estricta ordenación débil

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

  

dos objetos X e Y son equivalentes si tanto f (x, y) y f (y, x) son falsas. Tenga en cuenta que un objeto es siempre (por el invariante irreflexivity) equivalente a sí mismo.

En términos de C ++ esto significa que si tiene dos objetos de un tipo determinado, debe devolver los valores siguientes cuando se compara 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

¿Cómo se define equivalente / menos es totalmente dependiente del tipo de su objeto.

Definición formal:
estricto orden débil

Ciencias de la Computación:
estricto Débil Orden

¿Cómo se relaciona con los operadores:
Comparador

Answer 3

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

C ++ 11 solución

C ++ 11 proporciona en adelante std::tuple<T...> , que se puede utilizar para almacenar sus datos. tuples tienen una coincidencia de operator< que compara inicialmente la más a la izquierda elemento, luego trabaja a lo largo de la tupla hasta Está claro que el resultado. Eso es adecuado para proporcionar el estricta ordenación débil espera por ejemplo, std::set y std::map .

Si tiene datos en algunas otras variables (por ejemplo, campos de una struct), incluso se puede utilizar std::tie() que crea una tupla de referencias , que puede ser comparado con otro ejemplo tupla. Eso hace que sea fácil de escribir operator< para campos específicos de datos en miembro de un tipo class / struct definida 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 4

Usted podría simplemente utilizar vectores de tres elementos, que ya tendrá operador <() adecuadamente definida. Esto tiene la ventaja de que se extienda a N-elementos sin tener que hacer nada.

Answer 5

El flujo básico debe ser a lo largo de las líneas de: si los elementos de orden k son diferentes, retorno que es más pequeña cosa ir al siguiente elemento . El código siguiente se supone que No tiene una tupla impulso de lo contrario se utilizaría get<N>(tuple) y no tener el problema en primer lugar.

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 6

Incluso si no se puede utilizar la versión de impulso, debe ser capaz de nick del código. Me robé esto desde std :: pair - Una tupla 3 será similar supongo

.

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

Editar:. Como un par de personas han señalado, si robas código de la librería estándar para utilizar en su código, se debe cambiar el nombre de las cosas que tienen guiones en la parte delantera, ya que estos nombres se reservan