std::list::sort(): なぜトップダウンのマージソートに移行するのでしょうか?

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

からの切り替えstd::list<>::sort() におけるボトムアップからトップダウンへのマージ ソートは、より堅牢で例外安全なソートの必要性に対処するために生まれました。以前の実装では内部リストの配列を使用していましたが、VS2015 ではデフォルトで構築できないステートフルなアロケーターが導入されたため、問題が発生する可能性がありました。

これを回避するために、Microsoft の Stephan T. Lavavej 氏は、イテレーターを使用して次のことを行うことを提案しました。元のリンク リスト内の実行境界を追跡します。これにより、マージ操作中に std::list::splice を使用してリスト内でノードを移動できるようになり、例外の安全性が確保されます。この変更により堅牢性は向上しますが、中間点を見つけるためにリンク リストをスキャンするのは非効率的になる可能性があるため、パフォーマンスのコストが発生します。

しかし、Microsoft は Visual Studio 2022 アップデートで、次のようにトップダウン実装を強化しました。リストを反復処理するのではなく、整数サイズを単純に半分にする、より効率的な再帰戦略に切り替えます。この変更により、例外安全性の利点が維持され、std::next の繰り返し呼び出しによるパフォーマンスの低下が回避されます。

トップダウンのアプローチの代替として、一部の開発者は、次のようなボトムアップのマージ ソートを使用することを提案しています。このドキュメントの前半で紹介した反復子。このアプローチでも反復子が使用されますが、ボトムアップ方式で動作するため、リストをスキャンして中間点を見つける必要がなくなります。具体的な実装は、リストのサイズとノードの分布に依存し、時間と空間の複雑さの間のトレードオフがあります。

std::list ではトップダウンのマージ ソートがデフォルトのままです<> ::sort() は、VS2022 で変更された実装であり、効率と例外の安全性のバランスを提供することを目的としています。開発者は、アプリケーションの特定の要件に応じて、イテレータを使用したボトムアップのマージ ソートなどの代替実装を検討する場合があります。

以上がstd::list::sort(): なぜトップダウンのマージソートに移行するのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。