Почему это сравнение std :: sort не удается?

Question

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

sort(league_vector.begin(), league_vector.end());
reverse(league_vector.begin(), league_vector.end());
sort(league_vector.begin(), league_vector.end(),
   [](const std::vector<unsigned int>& a, const std::vector<unsigned int>& b) {return a[0] == b[0] && a[2] < b[2];});

Так что просто отсортируйте, а затем переверните все, что будет упорядочено по первому элементу.Затем пользовательская сортировка с использованием лямбда-функции, которая должна возвращать true только в том случае, если третий элемент меньше и , первый элемент равен.

Кажется, что это нормально работает, когда у меня относительно небольшое числоэлементов в родительском векторе (около 50 или меньше), но когда у меня есть больше, чем это, окончательный порядок выходит довольно перемешанным без какого-либо очевидного паттерна вообще.

Я заменил это на один пользовательскийsort:

sort(league_vector.begin(), league_vector.end(),
   [](const std::vector<unsigned int>& a, const std::vector<unsigned int>& b)
   {return ((a[0] > b[0]) || (a[0] == b[0] && a[2] < b[2]));});

Таким образом, возвращается значение true, когда первый элемент больше, или когда третий элемент меньше И первый элемент такой же.Кажется, это работает нормально, поэтому я просто использую это, но я не могу понять, что не так с первым подходом.Тем более, что первый подход иногда работает, а второе сравнение в любом случае является лишь продолжением первого.

Answer 1

Прежде всего, std::sort не является стабильной сортировкой, что означает, что она не сохраняет порядок эквивалентных элементов.Если вы хотите стабильную сортировку, используйте std::stable_sort.Кроме того, ваша пользовательская функция сравнения не имеет смысла.Давайте проанализируем, как он себя ведет:

Если a[0] равно b[0], ваша функция возвращает результат сравнения a[2] и b[2].Однако, если a[0] не равно b[0], ваша функция всегда возвращает false.Поскольку эквивалентность определяется как !(a < b) && !(b < a), согласно вашей функции сравнения любые два вектора с разными первыми элементами равны.

Эта функция также не является допустимой функцией сравнения, поскольку она не удовлетворяет строгому слабому порядку,Любые два вектора с разными первыми элементами равны, но два вектора с одинаковым первым элементом не обязательно равны.Это означает, что если a = {1, 2, 3}, b = {2, 3, 4} и c = {1, 3, 4}, a == b и b == c, но a != c.

Answer 2

Почему ваша первая попытка не удалась? Давайте возьмем конкретный пример, сосредоточимся на этом сравнении и попытаемся объяснить, почему это недопустимо, выполнив простой тест.

Вот два вектора лиги в качестве примера:

std::vector<std::vector<unsigned int>> league_vector = {{1,2,3,4}, {2,3,4,5}, {4,5,6,7}};

Теперь дайте это std::sort:

std::sort(league_vector.begin(), league_vector.end(),
          [](const std::vector<unsigned int>& a, 
          const std::vector<unsigned int>& b) {return a[0] == b[0] && a[2] < b[2];});

Сконцентрируйтесь на этом:

a[0] == b[0]

Итак, скажем, std::sort дает ваше сравнение первых двух векторов в league_vector в этом порядке

a={1,2,3,4} b={2,3,4,5}

Ваша функция сравнения вернет false, начиная с a[0] != b[0].

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

a={2,3,4,5} b={1,2,3,4}

Другими словами, простое переключение значений. Вы снова возвращаете false с a[0] != b[0].

Как это может иметь смысл, когда вы говорите, что в первом тесте a должно идти после b, а во втором тесте с только что переключенными значениями, a должно идти после b?

Алгоритм сортировки оправданно запутывается и помещает значения в неортодоксальный порядок.

Обратите внимание, что компилятор Visual Studio выполняет этот тест, который я описал, где функция сравнения задается a и b, проверяется возвращаемое значение, а затем b и a и проверяется возвращаемое значение. Если есть несоответствие, как указано, среда выполнения отладки устанавливает условие «недопустимое сравнение» (или подобное).