小さなデータセットに対して std::sort が std::swap を避けるのはなぜですか?

std::sort による小規模データセットでの std::swap の回避

このコード スニペットでは、カスタム オブジェクトの配列が作成され、 std::sort に渡されます。

<code class="cpp">std::vector<my_space::A> vec(n);
for (int i = 0; i < n; ++i) {
  vec[i].a = -i;
}

std::sort(vec.begin(), vec.end());

my_space のカスタム スワップ関数は次のように定義されています:

<code class="cpp">namespace my_space
{
struct A
{
  double a;
  double* b;
};

void swap(A& lhs, A& rhs)
{
  std::cerr << "My swap.\n";
  std::swap(lhs.a, rhs.a);
  std::swap(lhs.b, rhs.b);
}
}  

実行すると、次の現象が観察されます: n が 20 に設定されている場合、カスタム スワップ関数が呼び出され、配列が正常に並べ替えられます。ただし、n が 4 に設定されている場合、配列はカスタム スワップ関数を呼び出さずにソートされます。

この動作は、std::sort が狭い範囲に対して挿入ソートを使用することに起因します。 GCC の stdlibc 実装では、パフォーマンス上の理由から挿入ソートが採用されています。内部で何が起こるかは次のとおりです。

<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>

この操作は、1 つの素早いアクションで n 回のスワップを模倣します。その結果、カスタム スワップ関数は呼び出されません。

GXX_EXPERIMENTAL_CXX0X が定義されている場合にのみ、_GLIBCXX_MOVE が std::move を呼び出すことに注意してください。それ以外の場合は、デフォルトで値がコピーされます。

以上が小さなデータセットに対して std::sort が std::swap を避けるのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。