This chapter is from the book
This chapter is from the book
This chapter is from the book
3.7 Dynamic Memory Allocation
When you design programs, you cannot always determine how much memory you need before your program runs. The length of an array or the number of structures, for example, may be unknown until your executing program determines what these values should be. An area of memory called the free store is available in the C++ run-time environment to handle dynamic memory allocation at run time. Programs use operator new to allocate memory from free store and operator delete to release free store memory. This section introduces new and delete and shows you how to allocate memory dynamically at run time.
Operator new
The predeclared formats for dynamic allocation with operator new are
new Type // one object new Type(initial_value) // one object, initial value new Type[size1] // array of objects new Type[size1][size2][sizeN] // multidimensional array of objects
For now, let's work with objects as C++ built-in types. Operator new allocates one object or an array of objects from free store. There are no default initial values for built-in types. In an expression, operator new returns a nonzero pointer to free store memory if it's available and throws a bad_alloc exception if it is not (see page 649 for a discussion on bad_alloc). The second format allocates one object and initializes it to the value you supply inside the parentheses. The [] notation allocates one-dimensional or multidimensional arrays of objects, where size1 is any integer expression (0 or greater). For multidimensional arrays, size2 through sizeN must be constant integer expressions (1 or greater). With the [] format, operator new returns a pointer to the first element of the array. There is no format to initialize array elements. ("Arrays of Class Objects" on page 236 applies operator new and delete to user-defined object arrays.)
The C++ standard library also provides versions of operator new that do not throw exceptions. These "nothrow" versions are not predeclared; therefore, you must specify include file <new> in order to use them. Here are the formats.
new(nothrow) Type // one object new(nothrow) Type(initial_value) // one object , initial value new(nothrow) Type[size1] // array of objects new(nothrow) Type[size1][size2][sizeN] // multidim array of objects
The nothrow versions of operator new return a nonzero pointer to free store memory if it's available and 0 if it is not.
NOTE
Catch bad_alloc exceptions from the predeclared formats of operator new. Otherwise, use the nothrow versions of operator new with programs that do not include exception handling.
Here are several examples of operator new inside a try block.
try {
int *pn = new int; // one integer
int *pi = new int(5); // one integer, value 5
double *pd = new double(55.9); // one double, value 55.9
int *buf = new int[10]; // pointer to 10 integers
. . .
}
catch (bad_alloc) {
// handle failure from new
}
Each statement declares a pointer to the same type that you use with operator new. Therefore, you may assign (or initialize) operator new's return value to a pointer of the same type without a cast. The last statement assigns operator new's return value (a pointer to the first of 10 uninitialized integers in free store) to integer pointer buf. The following for loop shows you how to fill the integer array with data.
for (int i = 0; i < 10; i++) buf[i] = val; // assign val to each element
Specify include file <new> and argument nothrow to use the nothrow versions.
#include <new> int *pn = new(nothrow) int; // one integer int *pi = new(nothrow) int(5); // one integer, value 5 double *pd = new(nothrow) double(55.9); // one double, value 55.9 int *buf = new(nothrow) int[10]; // pointer to 10 integers
NOTE
Always check the return value of a nothrow version of operator new for zero before you use the pointer to free store.
C++ also provides placement formats for operator new (which require include file <new>).
new(vptr) Type // one object new(vptr) Type(initial_value) // one object, initial value new(vptr) Type[size1] // array of objects new(vptr) Type[size1][size2][sizeN] // multidim array of objects
vptr is a pointer to a previously allocated storage location. Each expression creates one or more objects of type Type at that specified storage location. Placement formats for operator new do not throw exceptions. We show you more about the placement form of operator new in "Free Store Placement" on page 349.
Operator new does not provide a way to initialize array elements. The following attempts, therefore, are illegal.
float *pf = new float[10](55.9); // illegal - can't initialize float *pf = new float(55.9)[10]; // illegal - can't initialize
A for loop with an array of pointers, however, does the job.
const int max = 10; float *pf[max]; // array of pointers to floats for (int i = 0; i < max; i++) // initialize each float and pf[i] = new float(55.9); // assign to pointer pf
Figure 3.4 shows pointer array pf as well as the free store space each array element points to.
)
Figure
3.4. An array of 10 pointers to floats
Operator new allocates free store memory for constants as well. The following statements show the approach.
const double *vision = new const double(55.9);
We use const in both the pointer declaration and with operator new. The initialization format with operator new initializes the const double, since assignment statements such as *vision = 55.9 are illegal with constant types. The use of operator new to allocate const arrays is legal, but problematic (how would you initialize the array elements?).
Operator new is useful with structures, too.
const int MaxNodes = 512;
struct node {
int data;
node *pnode;
};
node *list = new node; // one node
node *block = new node[MaxNodes]; // array of MaxNodes nodes
These statements create a single node and an array of 512 node structures in free store.
Error Handling
What should you do when operator new fails? This section explores three techniques: exceptions, assertions, and set_new_handler().
Exceptions
Exception handling (page 130) provides the default behavior for operator new failures.
try {
const int size = 1024;
int *p = new int[size];
. . .
}
catch (bad_alloc) {
. . .
}
All calls to operator new that fail throw bad_alloc exceptions (see page 649). Catch handlers may display error messages or provide any necessary cleanup. Note that exceptions make it unnecessary to check return values from operator new.
Assertions
Recall that assertions (see Exercise 7 on page 81) terminate your program at run time if their arguments are zero. An assertion, therefore, is a simple way to trap failures from the nothrow versions of operator new.
#include <assert.h> #include <new> . . . double *pd; pd = new(nothrow) double[100]; // array of 100 doubles assert(pd); // same as assert(pd != 0)
Because the nothrow version of operator new returns 0 when it fails to allocate free store memory, assertions can pinpoint the location in your source code where the failure occurs. For example, the following message might appear when a running program called pgm.C is unable to allocate 100 doubles from free store.
Assertion (pd) failed: file pgm.C, line 44.
NOTE
The use of assertions to test failures from operator new can be valuable during the early stages of program development. However, subsequent compiling with -DNDEBUG removes assertions from programs (and removes error checking as well!).
set_new_handler()
A handler function is another alternative for dealing with failures from operator new. In this case, operator new calls your handler function when it fails to allocate free store. This approach requires header file <new> and uses pointers to functions (page 92).
#include <new> . . . typedef void (*PTRF)(); PTRF set_new_handler(PTRF func_name);
The typedef defines PTRF as a pointer to a function with no arguments and no return type. A call to set_new_handler() accepts function name func_name with a void signature and void return type. This name is the handler function you want operator new to call when it fails. The return value from set_new_handler() is a pointer to a function that was the argument to the previous call to set_new_handler(). This capability lets you control which handler functions operator new calls during the execution of a program.
NOTE
Operator new enters a loop when it attempts to allocate free store memory. If your installed new handler returns, make sure that it can supply additional memory. Otherwise, operator new will fail again (and again). If the handler cannot supply additional memory, it should throw exception bad_alloc (or terminate in some other way).
If the handler function returns (and it should return only if memory is available), operator new makes another attempt to allocate free store memory. Here's a program that installs a handler function and tests it use.
Listing 3.17 Example of set_new_handler()
// setnh.c - set_new_handler
#include <iostream.h>
#include <new>
#include <stdlib.h>
const int bsize = 512;
int *psav;
bool allocate = true;
void get_memory() {
cerr << "free store exhausted" << endl;
delete [] psav; // release saved block
allocate = false;
}
void eat_memory(int size) {
int *p = new int[size]; // allocate memory
if (allocate)
eat_memory(size); // recursive call
else
cerr << "free store addr = " << p << endl;
}
int main()
{
set_new_handler(get_memory); // specify handler
psav = new int[bsize]; // block to save
cerr << "free store addr = " << psav << endl;
eat_memory(bsize);
return 0;
}
$ setnh
free store addr = 0x006529e8
free store exhausted
free store addr = 0x006529e8
The program calls set_new_handler() with get_memory, the name of our handler function. Inside main(), we allocate a chunk of memory that we'll free later in our handler function. Note that eat_memory() is a recursive function that consumes the rest of free store with calls to operator new. When operator new eventually fails, it calls get_memory(). This handler function displays a diagnostic message before releasing the saved block of memory with operator delete, which we discuss in the next section. When get_memory() returns, operator new attempts to allocate free store memory again, only this time it succeeds. The allocate boolean terminates the recursion with eat_memory(), and the output from the program verifies that we reclaim the freed space.
NOTE
We recommend exceptions for error handling with operator new because exceptions provide a clean separation between new's implementation and code requesting free store memory. Furthermore, exceptions obviate the need to check return values from each invocation of operator new. For the remainder of this book, we assume that failures to allocate memory from operator new throw bad_alloc exceptions.
Operator delete
Operator delete releases dynamic free store memory that you allocate with operator new. The formats are
delete free_store_ptr; // release one object delete [] free_store_ptr; // release array of objects
The free_store_ptr in both formats must be a pointer previously allocated by operator new. The spaces surrounding [] are optional but improve readability. With arrays, do not place a size within the [] because the free store manager supplies the value you specify with operator new. The use of operator delete with a free store pointer equal to 0 is harmless. Operator delete's return value is void and it does not throw any exceptions.
Here are several examples of operator delete.
#include <new>
int *number = new(nothrow) int; // one integer
delete number; // delete one integer
int *buf = new int[10]; // array of 10 integers
delete [] buf; // delete 10 integers
const char *ps; // ptr to constant char
ps = new const char('#'); // one const character
delete ps; // OK - ps points to const char
We use delete [] with buf because operator new[] allocates an array of 10 integers. Note that a pointer to a constant type is legal with operator delete, as the last example shows.
Suppose you allocate and initialize types with a for loop that calls operator new, as follows.
const int max = 10; float *pf[max]; // array of pointers to floats for (int i = 0; i < max; i++) // initialize each float and pf[i] = new float(55.9); // assign to pointer pf
To release the free store memory properly, use a for loop with operator delete.
for (int i = 0; i < max; i++) // loop through the array delete pf[i]; // delete one float, one at a time
NOTE
When you allocate an array of objects with operator new, use the [] notation with operator delete to release the array. Programs with loops that use operator new to allocate objects one at a time should have corresponding loops to release each object with operator delete (without []).
Failure to release all free store memory that you allocate with operator new is called a memory leak. Programs with memory leaks are not portable or predictable. Memory leaks are difficult to find, so the best way to avoid them is to allocate and deallocate free store memory consistently and accurately with operator new and delete.
References to free store memory are also possible.
short & cake = *(new short(10)); // allocate one short
This statement creates an alias called cake for the (otherwise unnamed) short in free store. We use indirection (*) to dereference operator new's return value and match data types (short). This approach lets you access free store memory with a reference instead of pointer notation.
cake = 5; // assign 5 to short in free store cake++; // increment short in free store
To delete the short integer that cake aliases, use the address operator & with a static cast.
delete static_cast<short *>(&cake);
new and delete with Pointer Arrays
Pointer arrays are arrays of pointers that reside on the stack, in the data area, or in free store. You may use operator new to allocate a pointer array from free store, as well as the memory that the pointer array elements point to. The formats are
new Type *[size1] // one-dimensional array of ptrs new Type *[size1][size2][sizeN] // multidimensional array of ptrs
The rules for size1 through sizeN are the same as for array declarations with operator new. Of course, arrays of pointers to pointers are also possible.
new Type **[size1] // one dim array of ptrs to ptrs new Type **[size1][size2][sizeN] // multidim array of ptrs to ptrs
Pointer array elements do not have initial values.
Operator new always returns a pointer to the type you create.
char *p1 = new char; // one char int **p2 = new int *[10]; // array of 10 pointers float ***p3 = new float **[20] ; // array of 20 ptrs to ptrs
Pointer p1 points to a single character, whereas p2 points to an array of 10 pointers to integers. Likewise, p3 points to an array of 20 pointers to pointers to floats. When creating pointer arrays with operator new and assigning their return values to pointers, make sure you use the correct number of indirections (*) with the pointer (one more than what you use with operator new).
Operators new and delete can be confusing when you are working with pointer arrays. Consider the following.
long **walk; // pointer to pointer to long walk = new long *[10]; // allocate pointer array, 10 ptrs to longs walk[0] = new long; // allocate long for first pointer delete walk[0]; // release first long delete [] walk; // release pointer array long *wait[10]; // pointer array of 10 longs, not free store wait[0] = new long; // allocate long (first pointer), free store delete wait[0]; // release first long
Figure 3.5 shows the memory layout for these pointer arrays. Pointer walk points to free store memory, whereas operator new allocates an array of 10 pointers to longs. The third statement uses operator new to allocate one long in free store and store its address in the first element of the pointer array walk. The first delete statement frees the long from free store, and the second delete statement frees the pointer array. It's important that these two delete statements execute in exactly this order. (Why?)
)
Figure
3.5. Pointer arrays
The second group of statements work with wait, an array of pointers to longs. The wait array resides on the stack or in the data area, depending on where you place its declaration in your code (inside or outside function definitions, respectively). We use the same format with operator new to initialize wait's first element as we do with walk. The last statement uses operator delete to release the long from free store. Note that we do not use [] here, since we did not allocate an array.
Here's another example of pointer arrays.
const int maxlines = 24; char **screen = new char *[maxlines]; // array of pointers to char
We declare screen as a pointer to a pointer (char **) because operator new creates an array of character pointers. The following for loop calls operator new to initialize each screen pointer array element.
const int maxcols = 80; for (int line = 0; line < maxlines; i++) screen[line] = new char [maxcols]; // array of chars
Each call to operator new allocates an array of characters and stores its return pointer (a pointer to the first character of the array) in the lineth element of the screen pointer array. To access individual characters, we use the Basic Rule (page 40) with pointer and array notation, as follows.
screen[5][8] = 'a'; // store 'a' in 6th line, 9th col **screen = 'a'; // store 'a' in screen[0][0]
Which method is preferable—a pointer to a pointer array, or an array of pointers? The answer depends on whether you want the pointer array to be dynamic. When you create a pointer array with operator new in free store, you save its address in a pointer (walk and screen, for example). When you no longer need the array, you release the memory with the pointer and operator delete. The wait pointer array, however, lives in either the stack or the data area. Consequently, you cannot control its release of memory; it's either freed at the end of a block (if the pointer array is automatic) or released when your program terminates (if it's static). Operator delete, on the other hand, may release the pointer arrays addressed by walk and screen at any time during a program's execution.
new and delete with Multidimensional Arrays
It may not always be practical to create large multidimensional arrays on the stack or in the data area at compile time. Operator new, on the other hand, has a format that creates pointers to multidimensional arrays in free store memory at run time.
Type (*pname)[size2][sizeN] = new Type[size1][size2][sizeN];
By the Right-Left Rule (page 97), pname is a pointer to an array whose number of dimensions is one less than the number of dimensions in the array you allocate with operator new. All sizes must be constant integer expressions except the first one with operator new (size1). To release free store memory for the multidimensional array, use the delete [] format with pname.
NOTE
In the above format, don't forget to include parentheses around *pname. If you don't, pname becomes a multidimensional array of pointers, which is incorrect.
The following statements demonstrate how you create and release two-dimensional and three-dimensional arrays with operator new and operator delete.
double (*r)[10] = new double [5][10]; // 2D array (5 x 10) int (*s)[5][10] = new int [2][5][10]; // 3D array (2 x 5 x 10) delete [] r; // delete 2D array delete [] s; // delete 3D array
To see how this format of operator new works, let's review how we create one-dimensional arrays. Consider the following statements.
const int i = 2; // const integer const int val = 5; // const integer int j = 2; // integer float a[i * val]; // legal - constant integer expression float b[j * val]; // illegal - integer expression
We successfully create array a because its size is a constant integer expression. The declaration for array b is illegal because the compiler cannot determine its size at compile time (j is not const and programs may modify it).
When allocating one-dimensional arrays, operator new accepts both integer and constant integer expressions.
float *a = new float[i * val]; // legal - constant integer expr float *b = new float[j * val]; // legal - integer expression
We use free store memory for one-dimensional arrays (a[i] and b[i]) and release the memory for the array with operator delete.
delete [] a; // free array a delete [] b; // free array b
Now let's examine two-dimensional arrays from the same perspective.
const int imax = 2; // const integer const int jmax = 5; // const integer const int j = 2; // const integer int itop = 3; // integer float a[imax][jmax]; // legal - constant integer expressions float m[j * imax][jmax]; // legal - constant integer expressions float b[itop][jmax]; // illegal - itop not const
The last declaration is illegal because itop must be a constant integer expression. We can, however, use operator new to allocate a two-dimensional array of floats from free store, using itop for the number of rows.
float (*b)[jmax] = new float[itop][jmax]; // legal
Figure 3.6 shows the memory layout.
)
Figure
3.6. Two-dimensional arrays with operator new
Pointer b points to the first of three consecutive arrays of jmax (5) floats, from the Right-Left Rule (page 97). The expressions b[0], b[1], and b[2] are the addresses of the first, second, and third rows, respectively, of the two-dimensional array in free store. We use a two-dimensional format for operator new that specifies the number of rows and columns we want. The number of columns (jmax) must be a constant integer expression with this format, but the number of rows need not be a constant integer expression.
Storage map equations (page 100) help explain why. When you use b[i][j] in your program, the compiler uses a storage map equation to locate array elements. This storage map equation requires the number of columns but not the number of rows. Hence, you must use a constant integer expression for the number of columns when you use operator new to allocate two-dimensional arrays. The number of rows may be any integer expression.
Operator delete releases the free store memory for this array.
delete [] b; // release 3 by 5 array of doubles
The free store manager releases all the memory because the number of rows and columns you specify with operator new determines its size (rows times columns).
These concepts apply to three-dimensional arrays, too.
const int imax = 2; // const integer const int jmax = 5; // const integer const int kmax = 6; // const integer int itop = 3; // integer double c[imax][jmax][kmax]; // legal double d[itop][jmax][kmax]; // illegal - itop not const double (*e)[jmax][kmax] = new double[itop][jmax][kmax]; // legal double (*f)[jmax][kmax] = new double[jmax][itop][kmax]; // illegal
Here, e and f are pointers to two-dimensional arrays of doubles, by the Right-Left Rule (page 97). The declaration for e is legal, because itop is the number of grids in a three-dimensional array and does not have to be a constant. This declaration lets you use three-dimensional subscripting (e[i][j][k]) in your code. The declaration for f, however, is illegal because itop (the number of columns) must be a constant integer expression. Operator delete releases the free store memory for e, as follows.
delete [] e;
We can generalize this approach to allocate arrays with operator new for any number of dimensions. Remember, the dimensions of any multidimensional array (except the first) must always be constant integer expressions with operator new. As long as you obey this rule, you may create and release multidimensional arrays "on the fly" with operator new and delete. For a more general solution to creating dynamic multidimensional arrays without this restriction, refer to Listing 9.4 on page 404 and Exercise 9 on page 167.
NOTE
C programs call library routines malloc(), calloc(), realloc(), and free() to allocate, reallocate, and free memory at run time from the heap. C++ programs can still call these routines, but don't intermix heap pointers from these functions with free store pointers from operator new and delete. Programs that do are not portable and may behave strangely.