std :: sort（）にはどのような原因があります。

Question

Std :: Sort（）を使用することを理解しているので、比較関数は厳密な順序でなければならず、そうでなければバインドされたアドレスへのアクセスのためにクラッシュします。（ https://gcc.gnu.org/ml/gcc-バグ/ 2013-12 / MSG00333.HTML ）

しかし、なぜstd :: sort（）比較関数が厳密な弱い順序でないときにバインドされたアドレスにアクセスしますか？それは何を比較しようとしていますか？

また、STLに他の落とし穴があるかどうか、私が知っておくべきだと思います。

Answer 1

最初のことは、要件に準拠していない比較器を使用してアルゴリズムを呼び出すことであり、何でも問題があります...

それ以外の場合、私は、コンパレータが悪い場合にどのタイプの実装が範囲外にアクセスするのかを知ることに興味があると思います。 最初の場所で要素にアクセスする前に、実装は範囲をチェックしないように？すなわち、コンパレータを呼び出す前の

答えはパフォーマンスですが、これはこの種の問題につながる可能性がある可能性のあるものの1つです。ソートアルゴリズムの実装が異なりますが、NOTよりも多くの場合、std::sortはQuickSortのバリアントの上に構築されています。

QuickSortの実装はピボットを選択してからピボットの周囲の入力をパーティション化し、次に両側を独立に分類します。ピボットの選択には異なる戦略がありますが、共通のものは3つの中央値です。アルゴリズムは最初の、最後の要素と中間要素の値を取得し、3つの中央値を選択し、それをピボット値として使用します。

概念的にパーティションが歩行するまで左から歩くまで歩き回ると、ピボットよりも小さくない要素が見つかると、ピボットよりも小さい要素を見つけようとしている右から歩きます。 2つのカーソルが満たされた場合は、パーティションが完了しました。場所の外部要素が見つかった場合、値は交換され、プロセスは両方のカーソルによって決定された範囲で続行されます。スワップの要素を見つけるために左から歩くループは次のようになります。

while (pos < end && value(pos) < pivot) { ++pos; }

.

一般的なパーティションがピボットの値が範囲内にあると仮定することはできません。この場合の一般的な最適化は、中央値の値をループの最後の要素に置くことです。これにより、value(pos) < pivotは pos == end（最悪の場合：pos == end - 1）の前にtrue になることを保証します。ここでの意味は、範囲の最後のチェックを落とすことができ、より速いより速い条件でunchecked_partition（あなたの名前の選択を選択）を使用することができます。

while (/*pos < end &&*/ value(pos) < pivot) ++pos;

.

<の綴りcomparator(value(pos), pivot)を綴っていることを除いて、すべて完全に良い。 comparatorが誤って実装されている場合は、comparator(pivot,pivot) == trueで終わる可能性があり、カーソルは範囲外でなくなります。

これは、境界チェックのための境界チェックを除去することができるアルゴリズムの最適化の一例であることに注意してください。有効な順序を想定して、QiqueSortの場合は上記のループでアレイから外れるのは不可能なです。この変更されたパーティションを呼び出す前に、の前の最後の要素にピボットを設定します。

質問に戻る：

最初の場所で要素にアクセスする前に、実装は限界をチェックしないようにしてください。すなわち、比較器

を呼び出す前に

いいえ、それが配列から出て歩いていないことを証明することによってチェックしているが、その証明は、比較器が有効であることを前提に構築されている。

Answer 2

std::sortは実際には特定のコンパレータが厳密な弱い順序付けを確立することを要求します。そうしないと、ソートは実際には意味がありません。

範囲外のアクセスは、投稿したリンクはバグレポートにとって、すなわち実際にこれを行うことになっていません。他のソフトウェアのようなコンパイラはバグを持つことができます。 ADAMによって指摘されているように、この特定のバグレポートはそれが実際にはバグではないので拒否されました。

厳密な弱い注文がないと標準によって定義されていないときは正確に起こるのは、それをすることは理にかなっていないため、標準によって除外されます。したがって、漏れによって未定義です。 未定義は、範囲外にアクセスすることさえあります。

「落とし穴」を回避するためだけに、使用するアルゴリズムと機能の要件に注意してください。 C ++の場合、通常使用する素晴らしい参照サイトがあります。 cppreference

std::sort のページ：

comp - 比較関数オブジェクト（すなわち、比較要件を満たすオブジェクト）は、第1の引数が2番目未満の場合（すなわち、前に順序付けされている）。

比較