Pedido de STL - pedidos fracos rígidos

Question

Por que o STL funciona com uma função de comparação que é ordem fraca estrita? Por que não pode ser uma ordem parcial?

Answer 1

UMA ordem parcial Não seria suficiente para implementar alguns algoritmos, como um algoritmo de classificação. Como um conjunto parcialmente ordenado não define necessariamente um relacionamento entre todos os elementos do conjunto, como você classificaria uma lista de dois itens que não têm um relacionamento de pedido dentro da ordem parcial?

Answer 2

Simplesmente, uma ordem fraca estrita é definida como uma ordem que define uma relação de equivalência (computável). As classes de equivalência são ordenadas pela estrita ordem fraca: Uma ordem estrita fraca é uma ordem estrita nas aulas de equivalência.

Uma ordem parcial (que não é uma ordem fraca estrita) não define uma relação de equivalência, então Qualquer especificação usando o conceito de "elementos equivalentes" não tem sentido com uma ordem parcial que não é uma ordem fraca estrita. Todos os contêineres associativos do STL usam esse conceito em algum momento, portanto, todas essas especificações não têm sentido com uma ordem parcial que não é uma ordem estrita fraca.

Como uma ordem parcial (isso não é uma ordem fraca estrita) não define necessariamente nenhuma ordem estrita, você não pode "classificar elementos" no sentido comum de acordo com a ordem parcial (tudo o que você pode fazer é um "tipo topológico" que possui propriedades mais fracas ).

Dado

• um conjunto matemático S
• uma ordem parcial < sobre S
• um valor x dentro S

você pode definir uma partição de S (cada elemento de S está dentro L(x), I(x) ou G(x)):

L(x) = { y in S | y<x }
I(x) = { y in S | not(y<x) and not(x<y) }
G(x) = { y in S | x<y }

 L(x) : set of elements less than x
 I(x) : set of elements incomparable with x
 G(x) : set of elements greater than x

Uma sequência é classificada de acordo com < iff para cada x na sequência, elementos de L(x) aparecer primeiro na sequência, seguido por elementos de I(x), seguido por elementos de G(x).

Uma sequência é classificada topologicamente iff para cada elemento y que aparece depois de outro elemento x na sequência, y não é menor que x. É uma restrição mais fraca do que ser classificado.

É trivial provar que todo elemento de L(x) é menor do que qualquer elemento de G(x). Não há relação geral entre elementos de L(x) e elementos de I(x), ou entre elementos de I(x) e elementos de G(x). No entanto, se < é uma ordem estrita fraca, do que todos os elementos de L(x) é menor do que qualquer elemento de I(x), e do que qualquer elemento de I(x) é menor do que qualquer elemento de G(x).

Se < é uma ordem estrita fraca, e x<y então qualquer elemento de L(x) U I(x) é menos que qualquer elemento I(y) U G(y): qualquer elemento não maior que x é menor do que qualquer elemento não menos que y. Isso não se aplica necessariamente por uma ordem parcial.

Answer 3

Citando a resposta dada aqui:

Porque internamente, esses algoritmos implementam "é igual a" como !(a < b) && !(b < a).

Se você usou <= Para implementar o operador menos do que a == b. Uma verificação de igualdade quebrada vai estragar quase qualquer algoritmo.

Da mesma forma, eles implementam "não são iguais a" como (a < b) || (b < a), e mais uma vez, se você implementou o < operador usando <=, então retornará verdadeiro quando forem iguais um ao outro, quando na verdade eles não forem iguais. Portanto, a verificação da igualdade é quebrada nas duas direções.

O objetivo de limitar a biblioteca a um operador menos do que

• <(a, b): (a < b)
• <=(a, b): !(b < a)
• ==(a, b): !(a < b) && !(b < a)
• !=(a, b): (a < b) || (b < a)
• >(a, b): (b < a)
• >=(a, b): !(a < b)

Isso funciona desde que o operador fornecido atenda às condições de uma ordem estrita fraca. O padrão <= e >= Os operadores não.

Answer 4

Você não pode executar pesquisas binárias com pedidos parciais. Você não pode criar uma árvore de pesquisa binária com pedidos parciais. Que funções/tipos de dados de algoritmo Precisa de pedidos e pode trabalhar com pedidos parciais?