2

クリア関数の時間計算量は std::map ですか?
それが O(1) であると言うのは正しいでしょうか?

4

4 に答える 4

5

標準は[associative.reqmts]/8 表 102で次のように述べています。

a.clear()<=>a.erase(a.begin(), a.end()) 線形a.size()

したがって、実際には O(N) であることが義務付けられています。

EDIT：さまざまなビットをまとめます。

ノードを削除するには、次のmap2 つの操作を行います。

  1. アロケータdestroyメソッドを呼び出して要素を破棄する
  2. allocatordeallocateメソッドを呼び出して、ノードが占有しているメモリの割り当てを解除します

前者はコードで省略できます（ をチェックしますis_trivially_destructible）。実際には、一般的vectorに例で行われます。後者は残念ながらよりトリッキーであり、trait が存在しないため、オプティマイザーに依存する必要があります。

destroy残念ながら、オプティマイザーがインライン化によってノードとノードを完全に削除deallocateできたとしても、ツリー トラバーサルが役に立たなくなったことに気づき、それを最適化することもできないのではないかと心配しています。したがって、ツリーの Θ(N) トラバーサルになってしまい、各ステップで何も行われません...

于 2012-06-12T09:44:45.377 に答える
2

cplusplusリファレンスサイトは、各要素のデストラクタを呼び出す必要があるため、コンテナのサイズが直線的に複雑であると主張しています。

于 2012-06-12T09:30:02.467 に答える
2

これはテンプレートであるため、コンパイル時に型 (例: std::map<int>) のノーオペレーションで破棄されることがわかっている可能性があるため、メンバーを破棄する必要性は、必要な最悪の場合のパフォーマンスを推測するための適切な根拠にはなりません。それでも、コンパイラはバイナリ ツリーのすべてのノードにアクセスしてヒープ メモリを解放する必要があり、ノードの数は要素の数に直線的に関係します (erase()消去された要素へのイテレータ/参照/ポインタのみを無効にし、insert()その他は無効にしません)。 . すべてが 1:1 の関係を証明しています)。

したがって、線形ですが、要素のデストラクタが必要ない場合でもヒープの使用をクリーンアップする必要があるため....

(興味深いことに、これは、すべてのメモリが専用のメモリ プールから割り当てられた場合、自明な no-op デストラクタを持つ要素に対して、 のstd::map<>ような連想コンテナ、またはおそらくstd::map<>それ自体が巧妙なカスタム アロケータを使用して O(1) になる可能性があることを意味します。 O（1）で「捨てられた」）

于 2012-06-12T09:38:12.073 に答える
1

私が知っているように、これらのオブジェクトを 1 つずつ破棄する必要があるため、クリーン操作の複雑さはすべて O(n) です。

于 2012-06-12T09:36:50.110 に答える