ошибка сегментации при тривиальной сортировке вектора c ++ пары [duplicate]
@Skizz: Я уверен, что я прав, хотя лучший «источник», который я могу вам дать в данный момент, - это Википедия, из статьи о sizeof:
Википедия ошибается, Skizz прав. sizeof (char) равен 1, по определению.
Я имею в виду, просто внимательно прочитал запись в Википедии , чтобы понять, что это неправильно. «кратные символы».
sizeof(char)никогда не может быть ничем другим , чем «1». Если бы это было, скажем, 2, это означало бы, чтоsizeof(char)был вдвое больше размера char!
4 ответа
Алгоритм, который использует std::sort, не указан. Используя функцию сравнения, которая не соответствует требованиям, установленным стандартом, вы нарушаете предположения алгоритма и вызывают неопределенное поведение.
Посмотрите, что происходит на выходе этой функции шумового сравнения, которая использует <= (который не является допустимым компаратором) вместо < (что действительно) .
http: //coliru.stacked -crooked.com/a/34e4cef3280f3728
На выходе я печатаю добавочную переменную (для ссылки, чтобы указать, когда алгоритм идет haywire) , затем значением первого аргумента и его положением в векторе, а затем вторым аргументом и его положением в векторе. Пример выглядит следующим образом:
124: 2@12 <= 4@7
Это означает, что это 124-й вызов функции сравнения, и он сравнивает значение 2 с индексом 12 со значением 4 с индексом 7.
Вещи сходят с ума, начиная с строки 37
37: 0@0 <= 0@-1
38: 0@0 <= 144@-2
39: 0@0 <= 0@-3
40: 0@0 <= 192@-4
. Это сравнение значений, которые я даже не вставлял в вектор (144, 192 и т. д.), а также в индексы вне диапазон вектора (отрицательные индексы, в данном случае).
Функция сравнения просто моделирует оператор «меньше». Посмотрите, как работает оператор < для таких примитивных типов, как int:
int a = 1, b = 2; a < b == true a is less than b
int a = 2, b = 1; a < b == false a is not less than b, because a is greater than b
int a = 1, b = 1; a < b == false a is not less than b, because a equals b
Возврат true означает, что вы хотите a упорядочиваться до b. Поэтому верните false, если это не так, потому что вы хотите, чтобы b заказывалось до a, или потому, что их порядок не имеет значения.
Если вы вернете true, когда аргументы равны, то вы говорите, что хотите a прийти перед b, и вы хотите b прийти перед a, что является противоречием.
-
1Я не уверен, почему это означает, что я хочу этого. Это потому, что на следующем шаге сравнение будет на одни и те же значения, кроме того, что они будут отправлены в функцию сравнения с измененными аргументами? – Zebrafish 29 August 2017 в 01:54
-
2@Zebrafish: Это по определению. Кажется, у вас есть что-то в обратном направлении: вы не можете реализовать это, как хотите, а затем как-то скажите алгоритму, как его использовать - алгоритм говорит «дайте мне строгий предикат порядка», и вы это реализуете. И в строгом порядке, f (a, a) == false, когда a == a. – GManNickG 29 August 2017 в 02:29
Для объяснения ответа Бенджамина Линдли рассмотрим типичный случай, когда std :: sort использует quicksort с схемой разбиения типа Hoare. Левая сторона сканируется для значений & lt; с помощью compare (value, pivot), чтобы выполнить сравнение, в то время как правая сторона сканируется для значений> pivot, используя compare (pivot, value). Обратите внимание, что раздел quicksort может полагаться на то, что сканирование влево или вправо останавливается, когда оно встречает значение == pivot и не продолжает сканирование через точку поворота при этом сканировании. Если предоставленная пользователем функция сравнения возвращает true при таком сравнении (true, когда значение == pivot), сканирование может продолжаться за пределами границ массива или сортируемого вектора, что, по-видимому, произошло в тестовом примере Бенджамина Линдли.
Не вдаваясь в глубину математики, 2 переменные можно сравнить, используя только '& lt;' оператор (или '>', если хотите). Однако '& lt;' обычно используется в объяснении «строгого слабого порядка» и в реализации сортировщиков.
Идея в основном заключается в том, что в практическом программировании, если a < b == false и b < a == false, тогда a == b.