std::list::size() は C では本当に O(1) ですか?

Is std::list::size() Really O(n)?

std の時間計算量に関して懸念が提起されていますC の ::list::size() 。標準では複雑さが指定されていないにもかかわらず、実装に依存している可能性があると示唆する人もいます。

実装固有の動作

以前のバージョンの C では、 std の複雑さは次のとおりです。 :list::size() は、使用される STL 実装によって異なります。 Microsoft Visual Studio V6 は一定の複雑さで実装しましたが、GCC 4.1.0 までは距離ベースのアプローチを使用していたため、複雑さは O(n) でした。

標準化と複雑さ

C 11 では、n2923 によって変更が導入され、すべての標準コンテナー .size() 操作が定数時間計算量を持つことが要求されました。 (お(1))。これは現在、明示的な要件となっており、実装間で一貫したパフォーマンスを保証します。

GCC 実装

ただし、標準化にもかかわらず、 std::list::size( ) バージョン 4.8 までの GCC では、引き続き O(n) アルゴリズムが採用されています。これについては、元の質問でリンクされているブログ エントリで詳しく説明されています。

GCC 5.0 での更新

この問題は GCC 5.0 で解決されていることに注意することが重要です。後で。 C 11 モードでは、std::list::size() は GCC 5.0 以降で O(1) の複雑さで適切に実装されます。

libc 実装

GCC のアプローチとは対照的に、 libc の std::list::size() の実装は一貫して最適化されています。 O(1) 当初からの複雑さ。

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