为什么微软在 std::list::sort() 中切换到自上而下的归并排序？

std::list

尽管长期使用底部-up 归并排序方法在 std::list

最初，人们认为 Microsoft 有令人信服的理由转向效​​率较低的方法，特别是考虑到 VS2015 中引入了非默认可构造和有状态分配器。然而，经过进一步调查，发现原来的自下而上的归并排序算法可以修改为与迭代器一起使用。

微软的自上而下的方法

微软的自上而下的实现使用递归方法在每个递归级别将列表分成两半。这样做的明显原因是为了避免内存分配和异常安全问题。他们没有创建列表数组来存储排序的运行，而是使用迭代器来跟踪原始列表中的运行边界。

虽然这种方法可以防止内存分配问题，但它会以以下形式引入低效率：在每次递归调用中访问列表的中点，可能会导致执行时间变慢。

替代的自下而上方法

作为替代方案，其他开发人员提出了底部的修改版本-up 使用迭代器而不是列表数组的合并排序算法。这种方法涉及创建一个迭代器数组，其中每个条目代表排序运行的起点。扫描列表时，节点将合并到这些运行中，直到获得单个排序列表。

此方法提供了速度和内存效率，在使用内存中分散的节点。

结论

微软转向自上而下归并排序的原因仍然有些不清楚。虽然内存分配和异常安全问题可能会影响决策，但值得注意的是，这些问题可以通过保持更高效率的替代方法来解决。选择效率较低的算法表明 Microsoft 可能优先考虑稳定性和异常处理而不是性能。

以上是为什么微软在 std::list::sort() 中切换到自上而下的归并排序？的详细内容。更多信息请关注PHP中文网其他相关文章！