Time complexity of delete[] operator

Question

What is the Time Complexity of the delete[] operator?

I mean how is it implemented - does it iterate over all the elements in the array and calls destructor for every element?

Does this operator do the same for primitive types (int, etc.) and user defined types?

Answer 1

::operator delete[] is documented on cplusplus.com (which is sometimes frowned upon) as:

operator delete[] can be called explicitly as a regular function, but in C++, delete[] is an operator with a very specific behavior: An expression with the delete[] operator, first calls the appropriate destructors for each element in the array (if these are of a class type), and then calls function operator delete[] (i.e., this function) to release the storage.

so the destructor is called n times (once for each element), and then the memory freeing "function" is called once.

^{Notice that each destruction might take a different time (or even complexity) than the others. Generally most destructions are quick, and have the same complexity.... But that won't be the case if each destroyed element is a complex tree or node or graph...}

For primitive types like int the fictitious destructor of int is a no-op. The compiler probably would optimize that (if asked).

You should check the real C++11 standard, or at least its late n3337 working draft, which says (thanks to Matteo Italia for pointing that in a comment) in §5.3.5.6 page 110 of n3337:

If the value of the operand of the delete-expression is not a null pointer value, the delete-expression will invoke the destructor (if any) for the object or the elements of the array being deleted. In the case of an array, the elements will be destroyed in order of decreasing address (that is, in reverse order of the completion of their constructor; see 12.6.2)

If you use -and trust enough- GCC 4.8 or better, you could have used the g++ compiler with the -fdump-tree-phiopt or -fdump-tree-all option (beware, they are dumping a lot of files!), or the MELT plugin, to query the intermediate Gimple representation of some example. Or use -S -fverbose-asm to get the assembler code. And you also want to add optimization flags like -O1 or -O2 ...

^{NB: IMHO, cppreference.com is also an interesting site about C++, see there about delete (as commented by Cubbi)}

Answer 2

The implementation of delete and delete[] is composed of two phases:

1. recursive call to destructors (if any)
2. memory deallocation for deleted object

Let alone the chain of calls to destructors, whose complexity is essentially governed by you, we are left with how the memory is freed to consider.

The second point is not covered by the C++ specification. So, any compiler suite/OS is free to adopt its own strategy.

A common memory allocation/deallocation strategy is allocating a whole memory page when needed from the OS, then at each new/new[], returning a chunk of the appropriate size, whose length and attributes are then stored inside the page as a header/footer. A corresponding delete/delete[] can be as simple as marking that same chunk as "free", which is clearly O(1).

If the complexity of memory deallocation is O(1), then the complexity of a delete is essentially governed by calls to destructors. The default implementation does (almost) nothing, and it's a O(1) for a single call, thus an overall O(n), where n is the toal number of calls (e.g. if the object being destructed has two fields whose destructor is called, then n = 1 (object) + 2 (o. fields) = 3).

Putting all pieces together: you can arbitrarily increment complexity by performing operations in the destructor (which can be written by you), but you cannot "perform better"¹ than O(n) (n defined in the previous paragraph). The formally correct way to state this is: "the complexity of delete is an Omega(n)".

---

¹ allow me to be a bit informal on this point

Answer 3

For class types, the theoretical complexity is O(n). The destructor is called for each element. Of course, it's up to the implementation to adhere to the observable behavior, so if the destructor is a no-op or the behavior is the same as with just marking the whole chunk as freed, the complexity could be just O(1).

For primitive types, the compiler will likely just release the whole chunk of memory at once, thus the complexity O(1).

Answer 4

What is the Time Complexity of the delete[] operator?

The amount of the time required is of course implementation defined. However, the operator applies only to the pointer to the 1D array and thus it's O(1).

I mean how is it implemented - does it iterate over all the elements in the array and calls destructor for every element?

Yes.
Provided that it's called only on the exact pointer which is assigned a memory created using new[]. For primitive types there are no user defined destructors.

Does this operator do the same for primitive types (int, etc.) and user defined types?

The comparison is not fair, because primitive types don't have user defined destructor and they cannot be polymorhpic.
For example, delete[] on a polymorphic class is an undefined behavior. i.e.

Base* p1 = new Derived, *p2 = new Derived[2];
delete p1; // ok
delete[] p2;  // bad