Why Does `std::sort` Avoid Calling a Custom `swap` Function for Small Ranges?

std::sort Can Avoid std::swap for Efficiency

Question:

Consider the following code using user-defined type A with custom swap function:

<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>

When n is set to 20, the custom swap function is used and the array is sorted. However, when n is set to 4, the custom swap function is not called.

Answer:

For small ranges (such as when n is 4), std::sort implementations in GCC's stdlibc (and other standard library implementations) switch to insertion sort for performance reasons.

Insertion Sort Optimization:

Insertion sort in GCC's implementation uses a different approach to swapping:

1. It moves whole ranges of values at a time, using std::move_backward internally.
2. If the compiler's experimental C 11 features are not enabled, std::move_backward may use copying instead of moving.

This optimization improves performance by avoiding unnecessary swaps. Instead of swapping elements individually, a portion of the array is shifted, effectively performing multiple swaps in one operation.

Conclusion:

When sorting small arrays, std::sort may use insertion sort to avoid invoking the custom swap function. This optimization can improve performance but should be considered when copying objects is costly.

The above is the detailed content of Why Does `std::sort` Avoid Calling a Custom `swap` Function for Small Ranges?. For more information, please follow other related articles on the PHP Chinese website!