This document is part of the HTML publication "An Introduction to the Imperative Part of C++"
The original version was produced by Rob Miller at Imperial College London, September 1996.
Version 1.1 (modified by David Clark at Imperial College London, September 1997)
Version 1.2 (modified by Bob White at Imperial College London, September 1998)
Version 1.3, 1.4, 2.0, ..., 2.21, 3.1, ..., 3.3 (modified by William Knottenbelt at Imperial College London, September 1999-October 2026)
In the previous lectures, we have not given many methods to control the amount of memory used in a program. In particular, in all of the programs we have looked at so far, a certain amount of memory is reserved for each declared variable at compilation time, and this memory is retained for the variable as long as the program or block in which the variable is defined is active. In this lecture we introduce the notion of a pointer, which gives the programmer a greater level of control over the way the program allocates and de-allocates memory during its execution.
A pointer is a value that represents the memory address of an object. A pointer variable is a variable in which such an address can be stored. Pointer variables are declared using a "*", and have data types like the other variables we have seen. For example, the declaration
int *number_ptr;
states that "number_ptr" is a pointer variable that can store addresses of variables of data type "int". A useful alternative way to declare pointers is using a "typedef" construct. For example, if we include the statement:
typedef int *IntPtrType;
we can then go on to declare several pointer variables in one line, without the need to prefix each with a "*":
IntPtrType number_ptr1, number_ptr2, number_ptr3;
Given a particular data type, such as "int", we can write assignment statements involving both ordinary variables and pointer variables of this data type using the dereference operator "*" and the (complementary) address-of operator "&". Roughly speaking, "*" means "the variable located at the address", and "&" means "the address of the variable". We can illustrate the uses of these operators with a simple example program:
#include <iostream>
using namespace std;
typedef int *IntPtrType;
int main()
{
IntPtrType ptr_a, ptr_b;
int num_c = 4, num_d = 7;
ptr_a = &num_c; /* LINE 10 */
ptr_b = ptr_a; /* LINE 11 */
cout << *ptr_a << " " << *ptr_b << "\n";
ptr_b = &num_d; /* LINE 15 */
cout << *ptr_a << " " << *ptr_b << "\n";
*ptr_a = *ptr_b; /* LINE 19 */
cout << *ptr_a << " " << *ptr_b << "\n";
cout << num_c << " " << *&*&*&num_c << "\n";
return 0;
}
The output of this program is:
4 4 4 7 7 7 7 7
Diagrammatically, the state of the program after the assignments at lines 10 and 11 is:
after the assignment at line 15 this changes to:
and after the assignment at line 19 it becomes:
Note that "*" and "&" are in a certain sense complementary operations; "*&*&*&num_c" is simply "num_c".
In Program 7.1.1, the assignment statement
ptr_a = &num_c;
(in line 10) effectively gives an alternative name to the variable "num_c", which can now also be referred to as "*ptr_a". As we shall see, it is often convenient (in terms of memory management) to use dynamic variables in programs. These variables have no independent identifiers, and so can only be referred to by dereferenced pointer variables such as "*ptr_a" and "*ptr_b".
Dynamic variables are "created" using the reserved word "new", and "destroyed" (thus freeing-up memory for other uses) using the reserved word "delete". Below is a program analogous to Program 7.1.1, which illustrates the use of these operations:
#include <iostream>
using namespace std;
typedef int *IntPtrType;
int main()
{
IntPtrType ptr_a, ptr_b; /* LINE 7 */
ptr_a = new int; /* LINE 9 */
*ptr_a = 4;
ptr_b = ptr_a; /* LINE 11 */
cout << *ptr_a << " " << *ptr_b << "\n";
ptr_b = new int; /* LINE 15 */
*ptr_b = 7; /* LINE 16 */
cout << *ptr_a << " " << *ptr_b << "\n";
delete ptr_a;
ptr_a = ptr_b; /* LINE 21 */
cout << *ptr_a << " " << *ptr_b << "\n";
delete ptr_a; /* LINE 25 */
return 0;
}
The output of this program is:
4 4 4 7 7 7
The state of the program after the declarations in line 7 is:
after the assignments in lines 9, 10 and 11 this changes to:
after the assignments at lines 15 and 16 the state is:
and after the assignment at line 21 it becomes:
Finally, after the "delete" statement in lines 25, the program state returns to:
In the first and last diagrams above, the pointers "ptr_a" and "ptr_b" are said to be dangling. A particularly important point is that "delete ptr_a" destroys the dynamic object to which "ptr_a" points, but it does not change the value stored in "ptr_a". If another pointer is an alias for the same object, that pointer becomes dangling too. Thus "ptr_b" is dangling at the end of Program 7.1.2 even though it has not itself appeared in a "delete" statement.
Dereferencing a dangling pointer, for example by evaluating "*ptr", results in undefined behaviour and may have unpredictable (and sometimes disastrous) consequences. C++ provides the special pointer value "nullptr" to represent a pointer that deliberately points to no object. It is good practice to set a pointer to "nullptr" when we no longer want it to refer to a deleted object:
delete ptr_a;
ptr_a = nullptr;
...
...
if (ptr_a != nullptr)
{
*ptr_a = ...
...
...
Fragment of Program 7.1.3
Setting "ptr_a" to "nullptr" does not change any other pointer that may have been pointing to the same object. Such aliases must be handled separately. This is one reason why keeping track of ownership of dynamically allocated objects is important.
In the case that there is not sufficient memory to create a dynamic variable of the appropriate data type after a call to "new", the normal form of "new" throws an exception called "std::bad_alloc". Alternatively, a call to "new (nothrow)" returns "nullptr" if the allocation fails. These are two alternative ways of dealing with allocation failure:
#include <iostream>
#include <cstdlib> /* ("exit()" is defined in <cstdlib>) */
#include <new> /* ("bad_alloc" and "nothrow" are defined in <new>) */
...
using namespace std;
...
try
{
ptr_a = new int;
}
catch (const bad_alloc&)
{
cout << "Sorry, ran out of memory";
exit(1);
}
...
ptr_b = new (nothrow) int;
if (ptr_b == nullptr)
{
cout << "Sorry, ran out of memory";
exit(1);
}
...
...
Fragment of Program 7.1.4
Pointers can be used in the standard way as function parameters, so it would be even better to package up this code in a function:
void assign_new_int(IntPtrType &ptr)
{
ptr = new (nothrow) int;
if (ptr == nullptr)
{
cout << "Sorry, ran out of memory";
exit(1);
}
}
Fragment of Program 7.1.5
In modern C++, application programs usually avoid managing ownership with raw "new" and "delete" wherever a standard-library container or a smart pointer can manage the lifetime of an object instead. We use raw pointers and explicit allocation here because they expose the underlying mechanisms of dynamic memory allocation and object lifetime.
In the last lecture we saw how to declare groups of variables called arrays. By adding the statement
int hours[6];
we could then use the identifiers
hours[0] hours[1] hours[2] hours[3] hours[4] hours[5]
as though each referred to a separate variable. An array and a pointer are not the same thing. However, in most expressions the name of an array is automatically converted to a pointer to its first element. Thus if we add the integer pointer declaration
int *ptr;
to the same program, it is perfectly legal to follow this by the assignment
ptr = hours;
Here the expression "hours" is converted to a pointer to "hours[0]", and this address is stored in "ptr". Thus "hours[0]", "*hours", and "*ptr" all refer to the same integer object. Similarly, the remaining array elements can be referred to as
*(hours + 1) *(hours + 2) ...
or, after the assignment above, as
*(ptr + 1) *(ptr + 2) ...
The distinction between an array and a pointer is important. For example, "ptr++" is a valid operation that changes the address stored in "ptr", whereas "hours++" is not valid because "hours" is an array, not a modifiable pointer variable.
In this case, the "+ 2" is shorthand for "plus enough memory to store 2 integer values". We refer to the addition and subtraction of numerical values to and from pointer variables in this manner as pointer arithmetic. Multiplication and division cannot be used in pointer arithmetic, but the increment and decrement operators "++" and "--" can be used, and one pointer can be subtracted from another of the same type. Pointer arithmetic should only be used within a single array (or to form the special pointer just past the end of that array); moving outside those bounds leads to undefined behaviour.
Pointer arithmetic gives an alternative and sometimes more succinct method of manipulating arrays. The following is a function to convert a string to upper case letters:
void ChangeToUpperCase(char phrase[])
{
int index = 0;
while (phrase[index] != '\0')
{
if (LowerCase(phrase[index]))
ChangeToUpperCase(phrase[index]);
index++;
}
}
bool LowerCase(char character)
{
return (character >= 'a' && character <= 'z');
}
void ChangeToUpperCase(char &character)
{
character += 'A' - 'a';
}
Fragment of Program 7.2.1
Note the use of polymorphism with the function "ChangeToUpperCase(...)" - the compiler can distinguish the two versions because one takes an argument of type "char", whereas the other takes an array-style parameter. In a function parameter declaration, C++ adjusts "char phrase[]" to "char *phrase". Therefore this version can equivalently be written using pointer arithmetic:
void ChangeToUpperCase(char *phrase)
{
while (*phrase != '\0')
{
if (LowerCase(*phrase))
ChangeToUpperCase(*phrase);
phrase++;
}
}
Fragment of Program 7.2.2
This re-writing is transparent as far as the rest of the program is concerned - either version can be called in the normal manner using a string argument:
char a_string[] = "Hello World"; ... ... ChangeToUpperCase(a_string);
The mechanisms described above to create and destroy dynamic variables of type "int", "char", "float", etc. can also be applied to create and destroy dynamic arrays. This can be especially useful since arrays sometimes require large amounts of memory. A dynamic array of 10 integers can be declared as follows:
int *number_ptr; number_ptr = new int[10];
The variable "number_ptr" is a pointer to the first element of the newly allocated array. We can therefore refer to the 10 integer objects in the array either as
number_ptr[0] number_ptr[1] ... number_ptr[9]
or as
*number_ptr *(number_ptr + 1) ... *(number_ptr + 9)
To destroy the dynamic array, we write
delete [] number_ptr;
The "[]" brackets are important. They signal the program to destroy all 10 allocated variables, not just the first. To illustrate the use of dynamic arrays, here is a program fragment that prompts the user for a list of integers, and then prints the average on the screen:
...
...
int no_of_integers, *number_ptr;
cout << "Enter number of integers in the list: ";
cin >> no_of_integers;
number_ptr = new (nothrow) int[no_of_integers];
if (number_ptr == nullptr)
{
cout << "Sorry, ran out of memory.\n";
exit(1);
}
cout << "type in " << no_of_integers;
cout << " integers separated by spaces:\n";
for (int count = 0 ; count < no_of_integers ; count++)
cin >> number_ptr[count];
cout << "Average: " << average(number_ptr,no_of_integers);
delete [] number_ptr;
number_ptr = nullptr;
...
...
Fragment of Program 7.3.1
Dynamic arrays can be passed as function parameters just like ordinary arrays, so we can simply use the definition of the function "average()" from the previous lecture (Section 6.2) with this program.
Although dynamic variables can sometimes be a useful device, the need to use them can often be minimised by designing a well structured program, and by the use of functional abstraction. Most of the variables we have been using in the previous lectures have been automatic variables. That is to say, they are automatically created in the block or function in which they are declared, and automatically destroyed at the end of the block, or when the call to the function terminates. So, for a well structured program, much of the time we don't even have to think about adding code to create and destroy variables.
Modern C++ extends this idea by providing standard-library containers and ownership-managing types which arrange for dynamically allocated resources to be released automatically. For example, classes such as "vector" and "string" manage their own storage, while smart pointers such as "unique_ptr" can manage the lifetime of dynamically allocated objects. The explicit "new" and "delete" used in this lecture remain useful for understanding what these safer abstractions do on our behalf.
(N.B. It is also possible to declare variables as being static , i.e. remaining in existence throughout the subsequent execution of the program, but in a well designed, non-object based program it should not be necessary to use any static variables other than the constants declared at the beginning.)
In this section a brief description is given of an abstract data type (ADT) called a linked list, which is of interest here because it is implemented using pointers. You will learn much more about abstract data types in general later in the course.
In the implementation given below, a linked list consists of a series of nodes, each containing some data. Each node also contains a pointer pointing to the next node in the list. There is an additional separate pointer which points to the first node, and the pointer in the last node simply contains "nullptr". The advantage of linked lists over (for example) arrays is that individual nodes can be added or deleted dynamically, at the beginning, at the end, or in the middle of the list.
In our example, we will describe how to implement a linked list in which the data at each node is a single word (i.e. string of characters). The first task is to define a node. To do this, we can associate a string with a pointer using a structure definition:
struct Node
{
char word[MAX_WORD_LENGTH];
Node *ptr_to_next_node;
};
or alternatively
struct Node;
typedef Node *Node_ptr;
struct Node
{
char word[MAX_WORD_LENGTH];
Node_ptr ptr_to_next_node;
};
(Note the semicolon after the "}".) The word "struct" is a reserved word in C++ (analogous to the notion of a record in Pascal). In the first line of the alternative (second) definition of a node above, "Node" is given an empty definition. This is a bit like a function declaration - it signals an intention to define "Node" in detail later, and in the mean time allows the identifier "Node" to be used in the second "typedef" statement.
Having defined the structure "Node", we can declare variables of this new type in the usual way:
Node my_node, my_next_node;
The values of the (two) individual components of "my_node" can be accessed and assigned using the dot "." operator:
cin >> my_node.word; my_node.ptr_to_next_node = &my_next_node;
In the case that pointers to nodes have been declared and assigned to nodes as follows:
Node_ptr my_node_ptr, another_node_ptr; my_node_ptr = new Node; another_node_ptr = new Node;
we can either use dot notation for these types of statement:
cin >> (*my_node_ptr).word; (*my_node_ptr).ptr_to_next_node = another_node_ptr;
or write equivalent statements using the "->" operator:
cin >> my_node_ptr->word; my_node_ptr->ptr_to_next_node = another_node_ptr;
In other words, "my_node_ptr->word" simply means "(*my_node_ptr).word".
Below is a function which allows a linked list to be typed in at the keyboard one string at a time, and which sets the node pointer "a_list" to point to the head (i.e. first node) of the new list. Typing a full-stop signals that the previous string was the end of the list.
void assign_list(Node_ptr &a_list)
{
Node_ptr current_node, last_node;
assign_new_node(a_list);
cout << "Enter first word (or '.' to end list): ";
cin >> a_list->word;
if (!strcmp(".",a_list->word))
{
delete a_list;
a_list = nullptr;
}
current_node = a_list; /* LINE 13 */
while (current_node != nullptr)
{
assign_new_node(last_node);
cout << "Enter next word (or '.' to end list): ";
cin >> last_node->word;
if (!strcmp(".",last_node->word))
{
delete last_node;
last_node = nullptr;
}
current_node->ptr_to_next_node = last_node;
current_node = last_node;
}
}
Fragment of Program 7.5.1
For clarity, this example concentrates on creating and traversing the list. In a longer-running program, every node created with "new" should eventually be destroyed with "delete" (or its ownership should be managed by a suitable modern C++ abstraction).
We will assume that the function "assign_new_node(...)" used in the above definition is exactly analogous to the function "assign_new_int(...)" in Program 7.1.5.
Here's how the function "assign_list(...)" works in words and diagrams. After the line
assign_new_node(a_list);
The state of the program is:
Assuming the user now types in "my" at the keyboard, after line 13 the program state is:
After the first line inside the "while" loop, the program state is:
Assuming the user now types in "list" at the keyboard, after the "while" loop has finished executing for the first time the situation is:
After the first line in the second time around the "while" loop, we have:
Assuming the user now types in "." at the keyboard, after the "while" loop has finished executing for the second time the situation is:
Since the condition for entering the "while" loop no longer holds, the function exits, and the temporary pointer variables "current_node" and "last_node" (which were declared inside the function body) are automatically destroyed. The list nodes themselves remain, and we are left with:
Printing our linked lists is straightforward. The following function displays the strings in the list one after another, separated by blank spaces:
void print_list(Node_ptr a_list)
{
while (a_list != nullptr)
{
cout << a_list->word << " ";
a_list = a_list->ptr_to_next_node;
}
}
Second fragment of Program 7.5.1
In this lecture we have seen how pointers can be used to refer to objects by address, and how computer memory can be dynamically allocated and de-allocated during the execution of a program. We have discussed dangling pointers and the use of "nullptr", and emphasised that arrays and pointers are different even though array names are converted to pointers in many expressions. We have used pointer arithmetic to manipulate arrays and have seen how arrays may be created and destroyed dynamically. Finally, we have briefly introduced the notion of a linked list, as an example of an abstract data type which may be implemented using pointers. The material here is also covered in more detail in Savitch, Chapter 9 and Chapter 13.