작은 데이터 세트에 대해 `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개의 스왑을 모방합니다. 결과적으로 사용자 정의 스왑 함수가 호출되지 않습니다.

_GLIBCXX_MOVE는 GXX_EXPERIMENTAL_CXX0X가 정의된 경우에만 std::move를 호출한다는 점에 주목할 필요가 있습니다. 그렇지 않으면 기본적으로 값을 복사하게 됩니다.

위 내용은 작은 데이터 세트에 대해 `std::sort`가 `std::swap`을 피하는 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!