排序算法是否应该在比较函数中传递相同的元素

Question

libcxx的std::sort（c++标准的llvm版本 library) 调用具有相同元素的比较谓词，即比较函子的两个参数都指向相同的位置要排序的序列。一个简化的例子来说明这一点。

$ cat a.cc
#include <algorithm>
#include <vector>
#include <cassert>

int main(int argc, char** argv) {
  int size = 100;
  std::vector<int> v(size);

  // Elements in v are unique.
  for (int i = 0; i < size; ++i)
    v[i] = i;

  std::sort(v.begin(), v.end(),
            [&](int x, int y) { assert(x != y); return x < y; });

  return 0;
}

$ clang++ -std=c++11 -stdlib=libc++ a.cc -o a.out
$ ./a.out
a.out: a.cc:14: auto main(int, char **)::(anonymous class)::operator()(int, int) const: Assertion `x != y' failed.
./go.sh: line 5: 19447 Aborted                 (core dumped) ./a.out

适用于 libstdc++。

$ clang++ -std=c++11 -stdlib=libstdc++ a.cc -o a.out
$ ./a.out

用相同的元素调用比较函数可以吗？这不是多余的吗

Answer 1

据推测，在标准库作者看来，进行保证 return 错误的测试比不断检查相等索引以及比较元素更快。这可能是因为枢轴元素用作循环标记。

这样调用比较函数当然是允许的，你代码中的assert是不允许的

Answer 2

我可以在这个问题上发表一些权威意见，因为我是编写这段代码的人。

这是在您的示例中断言的比较：

https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm#L3994-L3995

随着时间的推移，link 可能会过时（指向错误的行），我也会在这里引用代码：

            // __m still guards upward moving __i
            while (__comp(*__i, *__m))
                ++__i;

这被称为 "unguarded" 循环，因为在递增时不检查序列末尾的迭代器 __i 运行。之所以可行，是因为该算法的一个不变量是，此时已知 __i <= __m（也在该引用上方 3 行的注释中）。

如果您查看此引用上方的代码，您将看到以下注释：

    // The search going up is known to be guarded but the search coming down isn't.
    // Prime the downward search with a guard.

所以在我们到达这一点之前，已经完成了对序列的保护搜索。即本次测试：

if (__i == --__j)

在这个测试找到较低的守卫之后，算法然后跳转到无守卫的循环，每次迭代只有一个测试，否则每次迭代会有两个测试（迭代器测试和取消引用测试迭代器的值）。

"unguarded loops" 的使用是元素与自身进行比较的原因。在开发过程中，我测量了在循环中进行一次额外比较的成本比在循环中每次迭代包含两次比较要好。

当然这是一个工程权衡。如果与比较迭代器本身的成本相比，比较函数被证明是非常昂贵的，那么人们可能会得出不同的结论。

这个答案与完全一致，这也是正确的（我已经赞成）。我添加了我的声音，因为我可以删除 "presumably" 并指向算法中的特定代码行。

排序算法是否应该在比较函数中传递相同的元素

Should sorting algorithm pass same element in the comparison function

c++

algorithm

sorting

libstdc++

libc++