`std::sort`가 작은 범위에 대한 사용자 정의 `swap` 함수 호출을 피하는 이유는 무엇입니까?

std::sort 효율성을 위해 std::swap을 피할 수 있음

질문:

사용자 정의 스왑 함수와 함께 사용자 정의 유형 A를 사용하는 다음 코드를 고려하세요.

<code class="cpp">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"; // Custom swap function
}</code>

n이 20으로 설정되면 사용자 정의 스왑 함수가 사용되고 배열이 정렬됩니다. 그러나 n이 4로 설정되면 사용자 정의 스왑 기능이 호출되지 않습니다.

답변:

작은 범위의 경우(예: n은 4), GCC의 stdlibc(및 기타 표준 라이브러리 구현)의 std::sort 구현은 성능상의 이유로 삽입 정렬로 전환

삽입 정렬 최적화:

GCC 구현의 삽입 정렬은 교체에 대해 다른 접근 방식을 사용합니다.

1. 내부적으로 std::move_backward를 사용하여 한 번에 전체 값 범위를 이동합니다.
2. 컴파일러의 실험적인 C 11 기능이 활성화되지 않은 경우 std::move_backward는 이동 대신 복사를 사용할 수 있습니다.

이러한 최적화는 불필요한 스왑을 방지하여 성능을 향상시킵니다. 요소를 개별적으로 교체하는 대신 배열의 일부가 이동되어 한 번의 작업으로 여러 번의 교체를 효과적으로 수행합니다.

결론:

작은 배열을 정렬할 때 std:: sort는 사용자 정의 스왑 함수 호출을 피하기 위해 삽입 정렬을 사용할 수 있습니다. 이 최적화는 성능을 향상시킬 수 있지만 개체 복사에 비용이 많이 드는 경우 고려해야 합니다.

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