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

Question

Como definir operator< em n-tupla (por exemplo, 3-tupla) para que ele satisfazer estrita fraca ordenação conceito? Eu sei que a biblioteca boost tem classe tupla com operator< corretamente definido, mas por algumas razões eu não posso usá-lo.

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

Este ordens os elementos por a1 sendo mais siginificant e a3 menos significativos.

Isso pode ser continuado ad infinitum, você também pode, por exemplo, aplicá-lo a um vector de T, a iteração através de comparações 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];

É claro que, se a comparação for caro, você pode querer armazenar em cache o resultado da comparação.

---

[editar] código errado removido

---

[editar] se mais do que apenas operator< está disponível, que tendem a usar o padrão

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

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

...

Answer 2

rigorosa ordenação fraco

Este é um termo matemático para definir uma relação entre dois objetos.
Sua definição é:

dois objetos x e y são equivalentes se ambos f (x, y) e f (y, x) são falsas. Note-se que um objeto é sempre (pelo invariante irreflexibilidade) equivalente a si mesmo.

Em termos de C ++ Isto significa que se você tem dois objetos de um determinado tipo, você deve retornar os seguintes valores quando comparado com o 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

Como você define equivalente / menos é totalmente dependente do tipo do seu objeto.

Definição Formal:
ordenação fraco Strict

Ciência da Computação:
Strict Ordenação fraco

Como se refere aos operadores:
Comparador

Answer 3

... uma nova resposta a uma pergunta muito antiga, mas a falta de resposta existente a solução fácil do C ++ 11 ...

C ++ 11 solução

C ++ 11 fornece diante std::tuple<T...> , que você pode usar para armazenar seus dados. tuples têm uma correspondência operator< que, inicialmente, compara mais à esquerda elemento, em seguida, funciona ao longo da tupla até o resultado é claro. Isso é adequado para proporcionar a rigorosa ordenação fraco esperada por exemplo std::set e std::map .

Se você tiver dados em algumas outras variáveis ??(por exemplo, campos em um struct), você ainda pode usar std::tie() para cria uma tupla de referências , que pode então ser comparado a um outro tal tupla. Isso faz com que seja fácil de escrever operator< para campos de dados membro específico em um tipo class / struct definido pelo usuário:

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

Você poderia simplesmente usar vetores de três elementos, que já terá operador <() adequadamente definiram. Isto tem a vantagem de que se estende a N-elementos, sem que você precise fazer nada.

Answer 5

O fluxo básico deve ser ao longo das linhas de: se os elementos KTH são diferentes, o retorno que é menor senão vai para o próximo elemento . O código a seguir assume que você não tem um impulso tupla caso contrário você usaria get<N>(tuple) e não têm o problema, para começar.

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

Mesmo que você não pode usar a versão impulso, você deve ser capaz de nick o código. Eu peguei isso do std :: pair -. A 3 tupla será semelhante Acho

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

Edit:. Como um casal de pessoas têm apontado, se você roubar código da biblioteca padrão para uso em seu código, você deve renomear as coisas que têm sublinhados na frente como esses nomes são reservados