时间戳

首页 > 解决方案 > 为什么这个 std::sort 比较失败？

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

问题描述

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

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 。

当我在父向量中的元素数量相对较少（大约 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。这似乎工作正常，所以我只是使用它，但我无法弄清楚第一种方法有什么问题。特别是第一种方法似乎在某些时候有效，而第二种比较无论如何只是第一种比较的扩展。

标签： c++sortingvectorstd

解决方案

首先，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}, and c = {1, 3, 4}, a == band b == cbut a != c。

推荐阅读