std::sort が狭い範囲に対してカスタム スワップ関数を呼び出さないのはなぜですか?

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

質問:

次のコードでは、より大きな範囲 (n=20) で std::sort が呼び出されているにもかかわらず、より小さな範囲 (n=4) で実行されるとカスタム スワップ関数が呼び出されないのはなぜですか?

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

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A&amp; rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A&amp; lhs, A&amp; 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";
}

答え:

狭い範囲の場合、GCC の stdlibc の std::sort 実装 (およびその他の標準ライブラリ実装) は、パフォーマンス上の理由から挿入ソートを利用します。挿入ソートでは、要素の交換に std::swap は使用されません。代わりに、一度に値の全範囲を移動するため、パフォーマンスが節約される可能性があります。

GCC の挿入ソート実装 (bits/stl_algo.h:2187、GCC 4.7.2) の関連コードは次のとおりです。

<code class="cpp">typename iterator_traits<_RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</code>

このコードは、現在の位置 (__i) の値を一時ストレージに移動し、以前のすべての値を __first から __i まで 1 つ上に移動してから、一時値を __first に再挿入します。そうすることで、n 個の値を個別に移動するのではなく、1 回の操作で n 回のスワップが実行されます。

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