为什么 `std::list::sort()` 切换到自上而下的合并排序方法？

STL：重新思考 std::list::sort()

传统上，std::list::sort() 使用以下方法实现自下而上的归并排序算法指针。然而，从 Visual Studio 2015 开始，标准库转而采用自上而下的合并排序策略。尽管最初认为由于每个递归级别上的重复顺序扫描导致效率低下，但仔细检查代码会发现不同的情况。

自上而下的方法及其优点

而不是扫描列表进行分割，自上而下的方法递归地将整数大小除以 2，通过减少元素比较的次数来实现更快的合并。此外，最初使用 std::next 来定位中点可能看起来效率低下，但它利用列表的属性来有效地将列表分成两半。

使用迭代器的更改避免了内存分配并确保异常安全。如果比较函数抛出异常，列表将保持有序，不会丢失任何数据。在合并逻辑中使用 std::list::splice 可以在原始列表中高效移动节点，进一步增强其稳定性和异常处理能力。

性能注意事项

与初始相反假设，在某些情况下，std::list::sort() 中的自上而下的归并排序通常优于自下而上的归并排序。对于节点分散或内存有限的列表，自上而下的合并排序表现出更好的缓存行为，从而加快执行速度。但是，如果内存充足，将列表移动到数组或向量并以该格式对其进行排序通常会更有效。

使用迭代器的替代自下而上归并排序

尽管效率较高与自上而下的方法相比，有些人试图修改自下而上的归并排序以与迭代器一起使用，从而消除对列表数组的需要。这种方法利用迭代器数组来跟踪排序的运行边界，并使用 std::list::splice 进行合并，实现与自顶向下方法类似的结果。

结论

切换到std::list::sort() 中自上而下的合并排序并不是一个仓促的决定，而是经过仔细考虑的优化，它带来了显着的性能和稳定性改进。虽然自上而下的方法可能并不总是理想的，但它在某些场景中已经证明了其价值，提供了更快、更可靠的排序算法。

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