**std::sort は常に狭い範囲に対してカスタム スワップ関数を呼び出しますか?**

狭い範囲のカスタム スワップを使用しない std::sort

C で std::sort 関数を使用する場合、一般に次のことが期待されます。プログラマが提供するカスタム スワップ関数は、並べ替えプロセス中に呼び出されます。ただし、特定のシナリオでは、これが当てはまらない場合があります。具体的には、小さいデータ範囲の場合、GCC の stdlibc にあるような std::sort の一部の実装では、パフォーマンスの最適化のために挿入ソートを利用することがあります。

挿入ソートの最適化

挿入ソートは、std::sort で使用されるデフォルトのクイックまたはイントロ ソート アルゴリズムとは異なり、明示的なスワップを使用しません。代わりに、ソートされた順序を達成するためにデータ要素のブロックを移動することによって動作します。このアプローチは、狭い範囲での個別のスワップよりも高速です。

挿入ソートの内部実装 (GCC 4.7.2 の bits/stl_algo.h にあります) では、データの移動は GLIBCXX_MOVE および _GLIBCXX_MOVE_BACKWARD3 を使用して実行されます。機能。これらの関数は、C 11 の std::move および std::move_backward に対応します。ただし、__GXX_EXPERIMENTAL_CXX0X マクロが定義されていない場合、移動ではなくコピーが行われる可能性があります。

カスタムへの影響Swaps

挿入ソートによって採用された最適化の結果、プログラマによって定義されたカスタム スワップ関数は、小さなデータ範囲のソート中に呼び出されない場合があります。これは、カスタム スワップ関数の計算コストが高い場合に特に問題となる可能性があります。

例

カスタム スワップ関数が実装されている次のコードと構造体のベクトルを考えてみましょう。 A はソートされています:

<code class="c++">namespace my_space
{
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";
    std::swap(lhs.a, rhs.a);
    std::swap(lhs.b, rhs.b);
}
}

int main()
{
    const int n = 4;
    std::vector<my_space::A> vec(n);
    for (int i = 0; i < n; ++i) { vec[i].a = -i; }
    for (int i = 0; i < n; ++i) { std::cerr << vec[i].a << " "; }
    std::cerr << "\n";
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; ++i) { std::cerr << vec[i].a << " "; }
    std::cerr << "\n";
}</code>

n=4 のような狭い範囲では、配列が正しくソートされていてもカスタム スワップ関数は呼び出されません。これは、明示的なスワップを必要としない挿入ソートが使用されているために発生します。

結論

std::sort が常にカスタム スワップを利用するとは限らないことに注意することが重要です。アルゴリズムの最適化による小さなデータ範囲の場合。これは、高価なカスタム スワップ関数を使用する場合に影響を与える可能性があります。

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