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.
";
    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 << "
";
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "
";
}

如果我使用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 实现出于性能原因递归到插入排序(在小范围内它比快速排序/内排序快).

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++11 中的 std::move 相同，_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屋！