Что заставляет std::sort() обращаться к адресам вне диапазона
Я понимаю, что для использования std::sort() функция сравнения должна иметь строгий слабый порядок, иначе произойдет сбой из-за обращения к адресу вне пределов. ( https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html)
Однако зачем std::sort() обращаться к внешнему адресу, если функция сравнения не является строгим слабым порядком? Что он пытается сравнить?
Также мне интересно, есть ли другие подводные камни в STL, о которых я должен знать.
2 ответа
Во-первых, вызов алгоритма с помощью компаратора, который не соответствует требованиям, является неопределенным поведением, и все происходит...
Но кроме этого, я предполагаю, что вам интересно знать, к какому типу реализации может в конечном итоге получить доступ за пределами, если компаратор плохой. Разве реализация не должна проверять границы перед тем, как получить доступ к элементам? т.е. перед вызовом компаратора
Ответ - производительность, и это только одна из возможных вещей, которые могут привести к такого рода проблемам. Существуют разные реализации алгоритмов сортировки, но чаще всего, std::sort построен на основе варианта быстрой сортировки, который будет вырожден в другом алгоритме сортировки, таком как mergesort, чтобы избежать худшей производительности быстрой сортировки.
Реализация быстрой сортировки выбирает стержень, а затем разделяет входные данные вокруг стержня, а затем независимо сортирует обе стороны. Существуют разные стратегии для выбора центральной точки, но общей является медиана трех: алгоритм получает значения первого, последнего и среднего элемента, выбирает медиану из трех и использует ее в качестве значения основной точки.
Концептуально раздел идет налево, пока не находит элемент, который не меньше, чем шарнир, затем идет справа, пытаясь найти элемент, который меньше, чем шарнир. Если два курсора встречаются, раздел завершен. Если найдены неуместные элементы, значения меняются местами, и процесс продолжается в диапазоне, определяемом обоими курсорами. Цикл, идущий слева, чтобы найти элемент для замены, будет выглядеть так:
while (pos < end && value(pos) < pivot) { ++pos; }
В то время как в общем случае раздел не может предположить, что значение pivot будет в диапазоне, quicksort знает, что оно есть, после того как он выбрал pivot из элементов в диапазоне. Обычная оптимизация в этом случае состоит в том, чтобы поменять значение медианы в последнем элементе цикла. Это гарантирует, что 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 и курсор выйдет за пределы.
Обратите внимание, что это только один пример оптимизации алгоритма, который может убрать проверку границ для производительности: при допустимом порядке невозможно выйти из массива в вышеуказанном цикле, если бы быстрая сортировка установила pivot на последний элемент перед вызовом этого модифицированный раздел.
Вернуться к вопросу:
Разве реализация не должна проверять границы перед тем, как получить доступ к элементам? т.е. перед вызовом компаратора
Нет, если он убрал проверку границ, доказав, что он не выйдет из массива, но это доказательство основано на предпосылке, что компаратор действителен.
std::sort действительно требует, чтобы данный компаратор устанавливал строгий слабый порядок, иначе сортировка не имеет большого смысла.
Что касается доступа за пределы допустимого диапазона, вы разместили ссылку на сообщение об ошибке, то есть на самом деле это не предполагается. Компиляторы, как и любое другое программное обеспечение, могут и будут иметь ошибки. Как отметил Адам, этот конкретный отчет об ошибке был отклонен, поскольку на самом деле это не ошибка.
Что именно происходит, когда у вас нет строгого слабого порядка, не определяется стандартом, это не имеет смысла, и поэтому стандарт не учитывается. Поэтому оно не определяется пропуском. Неопределенный означает, что может произойти что угодно, даже доступ вне диапазона.
Что касается избежания "ловушек", просто помните о требованиях алгоритмов и функций, которые вы используете. Для C++ есть хороший ссылочный сайт, которым я обычно пользуюсь: http://en.cppreference.com/w/
Который на страницеstd::sort говорит:
comp - объект функции сравнения (т. е. объект, который удовлетворяет требованиям Compare), который возвращает true, если первый аргумент меньше (т.е. упорядочен раньше) второго.
С ссылкой на описание сравнения