为什么“std::sort”并不总是为小范围调用“std::swap”？

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

在某些情况下，std::sort 可能不会调用自定义交换为给定数据类型定义的函数。这种行为已在 GCC 的 stdlibc 实现中观察到，并且在处理小范围元素时尤其明显。

为了提高性能效率，GCC 的 std::sort 实现对低于特定大小的范围采用插入排序。这是因为对于小型数据集，插入排序比快速排序或内插排序更快。但是，插入排序不使用定义的交换函数。相反，它会直接移动整个元素范围以实现更快的性能。

下面的代码片段说明了此行为：

<code class="cpp">#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";
}</code>

当 n 设置为 20 时，调用自定义交换函数，并且数组已正确排序。但是，如果 n 减少到 4，则不会调用自定义交换函数，但数组仍然正确排序。

在处理复制成本高昂的对象时，此行为可能会出现问题。为了缓解此问题，请考虑使用始终调用提供的交换函数的 std::sort 实现。此外，您可能需要向 GCC 开发人员报告此行为以进行进一步优化。

以上是为什么“std::sort”并不总是为小范围调用“std::swap”？的详细内容。更多信息请关注PHP中文网其他相关文章！