Pointers and Dynamic Memory Allocation

What are pointers good for?

To answer that, I need to talk about how programs allocate memory.

The memory allocations done in the sample programs so far have all been static memory allocation. Statically allocated memory does not change its size for as long as it exists. Consider, for example, the following statement:

 int thisInteger; 

This statement allocates enough memory to hold one integer. For as long as the variable exists, it can hold only one integer.

What if the program declares an array instead? Is that still static?

The answer is yes. Let's examine an array declaration to see why:

 int theseIntegers[10]; 

The array in the preceding statement allocates space for 10 integers. For as long as this variable exists, it can never hold more than 10 integers. The amount of memory allocated to this array does not change; it is static.

What if a program could change the amount of memory allocated for data as it runs?

It can. We call that dynamic memory allocation. Dynamic memory allocation is a tremendously important tool for programs in general and games in particular.

To understand why dynamic memory allocation is so critical to games, think about what happens in games. Imagine you're playing a game called Invasion of the Obnoxious Chicken Men. You're playing through level 1. You successfully save Lunar Colony 5 from the evil pecking horde of chicken men. You move on to level 2. Do you expect to see all of the same monsters that you saw on level 1? Probably not. Most games introduce new monsters when you move on to a higher level.

If you're writing Invasion of the Obnoxious Chicken Men, you know what kind of monsters there are in the game. In fact, you have to create a class for each type of monster. For instance, you may program a type of chicken man that you call a Mega-Scratcher. Are there MegaScratchers on level 1? Or are they introduced on level 2? That's up to you, but either way you don't write that into your program!

Warning

Do not confuse the term "statically allocated memory" with the C++ keyword static, which you've seen in previous chapters. They refer to two completely unrelated ideas. Confusing, I know, but that's the way it is.

It's true. You don't program your game to know what kind of monsters appear on level 1, what kind appear on level 2, and so forth. Instead, you put that into a special file that you create called a level file. The level file contains information about what kind of monsters appear on each level. The game reads the level file and dynamically allocates whatever monsters it specifies. It then starts the level using the monsters the level file told it to.

Games use dynamic allocation for virtually everything contained in a level. This includes the scenery, opponents, allies, powerups, and so on. The level file tells the game what objects the level contains and the game allocates those objects dynamically. As a result, the game doesn't have to contain code for each individual level. If that were necessary, game programs would be much bigger than they are now. They would be more difficult and expensive to make. Dynamic allocation saves development time and money as well as memory and disk space. In short, you can't write games without dynamic memory allocation.

Allocating Memory

The C++ language contains the new keyword, which is specifically for dynamic memory allocation. You can use it to allocate a single item. For instance, your program can allocate one integer or one MegaScratcher chicken man. The new keyword can allocate any type the compiler recognizes.

Programs can also use the new keyword to allocate groups of items. For example, your program can allocate a group of 100 floating-point numbers, or 25 sprites, or 30 MegaScratchers.

C++ does not limit the size of the block that your program allocates. However, a limit is imposed by the amount of memory available. If the requested amount of memory cannot be allocated, the new keyword returns a value of NULL. The value NULL is a special value defined in the C++ standard libraries.

Every time your program performs a dynamic memory allocation, it should test to ensure that the allocation was successful. Listing 11.2 demonstrates dynamic memory allocation.

Warning

Although some operating systems impose a size limit on blocks of allocated memory, most modern operating systems do not. However, if you ever write games for consoles or handheld devices, it is likely that the device's operating system will impose such a limit. One of the most common size limits is 64K. That was the size limit for an allocated memory block in DOS, the most common operating system before Windows.

Listing 11.2. Allocating memory with new

 1     #include <cstdlib> 2     #include <iostream> 3 4     using namespace std; 5 6     int main(int argc, char *argv[]) 7     { 8         int *someInts = NULL; 9         int *temp = NULL; 10        int i; 11 12        someInts = new int[10]; 13        if (someInts != NULL) 14        { 15            i = 0; 16            temp = someInts; 17            while (i < 10) 18            { 19                *temp = i; 20                i++; 21                temp++; 22            } 23 24            i = 0; 25            temp = someInts; 26            while (i < 10) 27            { 28                cout << *temp << endl; 29                i++; 30                temp++; 31            } 32        } 33        else 34        { 35            cout << "Could not allocate memory." << endl; 36        } 37 38        system("PAUSE"); 39        return EXIT_SUCCESS; 40    } 

The short program in Listing 11.2 begins by declaring three variables. The first two are integer pointers (pointers that point to integers). The third variable is an integer that the program uses as a loop counter.

Line 12 performs a dynamic memory allocation. It allocates enough memory for 10 integers. The syntax you see on line 12 is what you should use whenever you allocate a group of data items. That is, you use the keyword new, followed by the type and then square brackets containing the number of items to allocate. When the allocation is performed, the address of the first byte of the allocated memory block is stored in the integer pointer someInts.

Suppose you want to allocate just one integer. In that case, you would use a statement similar to the following:

 int *anInt = new int; 

This statement allocates space for one integer and saves the address of that integer in the pointer anInt.

Getting back to Listing 11.2, imagine that not enough memory remains for 10 integers. In that case, the new keyword returns the value NULL. The if statement on line 13 tests whether the address in someInts is not equal to NULL. If it is not equal to NULL, the allocation was successful. Therefore, the program is free to use the memory pointed to by the pointer.

On line 15, the program sets i to 0 so it can use i as a loop counter. Line 16 shows that the program sets the integer pointer temp to point to the same block of memory as someInts. When this statement executes, the program copies the address in someInts into temp.

Next, the program enters a loop on line 17. The loop iterates while i is less than 10. Inside the loop, the program stores the value in i into the memory location pointed to by temp. Notice the difference between the statements on lines 16 and 19. Line 16 copies an address into the pointer; it changes where the pointer points. Line 19 copies an integer into the memory that temp points at. These are two very different operations.

On line 20, the program increments i. On line 21, it increments temp. The question is, what does it mean to increment a pointer?

Tip

Always check your memory allocations to ensure that they are successful. If the new keyword returns the value NULL, the allocation failed. Otherwise, it was successful.

Remember that a pointer contains the address of the location in memory it points at. Memory addresses are simply unsigned integers. If your program increments a pointer, it increments the address the pointer contains. In other words, each time you increment the pointer, it points to the next location in memory. Figure 11.2 illustrates what's going on here.

Figure 11.2. Incrementing a pointer.

Figure 11.2 displays two views of the dynamically allocated memory from Listing 11.2. On the left, it shows how things look at the beginning of the while loop that begins on line 17. The variables someInts and temp both point to the beginning of the block of integers that were allocated. Line 19 copies the value in i to the memory location that temp points at. Line 21 increments temp. When it does, temp points at the next location in memory. This is shown in the right-hand view in Figure 11.2. Each time through the loop, line 21 increments temp. This moves temp through the entire block of memory one integer at a time.

Here's a question for you: Why does the program set temp to point to the same location as someInts on line 16?

Another look at Listing 11.2 provides the answer. By the time the loop beginning on line 17 ends, temp points one integer location beyond the end of the block of memory. In other words, without someInts, the program loses the starting address of the block of memory. The program could solve this by decrementing the address in temp again. However, that's a waste of CPU time. It's much faster and more efficient to just keep a pointer to the beginning of the block.

On line 25 of Listing 11.2, you can see the usefulness of using the temp pointer instead of incrementing someInts. Because the starting address of the memory block is still in someInts, the program can set temp to point to the beginning of the block again. The program can use another loop to increment it through memory once more. This time, it prints the contents of the memory locations that temp points at one at a time.

As you can see, this pointer stuff is not particularly straightforward. You can see that a program could have real problems if it lost the starting address of a block of memory it allocated. In fact, this is one of the most common types of errors that occur in programs on the commercial markets. It's extremely easy to lose the address of a block of memory completely, making the block unusable and unrecoverable. The only way to recover a lost block of memory is to exit the program. The operating system automatically cleans up all memory allocated to the program.

Programmers have a special name for the process of losing the starting address of a dynamically allocated block of memory. The technical term for it is memory orphaning. However, the less formal and more common name of this is leaking memory.

If your program has a memory leak, it will typically continue to request memory from the operating system. However, the leaked memory won't be returned to the operating system while the program runs. Gradually, the amount of free memory that the operating system can give to the program gets smaller. Eventually, it will run out of memory completely. This is very likely to cause your program to crash. In the days of DOS, running out of memory usually also caused your entire computer to crash. With modern operating systems, it is much less likely that the program will crash the computer. Nevertheless, I have seen memory leaks crash Windows, Linux, and most other operating systems in use today.

When doing dynamic memory allocation, your biggest problem will be memory leaks. How do I know? Because it's the biggest problem all C++ programmers face when they do dynamic memory allocation. The solution to this problem is to get into the habit of cleaning up all memory you allocate.

Tip

Always make sure your program saves the starting address of dynamically allocated memory. This enables the memory block to be used repeatedly.

Freeing Memory

To keep yourself from having problems when you use dynamically allocated memory, you must remember to free all memory you allocate. You do this by using the C++ keyword delete. Look again at the program in Listing 11.2 to see where you find the keyword delete.

What's that? It's not there? You found a memory leak.

The block of memory allocated on line 12 is never freed. Therefore, it is lost. However, it's only lost temporarily. Whenever a program ends, the operating system automatically reclaims all memory given to a program.

You should never depend on the operating system's ability to reclaim leaked memory in your programs. People can play games for hours on end. Because a memory leak gradually decreases the amount of remaining memory, your game could crash after the player has been at it for hours. The result is lost progress and much frustration with your game. In fact, it can be enough to make people stop playing an otherwise good game.

The long and short of this is that you must get in the habit of freeing all memory you allocate. Yes, I know I've said that before. However, it's so important that I'm willing to risk your ire by repeating it.

Let's jump into another sample program to see how to free memory. Listing 11.3 contains a program that demonstrates how to free a single integer. It also demonstrates how to free a group of integers. The same technique demonstrated here can be used for freeing any data type.

Warning

If you ever get the opportunity to write games for a console, you'll find that the operating systems they use are much simpler and more primitive (it makes them faster). As a result, they often do not automatically reclaim all memory allocated to a program. It is extremely likely that a large memory leak will crash a console and force the player to completely reboot.

Listing 11.3. Freeing dynamically allocated memory

 1     #include <cstdlib> 2     #include <iostream> 3 4     using namespace std; 5 6     int main(int argc, char *argv[]) 7     { 8         int *intPointer = NULL; 9 10        cout << "Allocating an integer..."; 11         intPointer = new int; 12        cout << "Done." << endl; 13        if (intPointer == NULL) 14        { 15            cout << "Error: Could not allocate the integer." << endl; 16        } 17        else 18        { 19            cout << "Success: Integer was allocated" << endl; 20            cout << "Storing a 5 in the integer..."; 21            *intPointer = 5; 22            cout << "Done." << endl; 23            cout << "The integer = " << *intPointer << endl; 24 25            cout << "Freeing the allocated memory..."; 26            delete intPointer; 27            cout << "Done." << endl; 28 29            cout << "Allocating 10 integers..."; 30            intPointer = new int [10]; 31            cout << "Done." << endl; 32        } 33 34        if (intPointer == NULL) 35        { 36            cout << "Error: Could not allocate 10 integers." << endl; 37        } 38        else 39        { 40            cout << "Storing 10 integers into the allocated memory"; 41            int *temp = intPointer; 42            int i = 0; 43            while (i < 10) 44            { 45                *temp = 10-i; 46                i++; 47                temp++; 48            } 49 50            cout << "Done." << endl; 51 52           cout << "Here are the 10 integers." << endl; 53            temp = intPointer; 54            i = 0; 55            while (i < 10) 56            { 57                cout << *temp << endl;; 58                i++; 59                temp++; 60            } 61 62            cout << "Freeing the allocated memory..."; 63           delete [] intPointer; 64            cout << "Done." << endl; 65        } 66 67        system("PAUSE"); 68        return EXIT_SUCCESS; 69    } 

The program in Listing 11.3 declares an integer pointer on line 8 and initializes it to NULL. This is a way of saying that the pointer doesn't point to anything.

Next, the program allocates a single integer on line 11. On line 13, the program tests to see if the allocation was successful. If there isn't enough memory to allocate an integer, the program prints an error message on line 15. If the memory was allocated, the program executes the else statement that begins on line 17.

Warning

In some cases, the new keyword does not return the value NULL when it can't allocate memory. Instead, it can throw an exception. Exceptions are an advanced C++ programming topic that we will not discuss in this book. By default, most compilers are configured to return NULL rather than throw exceptions when allocations fail. If your program crashes and displays an error message about an unhandled memory exception, you may need to adjust the compiler's settings. See your compiler documentation for details.

On line 21, the program stores a value in the allocated memory. For emphasis, I want to draw your attention to the fact that when the program stores the address of the newly allocated memory on line 11, it does not use the asterisk operator. However, when it stores a value in the dynamically allocated memory, it must use the asterisk. On line 23, the program prints the value stored in the dynamically allocated memory.

On line 26, the program uses the delete operator to free the memory it allocated. Because this statement frees memory for just one integer, it simply contains the keyword delete followed by the variable that points to the memory to be freed.

Allocating and freeing a group of memory locations works slightly differently. The statement on line 30 allocates a group of 10 integers. If the allocation is not successful, the if statement beginning on line 34 is executed. Otherwise, the program executes the else statement that starts on line 38. Within the else statement, the program uses the statements on lines 4148 to store integer values into the allocated memory. On lines 5360, it prints the contents of the allocated memory.

The big finale is on line 63. This statement deletes the group of integers allocated on line 30. The statement on line 63 is very similar to the one on line 26. The difference between the two is that the statement on line 63 contains the square brackets between the keyword delete and the variable. Those square brackets indicate that a group of memory locations are being freed, rather than just one single location.

You may wonder what would happen if you were to leave the square brackets off the statement on line 63. The answer is that it depends on the compiler. Some compilers may be "smart enough" to understand that you're really freeing a group of integers. However, the vast majority of compilers aren't that clever. They will happily compile your program and execute the statement without its square brackets. When they do, they free just one memory location; the rest are orphaned. In other words, you create a memory leak.

The moral from this is simple: You have to make sure you free all memory that you allocate. Make this your mantra. Say it 10 times every night before you go to bed. Well, maybe not. But do make it a priority when you're doing dynamic allocation in your programs.

Where Does Dynamically Allocated Memory Really Come From?

In talking about allocating and freeing memory, I've said that when a program allocates memory, the operating system gives the memory to the program. I told you that when memory is freed, it is given back to the operating system. In saying these things, I've generalized a bit.

What specifically happens is that when your program starts, the operating system actually allocates a chunk of memory for your program's dynamically allocated memory. This chunk of memory is called the heap. Operating systems often impose a maximum size to the heap. When your program allocates the entire heap, there is no more dynamic memory to allocate.

Dealing with the heap is a rather advanced topicand not essential to our goal in this book, which is programming a game in C++. However, you do at least need to know what the heap is.