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

Question

Possible Duplicates:
How does the standard new operator work in c++?
How does delete[] “know” the size of the operand array?

Dupe of http://stackoverflow.com/questions/197675/how-does-delete-know-the-size-of-the-operand-array

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

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.

Answer 2

My guess is that new[] actually allocates more data than it seems. It probably has a few bytes before the pointer that is returned that tells how many items are in the array.

Answer 3

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 4

How this is done is a compiler specific detail. But the call to delete[], assuming no memory corruption, will always delete the right number of elements. There are several ways to achieve this but one simple way is to hide the length in the memory.

Here's a nice and simple way to implement this for demonstration purposes. Say your code calls new int[10]. Instead of allocating 10 * sizeof(int), the compiler allocates (10 * sizefo(int))+sizeof(size_t). It then returns a pointer to you which is offset size_t from the start. Inside that initial size_t space it writes the number 10. Now when you call delete[] and pass in a pointer, the compiler just goes backward size_t bytes and finds the number of elements to delete.

Answer 5

The mechanism is implementation-dependent, but it will not be "fooled", by you reassigning the pointer in your example. It will deallocate the array of size 9, just like you told it to (and in this case there will be a memory leak because the array of size 5 now has nothing pointing to it).

Answer 6

How delete[] works is implementation-dependent, but the global new operator associates a descriptor with the allocated memory in some way (in most cases, it's prepended to the allocated memory, or stored in a lookup table). The descriptor contains the actual size of the memory that was allocated.

In your second code example, delete[] will correctly delete the nine-element array of int, and the original five-element array will be leaked.

Answer 7

You could imagine that the system store the size of the table in a structure like this:

struct MemoryAllocated
  {
  size_t sizeOfMemory;
  char* yourData;
  }

each type your allocating some memory, the system returns a pointer to 'yourData'. And each type your memory is 'free', the system shift the pointer to get the 'sizeOfMemory'. See also std::allocator