O que faz com std::sort() acessar o endereço fora do intervalo
-
21-12-2019 - |
Pergunta
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.
Solução
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.
Outras dicas
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