std::list::sort()：为什么要转向自上而下的合并排序？

std::list<>::sort()：为什么突然切换到自上而下策略？

从std::list::sort() 中自下而上到自上而下的合并排序的出现是为了满足更强大和异常安全排序的需求。之前的实现使用了内部列表数组，但这可能会遇到问题，因为 VS2015 中引入了非默认可构造和有状态分配器。

为了避免这种情况，Microsoft 的 Stephan T. Lavavej 建议使用迭代器跟踪原始链表中的运行边界。这允许在合并操作期间使用 std::list::splice 移动列表内的节点，从而确保异常安全。虽然此更改提高了鲁棒性，但它确实会带来性能成本，因为扫描链表来查找中点可能效率很低。

但是，在 Visual Studio 2022 更新中，微软通过以下方式增强了自上而下的实现：切换到更有效的递归策略，其中整数大小简单地减半，而不是迭代列表。此修改保留了异常安全的好处，并避免了重复调用 std::next 的性能损失。

作为自上而下方法的替代方法，一些开发人员建议使用自下而上的合并排序迭代器，如本文档前面介绍的。这种方法也使用迭代器，但以自下而上的方式操作，无需扫描列表来查找中点。具体实现取决于列表的大小和节点的分布，并在时间和空间复杂度之间进行权衡。

虽然 std::list 中自上而下的合并排序仍然是默认的，但::sort()，VS2022中修改后的实现旨在提供效率和异常安全性的平衡。开发人员可以根据应用程序的具体要求探索替代实现，例如使用迭代器的自下而上合并排序。

以上是std::list::sort()：为什么要转向自上而下的合并排序？的详细内容。更多信息请关注PHP中文网其他相关文章！