C++ FAQ Celebrating Twenty-One Years of the C++ FAQ!!!
(Click here for a personal note from Marshall Cline.)
Section 38:
[38.8] How do compilers use an "associative array" to remember the number of elements in an allocated array?

Recall that when you delete[] an array, the runtime system magically knows how many destructors to run. This FAQ describes a technique used by some C++ compilers to do this (the other common technique is to over-allocate).

If the compiler uses the associative array technique, the code for p = new Fred[n] looks something like this (where arrayLengthAssociation is the imaginary name of a hidden, global associative array that maps from void* to "size_t"):

// Original code: Fred* p = new Fred[n];
Fred* p = (Fred*) operator new[] (n * sizeof(Fred));
size_t i;
try {
  for (i = 0; i < n; ++i)
    new(p + i) Fred();           // Placement new
catch (...) {
  while (i-- != 0)
    (p + i)->~Fred();            // Explicit call to the destructor
  operator delete[] (p);
arrayLengthAssociation.insert(p, n);
Then the delete[] p statement becomes:
// Original code: delete[] p;
size_t n = arrayLengthAssociation.lookup(p);
while (n-- != 0)
  (p + n)->~Fred();
operator delete[] (p);
Cfront uses this technique (it uses an AVL tree to implement the associative array).

Compared to the over-allocation technique, the associative array technique is slower, but less sensitive to the problem of programmers saying delete p rather than delete[] p. For example, if you make a programming error by saying delete p where you should have said delete[] p, only the first Fred in the array gets destructed, but the heap may survive (unless you've replaced operator delete[] with something that doesn't simply call operator delete, or unless the destructors for the other Fred objects were necessary).