`std::sort` が狭い範囲に対してカスタムの `swap` 関数の呼び出しを回避するのはなぜですか?

std::sort 効率を上げるために std::swap を回避できる

質問:

カスタム スワップ関数を使用したユーザー定義型 A を使用した次のコードを考えてみましょう。

<code class="cpp">struct A {
    double a;
    double* b;
    bool operator<(const A& rhs) const {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& rhs) {
    std::cerr << "My swap.\n"; // Custom swap function
}</code>

n が 20 に設定されている場合、カスタム スワップ関数が使用され、配列が並べ替えられます。ただし、n が 4 に設定されている場合、カスタム スワップ関数は呼び出されません。

答え:

狭い範囲の場合 (次のような場合) n は 4)、GCC の stdlibc (およびその他の標準ライブラリ実装) の std::sort 実装は、パフォーマンス上の理由から挿入ソートに切り替えます。

挿入ソートの最適化:

GCC 実装の挿入ソートは、スワッピングに別のアプローチを使用します。

1. 内部で std::move_backward を使用して、一度に値の全範囲を移動します。
2. コンパイラの実験的な C 11 機能が有効になっていない場合、std::move_backward は移動の代わりにコピーを使用することがあります。

この最適化により、不必要なスワップが回避され、パフォーマンスが向上します。要素を個別に交換する代わりに、配列の一部がシフトされ、1 回の操作で複数のスワップが効果的に実行されます。

結論:

小さな配列を並べ替える場合、std:: sort は、カスタム スワップ関数の呼び出しを避けるために挿入ソートを使用する場合があります。この最適化によりパフォーマンスが向上しますが、オブジェクトのコピーにコストがかかる場合は考慮する必要があります。

以上が`std::sort` が狭い範囲に対してカスタムの `swap` 関数の呼び出しを回避するのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。