std::sort does not always call std::swap
Consider the following code:
#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";
}
If I use n=20 , the custom swap function is called and the array is sorted. But if I use n=4 , the array is sorted correctly, but the custom swap function is not called. Why is that? What if it is really expensive to copy my objects?
For this test, I was using gcc 4.5.3.
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 |
+---+---+---+---+---+---+
^
Depending on the type, swapping can be more expensive than a move-assignment (in C++98 a simple assignment). The standard library doesn't have any way to detect these cases. At least in C++11 the solution is clear: implement a move-assignment operator for all classes where you implement swap.
I modified the code to be more verbose. The sorting for 20 elements uses many swaps, uses assignment end copy. Sorting for 4 elements uses only assignment and copy. Don't know about the specs, but it might be something to go on.
#include <algorithm>
#include <iostream>
#include <vector>
namespace my_space
{
struct A
{
double a;
double* b;
A()
: a(0)
, b(NULL)
{ }
A(const A &rhs)
: a(rhs.a)
, b(rhs.b)
{
std::cerr << "copy" << std::endl;
}
A& operator=(A const &rhs)
{
if(this==&rhs)
return *this;
a = rhs.a;
b = rhs.b;
std::cerr << "=" << std::endl;
return *this;
}
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);
}
} // namespace my_space
int main()
{
const int n = 20;
std::cerr << "=== TEST CASE: n = " << n << std::endl;
std::cerr << "=== FILL ===" << std::endl;
std::vector<my_space::A> vec(n);
for (int i = 0; i < n; ++i) {
vec[i].a = -i;
}
std::cerr << "=== PRINT ===" << std::endl;
for (int i = 0; i < n; ++i) {
std::cerr << vec[i].a << " ";
}
std::cerr << "n";
std::cerr << "=== SORT ===" << std::endl;
std::sort(vec.begin(), vec.end());
std::cerr << "=== PRINT ===" << std::endl;
for (int i = 0; i < n; ++i) {
std::cerr << vec[i].a << " ";
}
std::cerr << "n";
}
Outputs
=== TEST CASE: n = 4
=== FILL ===
copy
copy
copy
copy
=== PRINT ===
0 -1 -2 -3
=== SORT ===
copy
=
=
copy
=
=
=
copy
=
=
=
=
=== PRINT ===
-3 -2 -1 0
And
=== TEST CASE: n = 20
=== FILL ===
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
=== PRINT ===
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19
=== SORT ===
copy
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
=
copy
=
copy
=
copy
=
=== PRINT ===
-19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0