Home > Backend Development > C++ > body text

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

Linda Hamilton
Release: 2024-10-29 20:20:03
Original
551 people have browsed it

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>
Copy after login

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!

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!