c++ - 为什么这个 std::sort 比较失败了？

Question

我有一个由无符号整数组成的 vector 。父 vector 的每个元素都是三个无符号整数的 vector 。我主要想按子 vector 第一个元素的降序对父 vector 进行排序，但我也想按第三个元素的升序顺序对具有相同第一个元素的任何子 vector 进行排序。我最初使用以下代码执行此操作:

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];});

所以只需排序，然后反转，整个事情将按第一个元素排序。然后使用 lambda 函数进行自定义排序，如果第三个元素较小并且第一个元素相等，则该函数应该只返回 true。

当我在父 vector 中的元素数量相对较少(大约 50 个或更少)时，这似乎工作正常，但当我有更多元素时，最终排序会变得非常困惑，根本没有明显的模式。

我已将其替换为单个自定义排序:

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) ，根据你的比较函数，任意两个第一个元素不同的 vector 是相等的。

此函数也不是有效的比较函数，因为它不满足严格的弱排序。任意两个第一个元素不同的 vector 相等，但两个第一个元素相同的 vector 不一定相等。这意味着如果 a = {1, 2, 3} , b = {2, 3, 4} , 和 c = {1, 3, 4} , a == b和 b == c但是a != c .