引数が等しいときにstd :: sort compare関数がfalseを返す必要があるのはなぜですか？ STDでは

Question

::ソートあなたはそれがリストをソートする方法の基礎となる第三引数を供給することができます。最初の引数が最初に来るようにするには、trueを返します。 2番目の引数が最初に来るようにするには、falseを返します。

if arg1 == arg2, compare function MUST return false. 

私が持っているいくつかの用語がありました：私は私の述語関数は、おそらく「無効コンパレータ」であり、私はそれが次の要件を満たしていないという事実にそれを絞られている問題に遭遇してきましたstd :: sortには厳密な弱い順序が必要であると見なされます。 2つの場所を除いて、私がこれらのトピックについて得た他のすべてのページは、技術的な論文のようです。理解できません。

In weak ordering some elements "may be tied" with each other. 

しかし、私にはこれがある、また、「部分的に順序集合」の意味である：私はそれを理解できることはつまりさらに

"there may be pairs of elements for which neither element precedes the other" 

、私は何を理解することはできません「厳密」とは、どちらかに含意します。

注文理論の用語について私の混乱を除いて、私の質問は、compare関数の引数1と引数2が等しい場合、その場合、どちらが先に来るか気にしない私は幸せです）、なぜ議論1が最初に来るように私は真実に戻りませんか？

私はまた私のプログラムは、実際には無効なコンパレータです知っているが、その後、私はそれはおそらくちょうど比較関数がtrueを返した場合ARG1とARG2が等しいかどうかをチェックしますと思った方法を尋ねるつもりでした。

Answer 1

比較関数は、単にモデル「未満」演算子。 <オペレータがintのようなプリミティブ型のためにどのように機能するかを考えてみましょう：true戻ると、あなたがaがb前に注文することにしたい意味

int a = 1, b = 2;  a < b == true  a is less than b 
int a = 2, b = 1;  a < b == false  a is not less than b, because a is greater than b 
int a = 1, b = 1;  a < b == false  a is not less than b, because a equals b 

。それはそうではありませんので、もしあなたがbがa前に注文したいので、またはその順序は重要ではありませんのでどちらか、falseを返します。

引数が等しいときにtrueを返す場合、あなたは、あなたがaがb前に来たいとあなたはbが矛盾している、aの前に来てほしいと言っています。数学の深さに行くことなく

Answer 2

は、2つの変数が（「>」あなたが望む場合は）単に「<」演算子を用いて比較することができます。しかし、「<」は、「厳密な弱い順序」とソーターの実装において一般的に使用されています。

考え方は基本的に実際のプログラミングではa < b == falseとb < a == falseの場合はa == bです。

Answer 3

std::sortが使用するアルゴリズムが指定されていません。標準で設定された要件を満たさない比較関数を使用すると、アルゴリズムの前提条件が破られ、未定義の動作が発生します。

ではなく、（有効である）<の（有効なコンパレータではありません）<=を使用しています。この騒々しい比較関数の出力で何が起こるか見て。出力において

http://coliru.stacked-crooked.com/a/34e4cef3280f3728

、Iは、最初の引数の値とベクトル内の位置が続くインクリメント変数（アルゴリズムがめちゃくちゃになったときの参照のために指摘する）を、印刷午前2番目の引数とそのベクトル内の位置。例は次のようになります。

これは比較関数の第124回の呼び出しであることを意味し、それは7

物事は行くインデックスの値4で、指標12の値2を比較している

124: 2@12 <= 4@7 

それは私もベクターに挿入する（144、192など）とベクター（負のインデックスの範囲外のインデックスで、でなかった値を比較している線で37

37: 0@0 <= 0@-1 
38: 0@0 <= 144@-2 
39: 0@0 <= 0@-3 
40: 0@0 <= 192@-4 

出発クレイジーこの場合）。

Answer 4

Benjamin Lindleyの答えについては、std :: sortがquicksortとHoareタイプのパーティションスキームを使用する典型的なケースを考えてみましょう。左側はcompare（value、pivot）を使って値<のピボットをスキャンし、右側はcompare（pivot、value）を使ってピボットの値をスキャンします。 quicksortパーティションは、値==ピボットが発生したときに左または右のスキャンが停止し、そのスキャンでピボットを超えてスキャンを続行しないという事実に依存することがあります。そのような比較（value ==ピボットの場合はtrue）でユーザーが指定したcompare関数がtrueを返した場合、ベンジャミン・リンドレーのテストケースで明らかに起きた配列またはベクトルの境界を超えてスキャンが続行される可能性があります。