65

std::list::size()最近、線形の複雑性があると言及している人がいることに気付きました。一部の情報源
に よると、これは実際には実装に依存しているため、標準では複雑さがどうあるべきかが規定されていません。このブログエントリ のコメントには次のように書かれています。

実際には、使用している STL によって異なります。Microsoft Visual Studio V6 は size() を {return (_Size); として実装します。} 一方、gcc (少なくともバージョン 3.3.2 および 4.1.0 では) は { return std::distance(begin(), end()); のように行います。最初の速度は一定で、2 番目の速度は o(N) です。

  1. したがって、私の推測では、VC++ クラウドsize()は常に複雑であり、Dinkumware はおそらく VC6 以降その事実を変えていないでしょう。私はそこにいますか？
  2. 現在はどのように見えますgccか? それが本当に O(n) である場合、なぜ開発者はそうすることにしたのですか?
4

7 に答える 7

81

C++11 では、標準コンテナーの場合.size()、操作は「一定の」複雑さ (O(1)) で完了する必要があります。(表 96 — コンテナー要件)。以前は、C++03 では複雑さが一定である必要がありましたが、必須ではありません ( .size() Is std::string size() a O(1) operation?を参照してください)。

標準の変更はn2923: Specifying the complex of size() (Revision 1)によって導入されました。

ただし、libstdc++ での の実装は.size() 、4.8 までの gcc で O(N) アルゴリズムを引き続き使用します。

  /**  Returns the number of elements in the %list.  */
  size_type
  size() const _GLIBCXX_NOEXCEPT
  { return std::distance(begin(), end()); }

c++11 で std::list が大きくなるのはなぜですか?も参照してください。詳細については、このように保持されています。

更新:C++11 モード (またはそれ以上) でgcc 5.0std::list::size()を使用する場合、適切に O(1)です。

ちなみに、.size()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& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}
于 2012-12-06T20:17:28.343 に答える
52

Pre-C++11の回答

規格には複雑さがどうあるべきかが明記されていないのは正しいですが、list::size()「一定の複雑さを持つべきである」ことを推奨しています（表65の注A）。

これはハワード・ヒナントによる興味深い記事で、なぜ一部の人々list::size()がO（N）の複雑さを持つべきだと考えるのか（基本的にはO（1）がO（N）の複雑さを持つと信じているためlist::size()）list::splice()、なぜO（1）list::size()が良い考えであるのかを説明しています（著者の意見では）：

この論文の要点は次のとおりです。

  • 内部カウントを維持してlist::size()O（1）になると、スプライス操作が線形になる状況はほとんどありません。
  • 誰かがO（N）を呼び出すために発生する可能性のある悪影響に気付かない可能性がある状況はおそらくもっとたくさんあります（ロックを保持しているときに呼び出されるsize()彼の1つの例など）。list::size()
  • 「驚き最小の原則」のために、O（N）を許可する代わりに、標準では、O（1）方式で実装するために実装size()するすべてのコンテナーを要求する必要があります。size()コンテナがこれを実行できない場合は、実装size()しないでください。この場合、コンテナのユーザーsize()は利用できないことを認識し、コンテナ内の要素の数を取得する必要がある場合は、container::distance( begin(), end())その値を取得するために使用できますが、それがO（N）操作。

私は彼の推論のほとんどに同意する傾向があると思います。しかし、私は彼が提案したオーバーロードへの追加が好きではありませんsplice()。n正しい振る舞いを得るために等しくなければならないを渡さなければならないことdistance( first, last)は、バグを診断するのが難しいためのレシピのように思えます。

変更を加えると既存のコードに大きな影響を与えるため、今後何をすべきか、何ができるかわかりません。しかし、現状では、既存のコードはすでに影響を受けていると思います。明確に定義されているはずの実装では、動作が実装ごとにかなり異なる可能性があります。サイズが「キャッシュ」され、既知/不明とマークされていることについてのonebyoneのコメントは、うまくいく可能性があります-償却されたO（1）動作を取得します-O（N）動作を取得するのは、リストがいくつかのsplice（）操作によって変更されたときだけです。これの良いところは、標準を変更せずに、今日の実装者が実行できることです（何かが足りない場合を除く）。

私の知る限り、C++0xはこの領域で何も変更していません。

于 2008-10-23T08:14:05.640 に答える
15

以前に gcc 3.4 を調べる必要があったので、次のlist::sizeように言えます。

  1. を使用していますstd::distance(head, tail)。
  2. std::distanceには 2 つの実装があります。RandomAccessIteratorを満たす型の場合は "tail-head" を使用し、単にInputIteratorを満たす型の場合は "iterator++" に依存する O(n) アルゴリズムを使用し、指定された末尾に到達するまでカウントします。
  3. std::listはRandomAccessIteratorを満たさないため、サイズは O(n) です。

std::list「理由」については、シーケンシャル アクセスが必要な問題に適しているとしか言えません。サイズをクラス変数として保存すると、挿入、削除などのたびにオーバーヘッドが発生し、その無駄は STL の意図からして大したことではありません。本当に定数時間が必要な場合はsize()、を使用してstd::dequeください。

于 2008-10-23T17:25:18.600 に答える
13

個人的には、サイズが O(N) であることが許可される唯一の理由として、スプライスが O(N) であるという問題を見ていません。使わないものにはお金を払わないというのは、C++ の重要なモットーです。この場合、リストのサイズを維持するには、リストのサイズをチェックするかどうかにかかわらず、挿入/消去ごとに追加のインクリメント/デクリメントが必要です。これは小さな固定オーバーヘッドですが、考慮することは依然として重要です。

リストのサイズを確認する必要はほとんどありません。合計サイズを気にせずに最初から最後まで反復することは、無限に一般的です。

于 2008-10-23T13:21:39.170 に答える
5

ソース（アーカイブ）に行きます。SGIのSTLページには、線形の複雑さを持つことが許可されていると記載されています。彼らが従った設計ガイドラインは、リストの実装を可能な限り一般的にし、リストをより柔軟に使用できるようにすることだったと思います。

于 2008-10-23T08:18:07.770 に答える
1

このバグ レポート: [C++0x] std::list::size complex は、GCC 4.x での実装が線形時間であるという事実と、C++11 の定数時間への移行がどのように遅かったかという事実を非常に詳細に捉えています。 ABI の互換性の問題により、近日中に (5.0 で利用可能) になります。

GCC 4.9 シリーズのマンページには、次の免責事項がまだ含まれています。

C++11 のサポートはまだ実験段階であり、将来のリリースでは互換性のない方法で変更される可能性があります。

同じバグ レポートがここで参照されています。

于 2015-12-04T01:57:25.847 に答える