将元素传递给 std::sort 中的比较函数的顺序背后的逻辑是什么？

Question

我正在练习 lambdas:

 int main()
 {
    std::vector<int> v {1,2,3,4};
    int count = 0;
    sort(v.begin(), v.end(), [](const int& a, const int& b) -> bool
        {
        return a > b;
        });
  }

这只是 GeeksForGeeks 中的代码，用于按降序排序，没有什么特别之处。我添加了一些打印语句（但为此 post 将它们取出）以查看 lambda 内部发生了什么。他们打印整个向量，以及 a 和 b 值：

1 2 3 4  
a=2 b=1

2 1 3 4  
a=3 b=2

3 2 1 4  
a=4 b=3

4 3 2 1 <- final

所以我更详细的问题是：矢量元素传递到 a 和 b 参数的顺序背后的逻辑是什么？

b 是否永久位于索引 0 而 a 正在迭代？如果是这样，传递给 lambda 的 second 参数停留在 first 元素上是不是有点奇怪？它是特定于编译器的吗？谢谢！

Answer 1

您只需按照给定的顺序比较两个元素。这意味着如果顺序是 a 然后是 b，那么 lambda 必须 return true.

a 或 b 是数组的第一个或最后一个元素，或者是固定的，这取决于排序算法，当然还有您的数据！

Answer 2

Is 'b' permanently at index 0 while 'a' is iterating? And if so, isn't it a bit odd that the second param passed to the lambda stays at the first element?

不是，因为第一个元素更高

似乎，使用这个算法，所有元素都用较高的元素（在第一轮）进行检查（并可能切换），并将较高的元素放在第一位；所以b永远指向更高的那个。

Answer 3

对于Visual Studio，如果子数组大小<= 32 个元素，std::sort 使用插入排序。对于较大的子数组，它使用 intro sort，这是快速排序，除非 "recursion" 深度变得太深，在这种情况下它会切换到堆排序。您的程序产生的输出似乎对应于插入排序的某些变体。由于比较函数是"less than"，并且由于插入排序正在查找由于左值"greater than"右值而乱序，因此输入参数被交换。

Answer 4

通过将谓词传递给 std::sort()，您指定了 排序标准 。如果第一个参数（即a）先于第二个参数（即b），则谓词必须returntrue，对于您指定的排序标准。

因此，对于您的谓词：

return a > b;

如果a比b大，那么a将先于b.

So my more detailed question is: What's the logic behind the order the vector elements are being passed into the a and b parameters?

a 和 b 只是您传递给 std::sort() 的元素的成对元素。 "logic" 将取决于 std::sort() 实现的底层算法。由于随机化，对于具有相同输入的调用，这些对也可能不同。

将元素传递给 std::sort 中的比较函数的顺序背后的逻辑是什么？

What's the logic behind the order the elements are passed to a comparison function in std::sort?

c++

sorting

stl

std

strict-weak-ordering