為什麼在 Visual Studio 2015 中 `std::list::sort()` 切換到自上而下的合併排序？

為什麼 std::list::sort() 突然切換到自上而下策略？

在Visual Studio 中2015年（VS2015），微軟將std::list::sort()的排序策略從傳統的自下而上的歸併排序轉換為自上而下的方法。此變更消除了內部列表數組的使用，並採用迭代器來追蹤原始列表中的排序運行邊界。

更改的原因

Stephan T. Lavavej自上而下方法的開發人員指出需要避免記憶體分配和非預設分配器的構造。 VS2015 引入了不再預設可構造和有狀態的分配器，這在使用以前的自下而上方法時帶來了問題。

自上而下方法的實作

頂部-down 方法利用遞歸演算法，將列表遞歸地分成兩半，直到達到列表為空或包含單一元素的基本情況。函數 _Sort 將清單分為三段：左遊、右遊、結束迭代器。合併邏輯是使用 std::list::splice 來移動原始清單中的節點，從而保持異常安全。

效能注意事項

而自頂向下該方法解決了記憶體分配問題，但與原始的自下而上的歸併排序相比，它會帶來性能損失。對於節點分散的大型列表，自上而下的方法會受到快取未命中增加的影響，從而導致執行時間變慢。在這種情況下，將清單移至陣列或向量，對其進行排序，然後從排序後的陣列或向量建立新清單可能會更快。

以上是為什麼在 Visual Studio 2015 中 `std::list::sort()` 切換到自上而下的合併排序？的詳細內容。更多資訊請關注PHP中文網其他相關文章！