How does delete[] know the size of an array?

Question

I am curious how delete[] figures out the size of the allocated memory. When I do something like:

int* table = new int[5];
delete[] table;

I understand that the memory of the table is freed. But what would happen if I reassigned the pointer to some different table.

int* table = new [5];
int* table2 = new [9];
table = table2;
delete[] table;

Will I free a table of the size 5 or 9? I am interested in how new[] and delete[] share information about their size. Or maybe I am missing something essential here.

Answer 1

It would delete an array of size 9. It deletes the array pointed to by the pointer.

It is unspecified how the size information is stored, so each compiler may implement it in a different way, but a common way to do it is to allocate an extra block before the array. That is, when you do this:

int* table = new int[5];

it actually allocates an array of 6 integers, and stores the array size in the first element. Then it returns a pointer to the second element. So to find the size, delete[] just has to read table[-1], basically.

That's one common way to do it, but the language standard doesn't specify that it must be done in this way. Just that it has to work.

Another approach might be to use the address of the array as a key into some global hash table. Any method is valid, as long as it produces the correct results.

Answer 2

Section 16.14 of the C++ FAQ lite answers this:

There are two popular techniques that do this. Both these techniques are in use by commercial-grade compilers, both have tradeoffs, and neither is perfect. These techniques are:

* Over-allocate the array and put n just to the left 
  of the first Fred object.
* Use an associative array with p as the key and n as the value.