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

Question

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

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 函数进行自定义排序，如果第三个元素较小 return 并且第一个元素相等，则该函数仅应 return 为真。

当我在父向量中的元素数量相对较少（大约 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]));});

因此，如果第一个元素较大，或者第三个元素较小且第一个元素相同，则此 return 为真。这似乎工作正常，所以我只是使用它，但我无法弄清楚第一种方法有什么问题。特别是第一种方法有时似乎有效，而第二种比较只是第一种方法的扩展。

Answer 1

首先，std::sort不是一个稳定的排序，这意味着它不保留等价元素的顺序。如果你想要一个稳定的排序，使用std::stable_sort。此外，您的自定义比较功能毫无意义。让我们分析一下它的行为：

如果 a[0] 等于 b[0]，您的函数 returns 比较 a[2] 和 b[2] 的结果。但是，如果 a[0] 不等于 b[0]，您的函数总是 returns 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}

您的比较函数将 return false 因为 a[0] != b[0]。

那么如果编译器做了一个 switch up，然后马上给你这个，只是为了看看你的函数是否有歧义：

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

换句话说，一个简单的值切换。自从 a[0] != b[0] 以来，您又 return false。

这怎么说得通，你在第一次测试中说 a 应该在 b 之后，而在第二次测试中只有切换值，a 应该在之后b？

排序算法理所当然地变得混乱，并以某种非正统的顺序排列值。

注意Visual Studio编译器做了我描述的这个测试，这里给出比较函数a和b，检查return值，然后b 和 a 以及 return 值已检查。如果存在所指出的不一致，调试运行时会使用 "invalid comparison"（或类似）条件进行断言。

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

Why is this std::sort comparison failing?

c++

sorting

vector

std