C++ FAQ / Section 38 / FAQ 38.8

 E-mail the author
[ Subject index | About the author | © ]
Revised Jul 4, 2012

[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);
  throw;
}
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).