最新の実装では 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() 関数は内部データ構造を使用して要素数を追跡し、実質的に操作を O(1) にします。これは、すべての標準コンテナの C 11 要件と一致しています。

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