为什么对于小数据集，`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>

此操作在一个快速操作中模拟 n 次交换。因此，不会调用自定义交换函数。

值得注意的是，仅当定义了 GXX_EXPERIMENTAL_CXX0X 时，_GLIBCXX_MOVE 才会调用 std::move。否则，它将默认复制值。

以上是为什么对于小数据集，`std::sort` 避免使用 `std::swap`？的详细内容。更多信息请关注PHP中文网其他相关文章！