为什么 std::sort 不为小范围调用我的自定义交换函数？

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

问题：

在下面的代码中，为什么在较小范围（n=4）执行 std::sort 时未调用自定义交换函数，即使在较大范围（n=20）中调用它？

<code class="cpp">#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A&amp; rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A&amp; lhs, A&amp; 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";
}

答案：

对于小范围，GCC 的 stdlibc（和其他标准库实现）中的 std::sort 实现出于性能原因使用插入排序。插入排序不使用 std::swap 来交换元素。相反，它一次移动整个范围的值，可能会节省性能。

GCC 插入排序实现中的相关代码（bits/stl_algo.h:2187，GCC 4.7.2）是：

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

此代码将当前位置 (__i) 的值移动到临时存储，将所有先前的值从 __first 向上移动到 __i，然后在 __first 处重新插入临时值。通过这样做，它可以在一次操作中执行 n 次交换，而不必单独移动 n 个值。

以上是为什么 std::sort 不为小范围调用我的自定义交换函数？的详细内容。更多信息请关注PHP中文网其他相关文章！