std::list::size() はすべての実装で本当に O(1) ですか?

std::list::size(): 本当に O(n)?

一部の個人は std: :list::size() は線形の複雑さを持ちますが、その複雑さに関する真実は実装に依存します。 C 標準では、この関数の複雑さの要件は指定されていません。

実装のバリエーション

• Microsoft Visual Studio VC : 古いバージョン(VC6 など)、size() は確かに一定の複雑さを持っていました。
• GNU Compiler Collection (GCC): 歴史的に (GCC 4.1.0 まで)、size() は、 O(n) アプローチでは、リストを反復処理して次の数を数えます。

GCC の現在の状態

C 11 では、C 標準により、すべての標準に対して size() 操作が義務付けられています。 std::list を含むコンテナーは、一定の複雑さ (O(1)) を持たなければなりません。これは、プラットフォームや実装間で一貫性のある効率的なランタイム動作を保証するためです。

Libstdc での実装

C 11 の義務にもかかわらず、size() の実装はlibstdc (GCC で使用される標準ライブラリ) の は、以前の GCC バージョンでは O(n) のままでした。 4.8.これは、パフォーマンス上の理由と、リスト構造内の追加のサイズ フィールドを維持するオーバーヘッドを最小限に抑えるために行われました。

更新: O(1) GCC 5.0 での実装

GCC 5.0 のリリースにより、size() が実装されました。 std::list は、C 11 モードで O(1) の複雑さを達成するために最終的に最適化されました。これは、リスト内の要素の数を追跡する内部サイズ フィールドを導入し、サイズ情報への定時アクセスを提供することで実現されました。

結論

std::list::size() の複雑さは過去に議論のテーマでしたが、現在の C 標準ではすべての標準で O(1) の複雑さが必要ですコンテナ。 GCC 5.0 以降のバージョンの実装はこの要件に準拠しており、std::list. に対する size()

の効率的かつ予測可能な実行を保証します。

以上がstd::list::size() はすべての実装で本当に O(1) ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。