O que faz com std::sort() acessar o endereço fora do intervalo

Question

Eu entendo que para uso std::sort(), a função de comparação deve ser rigorosa fraco ordem, de outra forma ele irá falhar devido ao acessar o endereço fora do limite.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

No entanto, qual seria o std::sort() acesso out-of-endereço vinculado quando a função de comparação não é restrita fraco ordem?O que é tentar comparar?

Também gostaria de saber se há outras armadilhas em STL que eu deveria estar ciente.

Answer 1

A primeira coisa é que chamar o algoritmo com um comparador que não estejam em conformidade com os requisitos é um comportamento indefinido e nada vai...

Mas do que isso, eu suponho que você está interessado em saber que tipo de implementação pode acabar acesso fora dos limites, se a comparação é ruim. Deve a execução não se verifique a limites antes de acessar os elementos em primeiro lugar?i.e.antes de chamar o comparador

A resposta é o desempenho, e esta é apenas uma das possíveis coisas que podem levar a este tipo de questões.Existem diferentes implementações de algoritmos de ordenação, mas mais frequentemente do que não, std::sort é construído em cima de um quicksort que irá degenerar em um outro algoritmo de classificação como mergesort para evitar o quicksort pior desempenho.

A implementação do quicksort seleciona uma tabela dinâmica e, em seguida, partições de entrada em torno do pivô, em seguida, independentemente tipos ambos os lados.Existem diferentes estratégias para a seleção do pivô, mas um dos mais comuns é a mediana de três:o algoritmo obtém os valores do primeiro, o último e o elemento intermediário, seleciona-se a mediana de três e usa isso como o pivô valor.

Conceitualmente partição passeios a partir da esquerda até encontrar um elemento que não é menor do que o pivô, em seguida, ele caminha da direita, tentando encontrar um elemento que é menor do que o pivô.Se os dois cursores atender, partição concluída.Se o limite de colocar elementos são encontrados, os valores são trocados e o processo continua no intervalo determinado por ambos os cursores.O loop de pé da esquerda para encontrar o elemento de comutação seria parecido com:

while (pos < end && value(pos) < pivot) { ++pos; }

Apesar de, em geral partição não é possível assumir que o valor do pivô será no intervalo, o quicksort sabe que é, afinal de contas, é selecionado o pivô de elementos no intervalo.Comum de otimização, neste caso, é trocar o valor da mediana para ser o último elemento do ciclo.Isso garante que value(pos) < pivot será verdade antes de pos == end (pior caso: pos == end - 1).A implicação aqui é que podemos descartar a seleção para o fim do intervalo e podemos usar uma unchecked_partition (pegue a sua escolha do nome) com um mais simples, mais rápido condição:

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

Tudo perfeitamente bem, exceto que < está escrito comparator(value(pos), pivot).Agora, se o comparator é implementado incorretamente, você pode acabar com comparator(pivot,pivot) == true e o cursor será executado fora dos limites.

Note que este é apenas um exemplo de otimização do algoritmo, que pode remover verificação de limites para o desempenho:supondo uma ordem válida, é impossível para sair da matriz acima ciclo se quicksort definir o pivô para o último elemento antes de chamar essa modificação partição.

De volta à questão:

Deve a execução não se verifique a limites antes de acessar os elementos em primeiro lugar?i.e.antes de chamar o comparador

Não, não se removida a verificação de limites, provando que ele não vai sair da matriz, mas que provar que é construído sobre a premissa de que a comparação é válida.

Answer 2

std::sort realmente exige que o comparador determinado estabeleça uma ordem fraca rigorosa, caso contrário, a classificação realmente não faz muito sentido.

Quanto ao acesso fora do intervalo, o link que você postou é para um relatório de bugs, isto é, não é suposto fazer isso. Compiladores como qualquer outro software podem e terão bugs. Como observado por Adam, este relatório de bugs específico foi rejeitado, pois não é realmente um bug.

O que exatamente acontece quando você não tem uma encomenda fraca estrita não é definida pelo padrão, não faz sentido fazer isso e, portanto, é deixado de fora pelo padrão. Portanto, é indefinido por omissão. indefinido significa que tudo pode acontecer, mesmo acessando fora do intervalo.

Quanto a evitar "armadilhas", apenas esteja ciente dos requisitos dos algoritmos e funções que você usa. Para C ++ há um site de referência agradável que eu costumo usar: cppreference

que em a página do std::sort diz:

.

Objeto de função de comparação (i.e. Um objeto que satisfaz os requisitos de comparação), que retorna true se o primeiro argumento for menor que (isto é, é encomendado antes) o segundo.

com um link para a descrição de comparar