std::sort가 작은 범위에 대해 사용자 정의 스왑 함수를 호출하지 않는 이유는 무엇입니까?

std::sort가 항상 std::swap을 호출하지는 않습니다

질문:

다음 코드에서 std::sort가 더 큰 범위(n=20)에 대해 호출되었음에도 더 작은 범위(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까지 한 단계 위로 이동한 후 __first에 임시 값을 다시 삽입합니다. 이렇게 하면 n개의 값을 개별적으로 이동할 필요 없이 한 번의 작업으로 n개의 스왑을 수행합니다.

위 내용은 std::sort가 작은 범위에 대해 사용자 정의 스왑 함수를 호출하지 않는 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!