`std::sort`가 작은 범위에 대해 항상 `std::swap`을 호출하지 않는 이유는 무엇입니까?

std::sort가 항상 std::swap을 호출하지는 않음

어떤 경우에는 std::sort가 사용자 정의 스왑을 호출하지 않을 수 있습니다. 주어진 데이터 유형에 대해 정의된 함수입니다. 이 동작은 GCC의 stdlibc 구현에서 관찰되었으며 작은 범위의 요소로 작업할 때 특히 두드러집니다.

성능 효율성을 위해 GCC의 std::sort 구현은 특정 크기 미만의 범위에 대해 삽입 정렬을 사용합니다. 이는 작은 데이터세트의 경우 삽입 정렬이 퀵 정렬이나 내부 정렬보다 빠르기 때문입니다. 그러나 삽입 정렬에서는 정의된 스왑 기능을 활용하지 않습니다. 대신 전체 요소 범위를 직접 이동하여 더 빠른 성능을 달성합니다.

이 동작은 아래 코드 조각에 설명되어 있습니다.

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double a;
    double* b;
    bool operator<(const A& rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& 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";
}</code>

n이 20으로 설정되면 사용자 정의 스왑 함수가 호출되고 배열이 올바르게 정렬됩니다. 그러나 n이 4로 줄어들면 사용자 정의 스왑 기능이 호출되지 않지만 배열은 여전히 ​​올바르게 정렬되어 있습니다.

이 동작은 복사 비용이 많이 드는 객체로 작업할 때 문제가 될 수 있습니다. 이 문제를 완화하려면 제공된 스왑 함수를 항상 호출하는 std::sort 구현을 사용하는 것이 좋습니다. 또한 추가 최적화를 위해 이 동작을 GCC 개발자에게 보고할 수도 있습니다.

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