std::sort(begin, end)への呼び出しが実際に範囲を変更したかどうかを判断する最もエレガントな方法は何ですか？ここでstd :: sort（begin、end）が範囲を変更したかどうかを調べる
は私の2つのアイデアです：
（a）のチェックであればすでにソートO（n）は：
if (already_sorted(begin, end)) { return false; }
std::sort(begin, end);
return true;
（b）は、比較のトラックの変化（これは安全なのですか？）：
bool modified = false;
std::sort(begin, end, [&modified](T a, T b){ modified |= a<b; return a<b; });
return modified;
もっと良い方法がありますか？
"begin"から "end"までの構造を反復しない限り、すでにソートされているかどうかを知ることができないため、O（n）にできるのは最高です。
私は最初の選択肢、already_sortedに行くだろう。
注： 'is_sorted（FwdIt begin、FwdIt end）'の典型的な実装は 'return std :: adjacent_find（begin、end、std :: greater
O（n）よりも、配列が開始された順序とは異なる順序で戻ってきたかどうかを確認するよりも、これを行うことはできません。理論的にソート関数は、何かを動かすことなく好きなような比較を行うことができるので、注文がうまく動作することが保証されていない場合、コンパレータをハイジャックすることで確認できます。さらに、スワップが実行されたかどうかを追跡することは、並べ替えがソートの最後に同じ順序に戻ることができるので、順序が変更された場合は必ずしもあなたに伝えません。
2つの等しい値が交換された場合、範囲が変更されたとみなしますか？この場合、already_sortedバリアントは機能しません。
それ以外の場合は、最速の方法です。
ええと...私は 'std :: stable_sort'を使ってこのケースを解決すると思います。 – Inverse
ソートされたオブジェクトは、クラス型である場合は、std::swapによって呼び出されますoperator =過負荷でサブオブジェクトをもたらす可能性があります。しかし、オブジェクトがスワップされてからスワップバックされると、理論上は誤検出が可能になります。
おそらく、合計実行時間が大幅に短縮されるまで、already_sortedを使用してください。
私は、（b）は安全だとは思わない：アルゴリズムは 'comp（a、b）'の代わりに 'comp（b、a）'をテストし、結果が '偽です。 –
私はより良い質問は、範囲が既にソートされているかどうかを知る必要がある理由だと思います。ソートされた範囲を「安全な」方法で処理するソートアルゴリズムを選択する必要があるでしょう。範囲はソートされていますか？ –
@ Jeff：私のアプリケーションにはソートされた範囲を生成する可能性のあるプロセスがあります。そうでない場合は、いくつかのステップを繰り返す必要があります。 – Inverse