C++ステートメントのBig-O 'delete [] Q;' O（1）またはO（n）？

Question

タイトルは自明です。非常に簡単な質問です。私はそれがO（n）だと思うが、私の最後の明日の前に確認したい。

Answer 1

短い答えは...それに依存します。

Qがデストラクタを持つオブジェクトの配列へのポインタの場合、delete[] Qはすべてのデストラクタを呼び出す必要があります。これはO（n）デストラクタを呼び出します。ここで、nは配列内の要素の数です。一方、Qがデストラクタを持たないオブジェクトの配列（たとえば、intsまたは単純なstruct）を指している場合は、O（1）時間だけかかるデストラクタを呼び出す必要はありません。

これらのデストラクタはそれぞれO（1）で実行する必要はありません。オブジェクトが、例えば、std::vectorオブジェクトの場合、各デストラクタは順番に、より多くの割り当て解除を解除しなければなりません。これらのオブジェクトが何であるかを知らなければ、デストラクタが呼び出されると、デストラクタが些細な場合は0個のデストラクタが呼び出され、それ以外の場合はO（n）デストラクタが呼び出されます。

しかし、ヒープアロケータの仕組みの実装の詳細は無視されます。メモリブロックの割り当てを解除すると、O（ログK）時間がかかる可能性があります。ここでKは割り当てられたブロックの総数です。メモリのブロック数に関係なくO（1）時間かかる場合があります。 O（ログログK）など。アロケータがどのように動作するかを知らずに、あなたは正直にはわからない。つまり、ブロックをメモリアロケータに渡す前にオブジェクトをクリーンアップするために必要な作業のみに焦点を当てると、格納されているオブジェクトにデストラクタがある場合はO（n）デストラクタ、それ以外の場合は0デストラクタが呼び出されます。これらのデストラクタは、完了までに時間がかかりません。次に、メモリブロックをメモリアロケータに再導入するコストがかかります。メモリアロケータには時間がかかることがあります。

希望すると便利です。

Answer 2

私はそれに賛同しますが、Xバイトのメモリを解放し、デストラクタを心配する必要はありません。

いくつかのメモリアロケータは、「小さな」（1〜500バイト）オブジェクトの空きリストを保持します。リストへの挿入はO（1）です。すべてのスレッドに対して1つの空きリストがある場合、ミューテックスを取得する必要があります。ミューテックスを取得するには、通常、最大2000個の "スピン"が必要で、システムコール（非常に高価です）が必要です。一部のアロケータは、スレッドローカルストレージを使用するスレッドごとに空きリストを持っているため、mutexは取得されません。

中規模（500〜60000バイト）のサイズのオブジェクトの場合、多くのアロケータはブロック結合を行います。つまり、隣接するブロックも空いているかどうかをチェックし、2つまたは3つの空きブロックを結合して1つ大きな空きブロックを作成します。合体はO（1）ですが、再びミューテックスを取得する必要があります。

大規模なブロックの場合、一部のアロケータはシステムコールを使用してメモリを取得します。したがって、メモリを解放することもシステムコールです。