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