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

Question

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

$ 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

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

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

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)

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

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

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

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