最新の C 実装では `std::list::size()` は本当に O(1) なのでしょうか?

最新の実装では std::list::size() は本当に O(n) ですか?

最近、一部の開発者は次のように提案していますstd::list::size() には線形時間計算量 (O(n)) があります。ただし、C 標準によれば、複雑さは定義されておらず、実装によって異なる場合があります。

C 標準 (C 03) の以前のバージョンでは、size() 操作の複雑さは一定であることが推奨されていました。 (お(1))。しかし、C 11 の導入により、これはすべての標準コンテナの要件になりました。 C 11 標準の表 96 では、.size() はすべてのコンテナに対して一定の複雑度を持つ必要があると明示的に述べられています。

歴史的に、GCC の libstdc ライブラリは std:: distance(begin を使用して複雑度 O(n) で size() を実装していました。 ()、end())、引用したブログエントリで説明されているように。ただし、C 11 モードでは、この動作が変更されました。

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

GCC 5.0 以降では、size() 関数は内部データ構造を使用して要素数を追跡し、操作を効果的に実行します。 ○(1)。これは、すべての標準コンテナの C 11 要件と一致しています。

一部のニッチなユースケースでは、依然として size() の複雑さが O(n) になる可能性があることに注意することが重要ですが、大多数のユーザーにとっては、操作は一定時間である必要があります。

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