为什么'std::sort”避免为小范围调用自定义'swap”函数？

std::sort 可以避免 std::swap 以提高效率

问题：

考虑以下使用用户定义类型 A 和自定义交换函数的代码：

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

当 n 设置为 20 时，使用自定义交换函数并对数组进行排序。然而，当 n 设置为 4 时，自定义交换函数不会被调用。

答案：

对于小范围（例如当n 为 4)，GCC 的 stdlibc 中的 std::sort 实现（以及其他标准库实现）出于性能原因切换到插入排序。

插入排序优化：

GCC 实现中的插入排序使用不同的交换方法：

1. 它一次移动整个值范围，内部使用 std::move_backward。
2. 如果未启用编译器的实验性 C 11 功能，std::move_backward 可能会使用复制而不是移动。

此优化通过避免不必要的交换来提高性能。不是单独交换元素，而是移动数组的一部分，从而在一次操作中有效地执行多次交换。

结论：

对小数组进行排序时，std:: sort 可以使用插入排序来避免调用自定义交换函数。这种优化可以提高性能，但在复制对象成本高昂时应考虑。

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