Why Does `std::sort` Avoid `std::swap` for Small Datasets?

std::sort's Avoidance of std::swap with Small Datasets

In this code snippet, an array of custom objects is created and passed to 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());

The custom swap function in my_space is defined as:

<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);
}
}  

Upon execution, the following phenomenon is observed: when n is set to 20, the custom swap function is called and the array is successfully sorted. However, when n is set to 4, the array is sorted without invoking the custom swap function.

This behavior stems from std::sort's use of insertion sort for small ranges. In GCC's stdlibc implementation, insertion sort is employed for performance reasons. Here's what happens internally:

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

This operation mimics n swaps in one swift action. As a result, the custom swap function is not called.

It's noteworthy that _GLIBCXX_MOVE will invoke std::move only if GXX_EXPERIMENTAL_CXX0X is defined. Otherwise, it will default to copying the values.

The above is the detailed content of Why Does `std::sort` Avoid `std::swap` for Small Datasets?. For more information, please follow other related articles on the PHP Chinese website!