Visual Studio 2015 で `std::list::sort()` がトップダウン マージ ソートに切り替わったのはなぜですか?

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

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

変更の理由

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

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

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

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

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

以上がVisual Studio 2015 で `std::list::sort()` がトップダウン マージ ソートに切り替わったのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。