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

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

$ 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

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

我可以在这个问题上有一定的权威性，因为我是编写这段代码的人。

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

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

由于随着时间的推移，链接可能会变得陈旧（指向错误的行），我还将在此处引用代码：

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

这被称为“无保护”循环，因为不检查迭代器__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)

在该测试找到较低的保护之后，算法然后跳转到无保护循环，该循环每次迭代仅进行一次测试，否则每次迭代将进行两次测试（对迭代器的测试和对迭代器取消引用值的测试） 。

使用“无保护循环”是元素与自身进行比较的原因。在开发过程中，我发现循环中一次额外比较的成本比循环中每次迭代包括两次比较要划算。

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

这个答案完全符合里奇的回答这也是正确的（我已经投票了）。我添加了自己的声音，因为我可以放弃“大概”并指向算法中的特定代码行。