c++ - 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

对于小范围，出于性能原因，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 |
+---+---+---+---+---+---+
  ^