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中文网其他相关文章!