** std::sort 是否始终调用小范围的自定义交换函数？**

std::sort 没有小范围的自定义交换

在 C 中使用 std::sort 函数时，通常期望排序过程中将调用程序员提供的自定义交换函数。然而，在某些情况下，情况可能并非如此。具体来说，对于小数据范围，std::sort 的某些实现（例如 GCC 的 stdlibc 中的实现）可能会利用插入排序来进行性能优化。

插入排序优化

插入排序与 std::sort 使用的默认快速或介绍排序算法不同，不使用显式交换。相反，它通过移动数据元素块来实现排序顺序。这种方法比小范围内的单独交换更快。

在插入排序的内部实现中（在 GCC 4.7.2 中的 bits/stl_algo.h 中找到），使用 GLIBCXX_MOVE 和 _GLIBCXX_MOVE_BACKWARD3 执行数据移动功能。这些函数对应于 C 11 中的 std::move 和 std::move_backward。但是，如果未定义 __GXX_EXPERIMENTAL_CXX0X 宏，它们可能会诉诸复制而不是移动。

对自定义的影响交换

由于插入排序采用的优化，在小数据范围排序期间可能不会调用程序员定义的自定义交换函数。如果自定义交换函数的计算成本很高，这可能会特别令人担忧。

示例

考虑以下代码，其中实现了自定义交换函数和结构体向量A 已排序：

<code class="c++">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 = 4;
    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=4 这样的小范围，即使数组已正确排序，也不会调用自定义交换函数。发生这种情况是因为采用了插入排序，不需要显式交换。

结论

重要的是要注意 std::sort 可能并不总是使用自定义交换由于算法优化，适用于小数据范围。当使用昂贵的自定义交换函数时，这可能会产生影响。

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