異なる C バージョンにおける `std::list::size()` の時間計算量はどのくらいですか?

std::list::size() 複雑さ: わかりやすく解説

一般に線形であると認識されていますが、std::list の複雑さは次のとおりです。 :size() は驚くほど微妙です。当初、その複雑さは C 標準で未指定のままであったため、実装に依存した変動が生じていました。

実装固有の不一致

Microsoft Visual Studio V6 では、std:: list::size() は、{return (_Size);} スキームに準拠した定数時間操作として実装されます。ただし、gcc バージョン 3.3.2 から 4.1.0 では、O(N) アルゴリズムが採用されていました。 }。この違いは、リスト全体を走査する必要がある距離関数の使用に起因しています。

C 11 での標準化

C 11 では、標準が義務付ける重大な変化が発生しました。 .size() は、std::list を含むすべての標準コンテナに対して「一定の」複雑さを示さなければなりません。これにより、以前の実装の不均衡が効果的に排除されます。

GCC 実装ラグ

この標準化にもかかわらず、4.8 より前の gcc バージョンの libstdc は、引き続き O(N) アルゴリズムを使用し続けました。 std::list の .size()。この決定の一部は、アルゴリズムの変更による潜在的なパフォーマンスへの影響によるものでした。

更新と改善

この状況は、gcc 5.0 以降で大幅に改善されました。 ::size() は、C 11 でコンパイルされたときに最終的に O(1) に最適化されました。 mode.

Libc 実装

libc では、 std::list の .size() 関数は一貫して O(1) です。これは、リストのサイズを追跡するために使用される圧縮ペア データ構造によって促進され、効率的かつ迅速なサイズの取得が保証されます。

結論として、std::list::size() の複雑さは歴史的に実装されていました。 -依存ですが、C 11 標準では、準拠するすべての実装に対して O(1) に標準化されています。実装の詳細はコンパイラやバージョンによって異なる場合がありますが、定数時間の複雑さに対する基本的な要件は変わりません。

以上が異なる C バージョンにおける `std::list::size()` の時間計算量はどのくらいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。