Classificação apenas usando o operador menos do que

Question

Na classificação C ++/STL, é feita usando apenas o operador menos do que o que Ao todo, não tenho idéia de como os algoritmos de classificação são realmente implementados, presumo que as outras operações sejam criadas Implicite:

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

Comparado ao uso de uma função Trivalue* Compare, como por exemplo, Java, isso é bom para o desempenho ou por que essa decisão de design foi tomada?

Minha suposição é que qualquer função do Trivalue Compareto ainda precisa implementar essas comparações em si, resultando no mesmo desempenho.

** Por função de comparação de Trivalue, quero dizer uma função de comparação que retorna -1, 0 e 1 para menos do que igual e superior a*

Atualizar:Parece uma nave espacial <=> O operador está chegando em C ++ 20, então, obviamente, o comitê pensou que havia desvantagens de usar apenas operator<.

Answer 1

Em certo sentido, os outros dois estão implícitos, mas mais precisos seria dizer que um tipo de comparação não precisar Um comparador tri-valor e os tipos de C ++ são implementados de uma maneira que não use um para minimizar o comportamento exigido do comparador.

Seria errado para o STD :: Satch para definir e usar exclusivamente algo assim:

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

... porque você acabaria com um algoritmo ineficiente em termos de número de chamadas para lessthan. Se o seu algoritmo não fizer nada útil com a diferença entre um retorno 1 e um retorno 0, você desperdiçou uma comparação.

C ++ refere -se a "pedidos fracos rígidos". Se < é uma ordem estrita fraca, e !(a < b) && !(b < a), não necessariamente Siga isso a == b. Eles estão apenas "no mesmo lugar" na ordem, e !(a < b) && !(b < a) é uma relação de equivalência. Portanto, o comparador exigido por sort ordens Classes de equivalência de objetos, ele não fornece um pedido total.

A única diferença que faz é o que você diz quando !(a < b). Para uma ordem total estrita, você deduziria b <= a, leia "Menos ou igual a". Para uma ordem fraca estrita, você não pode definir b <= a significar b < a || b == a E isso é verdade. O C ++ é pedante sobre isso e, como permite que a sobrecarga do operador tenha que ser, pois as pessoas sobrecarregam os operadores precisam do jargão para dizer aos usuários de seu código o que podem esperar em termos de como os operadores se relacionam. Java fala sobre o comparador e o código de hash sendo consistente com iguais, o que é tudo o que você precisa. C ++ precisa lidar com <,>, ==, <=,> =, a condição pós-condicionação e assim por diante.

O C ++ adota uma abordagem matemática bastante pura para isso na API, então tudo é definido em termos de relação binária única. Java é mais amigável em alguns aspectos e prefere comparações de três vias, onde a definição da unidade fundamental (a comparação) é um pouco mais complexa, mas a lógica que leva a ela é mais simples. Isso também significa que o algoritmo de classificação obtém mais informações por comparação, que ocasionalmente são úteis. Por exemplo, consulte a otimização do Quicksort "Flag da bandeira holandesa", o que é um benefício quando há muitos duplicações "no mesmo local" nos dados.

Nesse caso, um comparador de três valores é um ganho de velocidade. Mas o C ++ usa uma definição consistente de um comparador para classificar e também para set e map, lower_bound E assim por diante, que mal se beneficia de um comparador de três valores (talvez salve uma comparação, talvez não). Eu acho que eles decidiram não complicar sua boa interface geral no interesse de ganhos de eficiência potencial ou limitados.

Answer 2

Meu palpite em C ++ foi feito apenas para reduzir a duplicação de código: depois de definir um OP de comparação em uma classe/tipo, você não pode apenas comparar esses objetos simplesmente escrevendo um <b, mas também ganha a capacidade de classificar conjuntos de conjuntos de tais objetos.

Quanto à classificação, precisamos apenas do operador menos do que :)

Answer 3

Se você estiver se referindo ao STD :: Sort (), seu uso de apenas menos () porque não precisa preservar a ordem relativa de elemento equivalente, portanto, precisará de apenas menos () operador e operador implicitamente maior ().

Enquanto o std :: stable_sort o preservará, mas é mais lento. Precisa de menos () operador e iterador bidirecional em troca do operador igual () para construir a função "trivalue"