std :: sort并不总是调用std :: swap
考虑下面的代码：
#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";
}
如果我使用n=20 ，则调用自定义交换函数并对数组进行排序。 但如果我使用n=4 ，数组排序正确，但不调用自定义交换功能。 这是为什么？ 如果复制我的对象真的很贵吗？
对于这个测试，我使用的是gcc 4.5.3。
对于小范围，GCC的stdlibc ++（以及其他标准库实现）中的std::sort实现为了性能原因（比小范围上的快速排序/内插更快）重新进行插入排序。
GCC的插入排序实现反过来不会通过std::swap - 相反，它会一次移动整个值的范围，而不是单独交换，因此可能会节省性能。 相关部分在这里（ 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与C ++ 11中的std::move相同，而_GLIBCXX_MOVE_BACKWARD3是std::move_backward - 但是，如果定义了__GXX_EXPERIMENTAL_CXX0X__ ，则只有这种情况; 如果不是的话，那么这些操作就会复制而不是移动！
它的作用是将当前位置（ __i ）的值移动到临时存储区，然后将所有先前的值从__first移动到__i一个，然后在__first处重新插入临时值。 因此，这一次执行n次交换，而不必将n个值移动到临时位置：
first i
+---+---+---+---+---+---+
| b | c | d | e | a | f |
+---+---+---+---+---+---+
|
<---------------+
first i
+---+---+---+---+---+---+
| --> b-> c-> d-> e-> f |
+---+---+---+---+---+---+
first i
+---+---+---+---+---+---+
| a | b | c | d | e | f |
+---+---+---+---+---+---+
^
取决于类型，交换可能比移动赋值更昂贵（在C ++ 98中是一个简单的赋值）。 标准库没有任何方法来检测这些情况。 至少在C ++ 11中，解决方案很明确：为所有实现交换的类实施移动赋值运算符。
我修改了代码，使其更加冗长。 20个元素的排序使用许多交换，使用分配结束副本。 对4个元素进行排序只使用赋值和复制。 不知道规格，但可能会继续下去。
#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";
}
输出
=== TEST CASE: n = 4
=== FILL ===
copy
copy
copy
copy
=== PRINT ===
0 -1 -2 -3
=== SORT ===
copy
=
=
copy
=
=
=
copy
=
=
=
=
=== PRINT ===
-3 -2 -1 0
和
=== 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