Std::Sort Does Not Always Call Std::Swap

std::sort does not always call std::swap

For small ranges, std::sort implementations in GCC’s stdlibc++ (and other standard library implementations) recurs to insertion sort for performance reasons (it’s faster than quicksort / introsort on small ranges).

GCC’s insertion sort implementation in turn doesn’t swap via std::swap – instead, it moves whole ranges of values at a time, instead of swapping individually, thus potentially saving performance. The relevant part is here (bits/stl_algo.h:2187, GCC 4.7.2):

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

_GLIBCXX_MOVE is the same as std::move from C++11 and _GLIBCXX_MOVE_BACKWARD3 is std::move_backward – however, this is only the case if __GXX_EXPERIMENTAL_CXX0X__ is defined; if not, then these operations resort to copying instead of moving!

What this does is move the value at the current position (__i) to a temporary storage, then move all previous values from __first to __i one up, and then re-insert the temporary value at __first. So this performs n swaps in one operation instead having to move n values to a temporary location:

  first           i
+---+---+---+---+---+---+
| b | c | d | e | a | f |
+---+---+---+---+---+---+
                  |
  <---------------+

  first           i
+---+---+---+---+---+---+
| --> b-> c-> d-> e-> f |
+---+---+---+---+---+---+

  first           i
+---+---+---+---+---+---+
| a | b | c | d | e | f |
+---+---+---+---+---+---+
  ^

Why is swap called by std::sort only if my container has more than 32 elements?

Microsoft std::sort implementation looks like this:

const int ISORT_MAX = 32;  // maximum size for insertion sort

template<class RanIt, class Diff, class Pr>
void Sort(RanIt First, RanIt Last, Diff Ideal, Pr Pred)
{
    Diff Count;
    for (; ISORT_MAX < (Count = Last - First) && 0 < Ideal; )
    {   // divide and conquer by quicksort
        pair<RanIt, RanIt> Mid = Unguarded_partition(First, Last, Pred);

        // ...
    }

    if (ISORT_MAX < Count)
    {   // heap sort if too many divisions
        Make_heap(First, Last, Pred);
        Sort_heap(First, Last, Pred);
    }
    else if (1 < Count)
        Insertion_sort(First, Last, Pred);  // small
}

When the range to be sorted has 32 elements or less, Sort uses insertion sort. Insertion sort doesn't use swap in its implementation. Otherwise, divide-and-conquer quick sort is used. In the implementation it calls iter_swap (inside Unguarded_partition), which in turn calls swap:

template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 Left, FwdIt2 Right)
{   // swap *Left and *Right
    swap(*Left, *Right);
}

All these are implementation details. They vary from one standard library implementation to another.

How do I make std::sort not have name collision between std::swap and my namespace's templated swap?

A workaround is to create a better overload:

// No modifiable code
namespace my
{
    template<class T> void swap(T a, T b) { /*.. */ }
    struct Obj { /*..*/ };
}

// Your code:
namespace my
{
    void swap(Obj& lhs, Obj& rhs)
    {
        // my::swap<Obj&>(lhs, rhs);
        std::swap(lhs, rhs);
    }
}

// In namespace you want.
void doSortStuff()
{
    std::vector<my::Obj> arr;
    std::sort(arr.begin(), arr.end());
}

Then, between the 3 valid overloads, all are exact match, but the non-template is preferred.

std::sort and custom swap function

I have one proposal for you: make the index array the one you sort and keep the values as global array. From then on: sort based on comparator that accepts indices, but actually compares based on the values.

Why doesn't the sort algorithm on this code invoke the class's version of swap?

std::sort is not required to sort the elements by swapping them. If it does, then it will use the correct version of swap, but it can choose to use other methods. For example, it can call std::rotate, which moves ranges of elements.

sort() - No matching function for call to 'swap'

It turns out it's a very simple problem, but not very obvious to spot (and the error message doesn't do a very good job in helping out either):

Remove the const declaration on run() - voilá.

---

Related Topics