デストラクタを呼び出す必要があるため、clear() 操作の複雑さはコンテナのサイズに比例することを理解しています。しかし、プリミティブ型 (および POD) はどうでしょうか? 複雑さが一定になるように、ベクター サイズを 0 に設定するのが最善の方法のようです。
これが可能であれば、std::unordered_map でも可能ですか?
4828 次
2 に答える
9
複雑さが一定になるように、ベクター サイズを 0 に設定するのが最善の方法のようです。
一般に、ベクトルを 0 にサイズ変更する複雑さは、現在 .xml に格納されている要素の数に比例しvectorます。したがって、vectorのサイズを 0 に設定しても、呼び出しよりも利点はありませんclear()。この 2 つは本質的に同じです。
ただし、少なくとも 1 つの実装 (libstdc++、 のソースbits/stl_vector.h) では、部分的なテンプレートの特殊化を採用することで、プリミティブ型の複雑さが O(1) になります。
の実装は、重要なコンパイル時の最適化を実行する関数 inにclear()移動します。それは type のテンプレート パラメータで補助テンプレート クラスを宣言します。このクラスには、 に対する部分的な特殊化と に対する明示的な特殊化があります。どちらの特殊化も、 と呼ばれる単一の静的関数を定義します。テンプレート パラメータが の場合、関数本体は空です。パラメータが の場合、ボディにはのデストラクタを呼び出すループが含まれます。std::_Destroy(from, to)bits/stl_construct.h_Destroy_auxbooltruefalse__destroytruefalseTstd::_Destroy(ptr)
トリックは136 行目にあります。
std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);
__has_trivial_destructor補助クラスは、チェックの結果に基づいてインスタンス化されます。チェッカーはtrue、組み込み型、およびfalse非自明なデストラクタを持つ型を返します。その結果、、、およびその他の POD タイプでは、 への呼び出し__destroyはノーオペレーションになります。intdouble
は、オブジェクト自体を削除するのではなく、POD オブジェクトの「ハッシュ バケット」を表す構造を削除する必要がある場合があるという点で とstd::unordered_mapは異なります*。toの最適化は可能ですが、実装に大きく依存するため、当てにはできません。vectorclearO(1)
*正確な答えは実装によって異なります。オープン アドレス指定 (線形プローブ、二次プローブなど) に基づいた衝突解決を実装するハッシュ テーブルは、 内のすべてのバケットを削除できる場合がありO(1)ます。ただし、個別の連鎖に基づく実装では、バケットを 1 つずつ削除する必要があります。
于 2012-11-20T19:35:43.667 に答える
0
std::_Destroy最終的に によって使用されるgcc のバージョンの はclear()、型に自明なデストラクタがあるかどうかに基づいてテンプレートを作成しようとします。そのため、その場合、最適化パスがなくても複雑さは一定です。ただし、テンプレートがどの程度機能するかはわかりません。
于 2012-06-27T23:33:27.530 に答える