Why Does `std::sort` Not Always Call `std::swap` for Small Ranges?

std::sort Does Not Always Call std::swap

In certain cases, std::sort may not invoke the custom swap function defined for a given data type. This behavior has been observed in GCC's stdlibc implementation and is particularly apparent when working with small ranges of elements.

For performance efficiency, GCC's std::sort implementation employs insertion sort for ranges below a certain size. This is because insertion sort is faster than quicksort or introsort for small datasets. However, insertion sort does not utilize the defined swap function. Instead, it performs a direct move of the entire element range to achieve faster performance.

This behavior is illustrated in the code snippet below:

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

When n is set to 20, the custom swap function is called, and the array is sorted correctly. However, if n is reduced to 4, the custom swap function is not invoked, but the array is vẫn được still correctly sorted.

This behavior can become problematic when working with expensive-to-copy objects. To mitigate this issue, consider using an implementation of std::sort that always calls the provided swap function. Additionally, you may want to report this behavior to the GCC developers for further optimization.

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