ソートアルゴリズムは、同じ要素を比較関数に渡す必要があります

Question

std :: sort of 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) 

さもなければ反復ごとに2つの試験（上のテストが存在するであろう一方で、アルゴリズムは、反復ごとに1つのだけのテストを持っている無防備ループにジャンプイテレータと、イテレータのデリファレンスされた値に関するテスト）。

"unguarded loops"の使用は、それ自身と比較される要素の原因です。開発中、私は、ループ内の1つの余分な比較のコストが、ループ内の反復ごとの2つの比較を含むよりも優れていることを測定しました。

もちろん、これはエンジニアリングのトレードオフです。比較関数がイテレータ自体を比較するコストと比較して非常に高価であることが判明した場合、異なる結論に至る可能性があります。

この答えは（と私はそれをupvotedしました）も正しいrici's answerと完全に一致しています。私は "おそらく"とアルゴリズムのコードの特定の行にポイントをドロップすることが私の声を追加しました。

Answer 2

おそらく、標準ライブラリ作者の意見では、falseを返すことが保証されたテストを行うために高速です。ピボット要素がループのセンチネルとして使用されるため、これが発生する可能性があります。それは確かに比較関数のために許可されている

は、このように呼ばれるように、そしてあなたのコード内assertが許可されていません。