¿Qué causa que std::sort() acceda a una dirección fuera de rango?

Question

Entiendo que para usar std::sort(), la función de comparación debe ser de orden estrictamente débil; de lo contrario, fallará debido a que la dirección de acceso está fuera de límites.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

Sin embargo, ¿por qué std::sort() accedería a la dirección fuera de límite cuando la función de comparación no es un orden estrictamente débil?¿Qué intenta comparar?

También me pregunto si existen otros errores en STL que debo tener en cuenta.

Answer 1

Lo primero es que llamar al algoritmo con un comparador que no cumple con los requisitos es un comportamiento indefinido y todo vale...

Pero aparte de eso, supongo que te interesa saber qué tipo de implementación podría terminar accediendo fuera de límites si el comparador es malo. ¿La implementación no debería verificar los límites antes de acceder a los elementos en primer lugar?es decir.antes de llamar al comparador

La respuesta es el rendimiento, y esta es sólo una de las posibles cosas que podrían provocar este tipo de problemas.Existen diferentes implementaciones de algoritmos de clasificación, pero la mayoría de las veces, std::sort está construido sobre una variante de clasificación rápida que degenerará en un algoritmo de clasificación diferente como mergesort para evitar el peor rendimiento de la clasificación rápida.

La implementación de clasificación rápida selecciona un pivote y luego divide la entrada alrededor del pivote, luego ordena ambos lados de forma independiente.Existen diferentes estrategias para la selección del pivote, pero una común es la mediana de tres:el algoritmo obtiene los valores del primer, último y medio elemento, selecciona la mediana de los tres y la utiliza como valor pivote.

Conceptualmente, la partición camina desde la izquierda hasta que encuentra un elemento que no es más pequeño que el pivote, luego camina desde la derecha tratando de encontrar un elemento que sea más pequeño que el pivote.Si los dos cursores se encuentran, la partición se completó.Si se encuentran los elementos fuera de lugar, se intercambian los valores y el proceso continúa en el rango determinado por ambos cursores.El bucle que recorre desde la izquierda para encontrar el elemento a intercambiar se vería así:

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

Si bien, en general, la partición no puede asumir que el valor del pivote estará dentro del rango, la clasificación rápida sabe eso es, después de todo, seleccionó el pivote entre los elementos del rango.Una optimización común en este caso es intercambiar el valor de la mediana para que esté en el último elemento del bucle.Esto garantiza que value(pos) < pivot será verdad antes pos == end (peor de los casos: pos == end - 1).La implicación aquí es que podemos descartar la verificación del final del rango y podemos usar un unchecked_partition (elija el nombre que prefiera) con una condición más simple y rápida:

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

Todo perfectamente bien, excepto eso. < se escribe comparator(value(pos), pivot).Ahora si el comparator se implementa incorrectamente, podría terminar con comparator(pivot,pivot) == true y el cursor se saldrá de los límites.

Tenga en cuenta que este es sólo un ejemplo de optimización del algoritmo que puede eliminar la verificación de límites de rendimiento:asumiendo un pedido válido, es imposible salir de la matriz en el bucle anterior si la ordenación rápida establece el pivote en el último elemento antes llamando a esta partición modificada.

Volviendo a la pregunta:

¿La implementación no debería verificar los límites antes de acceder a los elementos en primer lugar?es decir.antes de llamar al comparador

No, no si eliminó la verificación de límites al demostrar que no saldrá de la matriz, pero esa prueba se basa en la premisa de que el comparador es válido.

Answer 2

std::sort realiza de hecho que el comparador dado establezca un pedido débil estricto, de lo contrario, la clasificación realmente no tiene mucho sentido.

En cuanto a la que accede a su alcance, el enlace que publicó es un informe de errores, es decir, no se supone que haga esto. Los compiladores como cualquier otro software pueden y tendrán errores. Como señaló Adán, este informe de errores en particular fue rechazado ya que no es realmente un error.

¿Qué sucede exactamente cuando no tiene un pedido débil estricto no está definido por el estándar, no tiene sentido hacerlo y, por lo tanto, es excluido por el estándar? Por lo tanto, es indefinido por omisión. indefinido significa que cualquier cosa puede suceder, incluso accediendo fuera de rango.

En cuanto a evitar "Pitfalls", solo tenga en cuenta los requisitos de los algoritmos y las funciones que usa. Para C ++ hay un buen sitio de referencia que generalmente uso: cppreference

que en La página de std::sort dice:

Comp - Objeto de función de comparación (es decir, un objeto que satisface los requisitos de comparación) que devuelve verdadero si el primer argumento es menor que (es decir, se ordena antes) el segundo.

Con un enlace a la descripción de comparar