Cómo definir operador< en una n-tupla que satisface un orden débil estricto [duplicado]
¿Cómo definir operator<en n-tupla (por ejemplo, en 3-tupla) para que satisfaga el estricto concepto de ordenamiento débil ? Sé que la biblioteca boost tiene una clase tupla correctamente definida operator<, pero por alguna razón no puedo usarla.
orden débil estricto
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 tanto f(x, y) como f(y, x) son falsas. Tenga en cuenta que un objeto es siempre (por la invariante de irreflexividad) 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 de definir equivalente/menos depende totalmente del tipo de objeto.
Definición formal:
ordenamiento estricto y débil
Ciencias de la Computación:
Ordenamiento estricto y débil
Cómo se relaciona con los operadores:
Comparador
Como nota al margen, podemos implementar manualmente pedidos débiles estrictos. Pero podemos hacerlo simplemente usando el std::tupleque lo ha implementado para usted. Simplemente necesitas crear una tupla sin copiar los objetos.
struct S
{
ThingA a;
ThingB b;
};
bool operator<(S const& lhs, S const& rhs)
{
return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}
Nota: Esto supone que thingAellos thingBmismos ya implementan un orden débil estricto.
También podemos implementar la igualdad de la misma manera:
bool operator==(S const& lhs, S const& rhs)
{
return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b);
}
Nota nuevamente: esto supone que thingAya thingBimplementa la igualdad.
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 los elementos por ser a1 el más significativo y a3 el menos significativo.
Esto puede continuar hasta el infinito; también podría, por ejemplo, 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 sea 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.
[editar] eliminó el código incorrecto
[editar] si hay más que solo operator<disponible, tiendo a usar el patrón
if (a1 != b1)
return a1 < b1;
if (a2 != b2)
return a2 < b2;
...
...una nueva respuesta a una pregunta muy antigua, pero la respuesta existente pierde la solución fácil de C++11...
solución C ++ 11
C++ 11 en adelante proporciona std::tuple<T...>, que puede utilizar para almacenar sus datos. tupleLos s tienen una coincidencia operator<que inicialmente compara el elemento más a la izquierda y luego trabaja a lo largo de la tupla hasta que el resultado sea claro. Esto es adecuado para proporcionar el orden débil estricto que esperan, por ejemplo std::set, y std::map.
Si tiene datos en otras variables (por ejemplo, campos en a struct), puede incluso usarlos std::tie()para crear una tupla de referencias , que luego se puede comparar con otra tupla similar. Eso facilita la escritura para campos de datos de miembros específicos en un tipo / operator<definido por el usuario :classstruct
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_);
}
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 elementos sin que tengas que hacer nada.
Jun 11 '2009 07:06
El flujo básico debe ser del tipo siguiente: si los K-ésimos elementos son diferentes, devolver el que es más pequeño; de lo contrario, pasar al siguiente elemento . El siguiente código supone que no tienes una tupla de impulso, de lo contrario la usarías get<N>(tuple)y no tendrías el problema para empezar.
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;
