std :: sort并不总是调用std :: swap [英] std::sort does not always call 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 ，则该数组已正确排序，但是自定义交换函数未调用 。这是为什么？如果复制对象真的很昂贵怎么办？

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?

在此测试中，我使用的是gcc 4.5.3。

For this test, I was using gcc 4.5.3.

推荐答案

对于小范围而言，GCC的stdlibc ++中的 std :: sort 实现（以及其他标准库实现）会重复插入排序性能原因（在小范围内它比quicksort / introsort更快）。

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的插入排序实现又不会通过 std :: swap进行交换 –而是一次移动整个值范围，而不是单独交换，从而有可能节省性能。相关部分在此处（ bits / stl_algo.h：2187 ，GCC 4.7.2）：

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 与<$ c相同$ c> std :: move 从C ++ 11和 _GLIBCXX_MOVE_BACKWARD3 是 std :: move_backward –但是，只有 __ GXX_EXPERIMENTAL_CXX0X __ 被定义；如果不是，那么这些操作将采取复制而不是移动！

_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!

这是将当前位置的值移动（ __ i ）到临时存储，然后将所有先前的值从 __ first 移到 __ i 上，然后在 __ first 处重新插入临时值。因此，这将在一次操作中执行 n 交换，而不必将 n 值移动到临时位置：

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

这篇关于std :: sort并不总是调用std :: swap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！