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

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

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

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

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's answer这也是正确的(我已经赞成)。我添加了我的声音，因为我可以删除“大概”并指向算法中的特定代码行。