`std::list::size()` は常に O(1) ですか?

Is list::size() 本当に O(1)?

かつては std::list::size が真でしたが() は実装間でさまざまな複雑さを示しましたが、C 11 ではその動作が標準化されています。コンテナ要件の表 96 では、すべての標準コンテナの .size() 操作に一定の複雑さ (O(1)) を義務付けています。

ただし、バージョン 5.0 より前の gcc の libstdc 実装には注目すべき例外が残っています。 C 11 標準要件にもかかわらず、その .size() 関数は、次の抜粋に示すように O(N) アルゴリズムを採用しています:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return std::distance(begin(), end()); }

この決定は、 libstdc 内の最適化を考慮した結果です。リストを走査するのではなく要素の個別の数を維持すると、標準の複雑さの要件に反しますが、一部のユースケースではパフォーマンスが向上します。一方、

Libc の実装は O(1) に正しく準拠しています。次のコード スニペットで示されているように、複雑さは次のとおりです。

_LIBCPP_INLINE_VISIBILITY
size_type size() const _NOEXCEPT     {return base::__sz();}

...

__compressed_pair<size_type, __node_allocator> __size_alloc_;

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

結論として、C 11 標準では、O(1) の複雑性が義務付けられています。 std::list::size()、バージョン 5.0 より前の gcc の libstdc 実装は依然として異常であり、代わりに O(N) アルゴリズムを採用しています。

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