ベクトルを消去または消去するC++の最速の方法

Question

私は、0〜5000の要素でベクトルを日常的に埋め込むコードを用意しています。私は、最大で5000の代わりにベクトルを複数回初期化する、私は再びベクトルを埋めるために、しかし一度だけ

vector<struct> myvector; 
myvector.reserve(5000); 

をしたいと思っ超えることはありません知っている、私はその容量を変更することなく、第1のベクトルをクリアする必要があります。だから、通常私はmyvector.clear（）を呼び出します。

これはO（n）操作です。私はこれのパフォーマンスを上げるために何か簡単なことがあるのですか、それともこれが得られる最高のものなのでしょうか？

Answer 1

あなたの構造体が自明ではないデストラクタを持っている場合、それは空になる方法にかかわらずベクトルのすべての要素に対して呼び出される必要があります。構造体に些細なデストラクタしかない場合は、コンパイラまたは標準ライブラリの実装で破棄処理を最適化し、O（1）操作を行うことができます。

Answer 2

既存のアイテムをベクターから削除するには、破壊される各アイテムのデストラクタを（潜在的に）呼び出す必要があります。したがって、コンテナの観点から、あなたが望むことができる最良のものは線形の複雑さです。

これは、ベクトルにどのような種類のアイテムを格納するかの問題だけを残します。コンパイラが呼び出すデストラクタを事前に知っている/知っているかもしれないintのようなものを保存すると、削除が一定の複雑さで終わる可能性は少なくともかなりあります。

しかし、構文を変更すると（例えば、resize()対erase(begin(), end())）、大きな違いはありません。この構文は、N個のデストラクタを呼び出す（スレッドがない場合）O（N）操作であるという事実を変えない。

Answer 3

clear()のコストは、格納されたオブジェクトが何であるか、特にそれらが些細なデストラクタを持っているかどうかに大きく依存します。型に些細なデストラクタがない場合、呼び出しはすべての格納されたオブジェクトを破棄しなければならず、実際にはO（n）操作ですが、実際には何もできません。

保存された要素に些細なデストラクタがある場合、実装ではコストを最適化でき、clear()は格安O（1）操作（ちょうどサイズをリセットする-endポインタ）になります。

漸近的な複雑さを理解するには、それが何を話しているかを知る必要があることを忘れないでください。 clear()の場合、それは呼び出されるデストラクタの数を表しますが、コスト（隠された）が0の場合、操作はノーオペレーションです。