Why doesn\'t std::sort call my custom swap function for small ranges?

std::sort Doesn't Always Call std::swap

Question:

In the following code, why is the custom swap function not called when std::sort is executed with a smaller range (n=4), even though it is called for a larger range (n=20)?

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A&amp; rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A&amp; lhs, A&amp; 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";
}

Answer:

For small ranges, std::sort implementations in GCC's stdlibc (and other standard library implementations) utilize insertion sort for performance reasons. Insertion sort does not use std::swap for swapping elements. Instead, it moves whole ranges of values at a time, potentially saving performance.

The relevant code in GCC's insertion sort implementation (bits/stl_algo.h:2187, GCC 4.7.2) is:

<code class="cpp">typename iterator_traits<_RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);</code>

This code moves the value at the current position (__i) to a temporary storage, moves all previous values from __first to __i one up, and then re-inserts the temporary value at __first. By doing so, it performs n swaps in one operation rather than having to move n values individually.

The above is the detailed content of Why doesn\'t std::sort call my custom swap function for small ranges?. For more information, please follow other related articles on the PHP Chinese website!