Usando std :: sort et al. com rotina de comparação definida pelo usuário

Question

Usando std :: sort et al. com rotina de comparação definida pelo usuário

#1 resposta do (2 votos)

5

No avaliador de um idioma personalizado, gostaria de substituir nossas próprias rotinas de classificação por std::sort ou outras rotinas, possivelmente tbb::parallel_sort . O problema é que permitimos que os usuários do idioma forneçam sua própria rotina de comparação e, nas implementações que eu tentei, std::sort não aceita gentilmente as rotinas que não são uma ordem estrita. Em particular, ele rapidamente começa a analisar "elementos" fora do intervalo do iterador para classificar.

Eu assumo que, se eu colocar uma camada indireta sobre os iteradores, eu poderia evitar isso usando sentinelas virtuais, mas não há razão para supor que as chamadas resultantes terminariam necessariamente.

Assim, dada uma caixa preta bool f(widget const &a, widget const &b) e um pedido total não controlado pelo usuário operator<(widget const &a, widget const &b) , qual seria a quantidade mínima de chamadas que eu precisaria fazer para obter uma chamada de classificação que termina e que faz o pedido de acordo com f se isso é, na verdade, uma ordem? Parece-me que o seguinte deve funcionar, mas espero que eu possa conviver com menos chamadas para f por algum método inteligente, possivelmente lembrando de comparações anteriores:

bool f_stabilized(widget const &a, widget const &b) {
  bool fab = f(a, b);
  bool fba = f(b, a);
  return (fab != fba) ? fab : (a < b);
}

Seria razoável começar apenas chamando f e somente depois de ver n ^ 2 as chamadas para uma lista de comprimento n voltariam para essa versão “estabilizada”? Eu percebo que não há razão para supor que o resultado seria corretamente ordenado e eu precisaria recomeçar desde o início com um tal wrapper.

c++ algorithms

por Christopher Creutzig 30.12.2013 / 17:33

fonte

1 resposta

Tags c++ algorithms

Qual é a melhor maneira de expor um objeto Model em um ViewModel? Implantando mudanças do Esquema do Banco de Dados em um processo de correção [duplicado]

score 2 · Answer 1

Sua pergunta parece se resumir a se o std::sort de C ++ pode ou não ser usado com funções de comparação que não se comportam como o operador < . O operador < é um pedido estrito e fraco, não um pedido total. Qualquer contêiner ou algoritmo na biblioteca padrão C ++ que dependa do operador < assume que ele forma um ordenamento estrito e fraco, e se você violar essa suposição, então pode haver destruição (como você viu). Então, para responder a pergunta sem rodeios no seu título, std::sort funciona absolutamente bem com rotinas de comparação personalizadas, mas essas rotinas personalizadas devem se comportar corretamente.

Quanto a como gerar uma ordem adequada para std::sort , dado um possível total de pedidos, tente o seguinte. Dada uma função de ordenação personalizada f , defina uma nova função de ordenação f_weak da seguinte forma:

template <typename T, typename F>
auto f_weak(F comparator)
{
    return [comparator](T a, T b) {
               return comparator(a, b) // true if a <= b
                        && a != b;
    };
}

e depois passar f_weak<T>(f) como último parâmetro para std::sort . Este código não foi testado e usa alguns recursos modernos do C ++, mas tenho certeza que você entendeu a essência dele.