std::list::sort() でトップダウン戦略に突然切り替えたのはなぜですか?

Visual Studio の場合2015 (VS2015)、Microsoft は std::list::sort() の並べ替え戦略を、従来のボトムアップ マージ ソートからトップダウン アプローチに切り替えました。この変更により、リストの内部配列の使用が排除され、元のリスト内でソートされた実行境界を追跡するために反復子が採用されました。

変更の理由

Stephan T. Lavavejトップダウンアプローチの開発者である彼は、メモリ割り当てとデフォルト以外のアロケータの構築を避ける必要性を挙げました。 VS2015 では、デフォルトで構築可能でステートフルではなくなったアロケーターが導入されました。これにより、以前のボトムアップ アプローチを使用するときに問題が発生しました。

トップダウン アプローチの実装

トップ-down アプローチでは、リストが空であるか単一の要素を含む基本ケースに達するまで、リストを再帰的に半分に分割する再帰アルゴリズムを利用します。関数 _Sort は、リストを左ラン、右ラン、および終了反復子の 3 つのセグメントに分割します。マージ ロジックは std::list::splice を使用して実行され、元のリスト内でノードを移動し、例外の安全性を維持します。

パフォーマンスに関する考慮事項

トップダウンこのアプローチはメモリ割り当ての問題に対処しますが、元のボトムアップ マージ ソートと比較してパフォーマンスが低下します。ノードが散在する大きなリストの場合、トップダウンのアプローチではキャッシュ ミスが増加し、実行時間が遅くなります。このような場合、リストを配列またはベクトルに移動し、並べ替えて、並べ替えられた配列またはベクトルから新しいリストを作成する方が速い場合があります。