**std::sort는 작은 범위에 대해 항상 사용자 정의 스왑 함수를 호출합니까?**

작은 범위에 대한 사용자 정의 스왑이 없는 std::sort

C에서 std::sort 함수를 사용할 때 일반적으로 예상되는 사항은 다음과 같습니다. 프로그래머가 제공하는 사용자 정의 스왑 기능은 정렬 프로세스 중에 호출됩니다. 그러나 특정 시나리오에서는 그렇지 않을 수도 있습니다. 특히 작은 데이터 범위의 경우 GCC의 stdlibc 에 있는 것과 같은 일부 std::sort 구현에서는 성능 최적화를 위해 삽입 정렬을 활용할 수 있습니다.

삽입 정렬 최적화

삽입 정렬은 std::sort에서 사용하는 기본 빠른 정렬 또는 소개 정렬 알고리즘과 달리 명시적인 스왑을 사용하지 않습니다. 대신, 정렬된 순서를 달성하기 위해 데이터 요소 블록을 이동하여 작동합니다. 이 접근 방식은 작은 범위의 개별 스왑보다 빠릅니다.

삽입 정렬의 내부 구현(GCC 4.7.2의 비트/stl_algo.h에 있음)에서 데이터 이동은 GLIBCXX_MOVE 및 _GLIBCXX_MOVE_BACKWARD3을 사용하여 수행됩니다. 기능. 이러한 함수는 C 11의 std::move 및 std::move_backward에 해당합니다. 그러나 __GXX_EXPERIMENTAL_CXX0X 매크로가 정의되지 않은 경우 이동 대신 복사에 의존할 수 있습니다.

사용자 정의에 미치는 영향 스왑

삽입 정렬의 최적화 결과, 작은 데이터 범위를 정렬하는 동안 프로그래머가 정의한 사용자 정의 스왑 함수가 호출되지 않을 수 있습니다. 이는 사용자 정의 스왑 함수가 계산 비용이 많이 드는 경우 특히 문제가 될 수 있습니다.

예

사용자 정의 스왑 함수가 구현되는 다음 코드와 구조체의 벡터를 고려해보세요. A가 정렬되었습니다:

<code class="c++">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 = 4;
    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=4와 같은 작은 범위의 경우 배열이 올바르게 정렬되었더라도 사용자 정의 스왑 함수가 호출되지 않습니다. 이는 명시적인 스왑이 필요하지 않은 삽입 정렬을 사용하기 때문에 발생합니다.

결론

std::sort가 항상 사용자 정의 스왑을 활용하는 것은 아니라는 점을 아는 것이 중요합니다. 알고리즘 최적화로 인해 작은 데이터 범위의 경우. 이는 비용이 많이 드는 사용자 정의 스왑 기능을 사용할 때 영향을 미칠 수 있습니다.

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