std :: sort并不总是调用std :: swap

Question

请考虑以下代码:

#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.

Answer 1

对于小范围,std::sortGCC的stdlibc ++(以及其他标准库实现)中的实现由于性能原因而重复出现插入排序(它比小范围上的quicksort/introsort更快).

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是一样的std::move从C++ 11和_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 |
+---+---+---+---+---+---+
  ^