**Does std::sort Always Call Custom Swap Functions for Small Ranges?**

std::sort Without Custom Swaps for Small Ranges

When working with the std::sort function in C , it's generally expected that custom swap functions provided by the programmer will be called during the sorting process. However, in certain scenarios, this may not be the case. Specifically, for small data ranges, some implementations of std::sort, such as those found in GCC's stdlibc , may utilize insertion sort for performance optimization.

Insertion Sort Optimization

Insertion sort, unlike the default quick or intro sort algorithms used by std::sort, does not use explicit swaps. Instead, it operates by moving blocks of data elements to achieve the sorted order. This approach is faster than individual swaps on small ranges.

In the internal implementation of insertion sort (found in bits/stl_algo.h in GCC 4.7.2), data movement is performed using GLIBCXX_MOVE and _GLIBCXX_MOVE_BACKWARD3 functions. These functions correspond to std::move and std::move_backward in C 11. However, they may resort to copying instead of moving if the __GXX_EXPERIMENTAL_CXX0X macro is not defined.

Impact on Custom Swaps

As a result of the optimizations employed by insertion sort, custom swap functions defined by the programmer may not be called during the sorting of small data ranges. This can be of particular concern if the custom swap function is computationally expensive.

Example

Consider the following code where a custom swap function is implemented and a vector of struct A is sorted:

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

For a small range like n=4, the custom swap function is not called even though the array is correctly sorted. This occurs because insertion sort is employed, which does not require explicit swaps.

Conclusion

It's important to be aware that std::sort may not always utilize custom swaps for small data ranges due to algorithmic optimizations. This can have implications when working with expensive custom swap functions.

The above is the detailed content of **Does std::sort Always Call Custom Swap Functions for Small Ranges?**. For more information, please follow other related articles on the PHP Chinese website!