小さな範囲に対して std::sort が常に std::swap を呼び出すわけではないのはなぜですか?

std::sort は常に std::swap を呼び出すわけではありません

場合によっては、std::sort がカスタム スワップを呼び出さない場合があります特定のデータ型に対して定義された関数。この動作は GCC の stdlibc 実装で観察されており、狭い範囲の要素を操作する場合に特に顕著です。

パフォーマンス効率を高めるため、GCC の std::sort 実装では、特定のサイズ以下の範囲に対して挿入ソートが採用されています。これは、小さなデータセットの場合、挿入ソートの方がクイックソートやイントロソートよりも高速であるためです。ただし、挿入ソートでは定義されたスワップ関数は利用されません。代わりに、要素範囲全体の直接移動を実行して、より高速なパフォーマンスを実現します。

この動作は、以下のコード スニペットに示されています。

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

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 = 20;
    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 が 20 に設定されている場合、カスタム スワップ関数が呼び出され、配列が正しくソートされます。ただし、n が 4 に減らされた場合、カスタム スワップ関数は呼び出されませんが、配列は依然として正しくソートされています。

この動作は、コピーに高価なオブジェクトを扱う場合に問題になる可能性があります。この問題を軽減するには、提供された swap 関数を常に呼び出す std::sort の実装を使用することを検討してください。さらに、さらなる最適化のために、この動作を GCC 開発者に報告することもできます。

以上が小さな範囲に対して std::sort が常に std::swap を呼び出すわけではないのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。