Что заставляет std::sort() получать доступ к адресу вне диапазона

Question

Я понимаю, что для использования std::sort() функция сравнения должна иметь строгий слабый порядок, иначе произойдет сбой из-за доступа к адресу за пределами границ.(https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)

Однако зачем std::sort() обращаться к внешнему адресу, если функция сравнения не является строгим слабым порядком?Что он пытается сравнить?

Также мне интересно, есть ли в STL другие подводные камни, о которых мне следует знать.

Answer 1

Во-первых, вызов алгоритма с компаратором, не соответствующим требованиям, — это неопределенное поведение и всякое бывает...

Но кроме этого, я предполагаю, что вам интересно знать, какой тип реализации может в конечном итоге получить доступ за пределы, если компаратор плох. Должна ли реализация вообще не проверять границы перед доступом к элементам?то естьперед вызовом компаратора

Ответ — производительность, и это лишь одна из возможных причин, которые могут привести к проблемам такого типа.Существуют разные реализации алгоритмов сортировки, но чаще всего std::sort построен на основе варианта быстрой сортировки, который будет использовать другой алгоритм сортировки, такой как сортировка слиянием, чтобы избежать наихудшей производительности быстрой сортировки.

Реализация быстрой сортировки выбирает точку поворота, а затем разделяет входные данные вокруг нее, а затем независимо сортирует обе стороны.Существуют разные стратегии выбора точки поворота, но наиболее распространенной является медиана из трех:алгоритм получает значения первого, последнего и среднего элемента, выбирает медиану из трех и использует ее в качестве опорного значения.

Концептуально раздел идет слева, пока не найдет элемент, который не меньше опорного элемента, затем он идет справа, пытаясь найти элемент, который меньше опорного элемента.Если два курсора встречаются, раздел завершен.Если обнаружены неуместные элементы, значения меняются местами и процесс продолжается в диапазоне, определяемом обоими курсорами.Цикл, идущий слева для поиска элемента для замены, будет выглядеть так:

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

Хотя в целом раздел не может предполагать, что значение поворота будет находиться в заданном диапазоне, быстрая сортировка знает это так, ведь он выбрал ось из элементов диапазона.Обычной оптимизацией в этом случае является замена значения медианы на последний элемент цикла.Это гарантирует, что value(pos) < pivot будет правдой до pos == end (худший случай: pos == end - 1).Подразумевается, что мы можем отказаться от проверки конца диапазона и использовать unchecked_partition (выберите имя по своему выбору) с более простым и быстрым условием:

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

Все отлично, кроме этого < пишется comparator(value(pos), pivot).Теперь, если comparator неправильно реализовано, вы можете получить comparator(pivot,pivot) == true и курсор выйдет за пределы.

Обратите внимание, что это всего лишь один пример оптимизации алгоритма, который может удалить проверку границ производительности:предполагая действительный заказ, это невозможный выйти из массива в приведенном выше цикле, если быстрая сортировка установила опорную точку на последний элемент до вызов этого измененного раздела.

Вернемся к вопросу:

Должна ли реализация вообще не проверять границы перед доступом к элементам?то естьперед вызовом компаратора

Нет, нет, если он устранил проверку границ, доказав, что он не выйдет из массива, но это доказательство построено на предпосылке, что компаратор действителен.

Answer 2

std::sort действительно требует, чтобы данный компаратор устанавливает строгий слабый упорядочение, в противном случае сортировка действительно не имеет большого смысла.

Что касается его доступа к дальности, ссылка, которую вы опубликовали, - это отчет об ошибках, то есть. Он не должен сделать это. Компиляторы, как и любое другое программное обеспечение, может иметь ошибки. Как отмечено ADAM, этот отчет об ошибках был отклонен, поскольку он не ошибка.

Что именно происходит, когда у вас нет строгого слабого упорядочения не определяется стандартом, он не имеет смысла делать это и поэтому оставлено стандартом. Поэтому это undefined бездействием. <Сильные> undefined означает, что что-то может произойти, даже доступа к диапазону.

Что касается «подводных камней», просто осознайте требования алгоритмов и используемых функций. Для C ++ есть хороший справочный сайт, который я обычно использую: CPPreference

который на Страница std::sort говорит:

Comp - объект функции сравнения (I.E. Объект, который удовлетворяет требованиям сравнения), который возвращает true, если первый аргумент меньше, чем (то есть заказывается до) второго.

со ссылкой на описание Сравнить