Pointers and Memory Management¶

Note

From this point onwards, we will be using C++ instead of C. One of the major differences is between the two languages is how they handle dynamic memory. C++ uses new and delete/delete[], while C uses malloc and free. We will only be using new and delete/delete[] in this course.

C++ Memory¶

managing memory turns out to be one of the trickiest and most important parts of C++ programming

a low-level way to think about memory in C++ is as one long vector of bytes:

address   0   1   2   3   4   5   6                    N-2 N-1
        +---+---+---+---+---+---+---+ ... +---+---+---+---+---+
value   |   |   |   |'a'|   |   |   |     |   |   |   |   |   |
        +---+---+---+---+---+---+---+ ... +---+---+---+---+---+

here, N is the amount of memory in your computer

every value in a C++ program has a corresponding address, e.g. the character a is at address 3

for example, consider this code:

char x = 'a';
cout << x;  // prints 'a'
cout << &x; // prints the address of 'a' (in this case 3)

& is the address-of operator, and returns the address of a variable

in general, we don’t know at what address a C++ value will be stored at, so in general our programs should not depend upon specific address values

we use pointers to store addresses

for example, the address of a char is of type char*, i.e. char* is the type “pointer to a char”

so we can write code like this:

char x = 'a';
char* px = &x;  // px stores the address of x
                // i.e. px points to x

in memory, it might look like this:

             408                   951
    +---+---+---+---+---+     +---+---+---+---+
... |   |   |'a'|   |   | ... |   |408|   |   | ...
    +---+---+---+---+---+     +---+---+---+---+
              x                    px
             *px

x has address 408, i.e. &x == 408 in this example (we don’t know the exact address)

px has address 951, i.e. &px = 951 in this example (we don’t know the exact address)

the value in px is the address of x, so we say px points to x

since px stores the address of x, that means we can access the value that location; C++ uses the notation *px to access the value at x

so in this example, address 48 has two names: x or px, and you can read/write the value there using either name, e.g.:

char x = 'a';
char* px = &x;

x = 'b';
cout << *px; // prints b

*px = 'c';
cout << x;  // prints c

The Three Memory Regions of a Running C++ Program¶

a C++ program divides its memory into three main regions:

+--------------------------------------------+
|       |                  |                 |
+--------------------------------------------+
 Static        Stack             Free store
 memory        memory            memory

Static memory has a fixed size (that is known at compile-time) that never gets bigger or smaller; global variables are stored here

Stack memory is where local variables and function parameters are stored; it automatically allocates and deallocates memory as needed

Free store (heap) memory is all the other memory, and it is not automatically managed; instead, the programmer must allocated memory on the free store using new, and deallocate memory using delete/delete[]

The Free Store¶

when we access the free store, we must do it through pointers:

double* y_addr = new double(6.4);  // returns a pointer to a newly allocated
                                   // double on the free store

new always returns a pointer

use the * to de-reference a pointer, i.e. to access the value it points to

cout << *y_addr << "\n";  // prints 6.4
*y_addr += 2;
cout << *y_addr << "\n";  // prints 8.4

Deallocating Free Store Memory¶

whenever you are finished using memory that’s on the free store, you must remember to delete it, e.g.:

delete y_addr;

if you forget to do this, your program is said to have a memory leak

for long-running programs (such as an operating system, a web server, a web browser, a text editor, etc.), memory leaks can a major problem that eventually causes them to crash

if you don’t de-allocate memory on the free store that you no longer need, a future call to new might fail because there is not enough memory left

experience shows that finding and fixing memory leaks is very difficult in general

the hard part is being 100% sure that you are

many other programming languages use an automatic memory deleter known as a garbage collector to deal with this

garbage collectors can have a performance impact that is too high for some of the applications that C++ is used for

e.g. a real-time flight control software might not be able to tolerate even a short pause as the garbage collector runs and cleans up memory

instead of a garbage collector, C++ provides destructors, and also smart pointers, to give programmers control over memory in a way that it is often as easy having a garbage collector, but with more flexibility and control

Arrays on the Free Store¶

use new and delete[] (the []-brackets are important!) to allocate and de-allocate arrays on the free store:

int* arr = new int[5]; // arr points to a newly allocated array of 5 ints
                       // on the free store; the value of the ints is unknown

the []-brackets are important: that’s how C++ knows you want to allocate an array (as opposed to a single int initialized to 5)

arr points to the first value of the array, and so we can use pointer arithmetic to access its individual elements:

*(arr + 0) = 1;
*(arr + 1) = 2;
*(arr + 2) = 3;
*(arr + 3) = 4;
*(arr + 4) = 5;

you can also use []-bracket notation: arr[i] is shorthand for *(arr + i):

arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;

here’s how you can imagine the array in memory:

     218 219 220 221 222 223 224
    +---+---+---+---+---+---+---+
... |   | 1 | 2 | 3 | 4 | 5 |   | ...
    +---+---+---+---+---+---+---+

         arr == 219

of course, we don’t know for sure the address values, so we’ve just made them up here

since arr is an int* (i.e. a pointer to an int), for an array it points to the first element of the array, i.e. it contains the address of the first element (219 in this case)

arr + 1 is 220, the second element of the array

arr + 2 is 221, the third element of the array

arr + 3 is 220, the fourth element of the array

etc.

nothing stops you from accessing elements before or after the array

e.g. arr - 1 is address 218, which is int-sized chunk of memory that appears just before the start of the array; in general, you have idea what memory value might be before the array, or even if you are allowed to access it
similarly, arr + 5 is address 215, which us the int-size chunk of memory immediately after the last element of the array; in general, you have idea what memory value might be before the array, or even if you are allowed to access it

C++ lets you add and subtract values to pointers, and this is called pointer arithmetic

pointer arithmetic is useful for accessing array values
but it has no restrictions: from a single pointer you can theoretically read/write any memory location on your computer, which is both dangerous and a security risk

as another example of using pointers, here are three different ways to print the contents of arr:

for(int i = 0; i < 5; ++i) {           // *(arr + i) style
    cout << *(arr + i) << "\n";
}

for(int i = 0; i < 5; ++i) {           // arr[i] style
    cout << arr[i] << "\n";
}

for(int* p = arr; p < arr + 5; p++) {  // direct pointer style
    cout << *p << "\n";
}

the last for-loop is interesting: it directly increments a pointer to print each element, and no i index variable is needed

C++ knows that p++ increments that address in p by the length of 1 int since it knows that p is an int* pointer

note that in all three loops we need to keep track of the size of the array ourselves since C++ arrays don’t store their size

Null Pointers¶

any pointer variable can be assigned the special value nullptr, e.g.:

string* a = nullptr;
char* b   = nullptr;
double* c = nullptr;

intuitively, a pointer with the value nullptr points nowhere, i.e. it doesn’t point to a valid memory address

you cannot de-reference a null pointer, i.e. *a is an error if a == nullptr

because of this, you always need to be certain that a pointers value is not nullptr before you de-reference it, e.g. code that looks like this is common with pointers:

if (a == nullptr) {
    cmpt::error("error: null pointer");
} else {
    cout << *a << "\n";
}

dealing with nullptr values is yet another small annoyance when dealing with pointer values, and it is up to the programmer to ensure they never accidentally de-reference nullptr

note that C++ references can never have a null value
for example, if variable x has type int& (reference to int), then x is guaranteed to contain an int

Example: Sorting a str_array¶

suppose str_array is defined like this:

struct str_array {
    string* arr;
    int sz;
    int cap;
}

str_array is meant to store a dynamic array

arr points to the first string in the array

sz is the number of strings in the array from the point of view of the programmer using it

cap is the size of the underlying array

here’s a diagram:

                                     |
       0                         sz-1| sz             cap-1
    +----+--------     ---------+----+----+--     ---+----+
arr |    |         ...          |    |    |   ...    |    |
    +----+--------     ---------+----+----+--     ---+----+
                 used entries        |   unused entries
                                     |

arr[0] to arr[sz-1] are the first sz elements of the array, and these are the elements the programmer knows about

arr[sz] to arr[cap-1] are the unused array entries; they are there to make it fast to expand the size of the array

if you don’t have any used entries, then to increase the size of the dynamic array you must make a new (bigger) array, copy all the elements from the old array into it, and then delete the original array
- keeping some extra entries means often you won’t have to do this relatively expensive array copying

important: sz < cap must always be true

important: if sz equals cap, then there are no unused entries, and so if you need to add any new strings it will be necessary to copy the elements into a new array as described above

now suppose we want to sort the elements of a str_array, i.e. we want to re-arrange the strings in the underlying array so they are in alphabetical order using this function call:

// words is a str_array that has already been created

sort(words);

after calling sort, the strings in words will be in alphabetical order

here is the function:

#include <algorithm>

using namespace std;

void sort(str_array a) {
    sort(a.arr, a.arr + a.size);  // this sort function is from <algorithm>
}

to sort a str_array named a, we have to sort all the elements in a.arr from a.arr[0] to a.arr[a.size-1]

fortunately, the C++ library has a sorting function called sort(begin, end) that lets us sort any sub-array in an array

we need to give std::sort two inputs: a pointer to the first element of the array (a.arr), and a pointer to one past the last element of the array (a.arr + a.size)

sort(a.arr, a.arr + a.size - 1) is wrong: it misses the last element of the array, i.e. the element at a.arr[a.size - 1]
by requiring a begin pointer and end pointer, std::sort can sort any part of the array

here is some sample code showing everything working together:

#include "cmpt_error.h"
#include <iostream>
#include <algorithm>

using namespace std;

struct str_array {
    string* arr;
    int sz;
    int cap;
};

void sort(str_array a) {
    sort(a.arr, a.arr + a.sz);
}

int main() {
    // create an array of 10 strings
    string* arr = new string[10];

    // the str_array is of size 3, so it has 3 strings and 7 unused entries
    str_array a{arr, 3, 10};

    // add some strings
    a.arr[0] = "mouse";
    a.arr[1] = "cheese";
    a.arr[2] = "cat";

    // print the str_array
    for(int i = 0; i < a.sz; i++) {
        cout << "\"" << a.arr[i] << "\" ";
    }
    cout << "\n";

    sort(a);

    // print the str_array
    for(int i = 0; i < a.sz; i++) {
        cout << "\"" << a.arr[i] << "\" ";
    }
    cout << "\n";

    // de-allocate the underlying array to avoid a memory leak
    delete[] a.arr;
}

Sample Code: Pointers¶

// pointers.cpp

#include "cmpt_error.h"
#include <iostream>

using namespace std;


void test1() {
    // Variable a has the type double. The value 6.02 is stored at some
    // location in the computer's memory.
    double a = 6.02;

    cout << "  a = " << a << "\n";

    // Variable pa has the type double*, i.e. pointer to a double. A double*
    // can store the address of a variable. In this case, pa stores the
    // address of variable.
    double* pa = &a;

    // The value of pa is the address of where in RAM a is stored. The
    // compiler and operating system determine the exact memory location of a,
    // and so we can't usually predict the value of pa. In fact, the value of
    // pa can change from run to run.
    cout << " pa = " << pa << "\n";

    // pa is the address of where in memory variable a is stored, and *a is
    // the value itself. This is important: having a pointer to a value means
    // you know the address of that value, and so you can access that variable
    // itself.
    cout << "*pa = " << *pa << "\n";

    // This statement modifies the value stored in a.
    *pa = 2.11;

    cout << "\n";
    cout << "  a = " << a << "\n";
    cout << "*pa = " << *pa << "\n";

    // You can have pointers to any type in C++, even pointers to pointers.
    // Here, variable ppa stores the address of pa. Thus, *ppa is the value of
    // pa, and **ppa is the value of a.
    double** ppa = &pa;

    cout << "\n";
    cout << " *ppa = " << *ppa << " (value of pa)\n";
    cout << "**ppa = " << **ppa << " (value of a)\n";
}


// C++ designates a region of your program's memory as the free store, where
// memory can be allocated and de-allocated by the program as it runs. In C++,
// we use new to allocate memory on the free store, and delete (or delete[], in
// the case of arrays) to deallocate memory on the free store.
//
// While this seems simple enough, decades of experience have shown that this
// sort of manual memory management is notoriously hard to get right. Errors
// related to the mis-use of new and delete are the source of some of the most
// difficult programming bugs. This is a major reason we're using valgrind: to
// check that our programs don't have any memory errors.
//
// Later, we will see that C++ provides a number of useful techniques for
// simplifying memory management.
void test3() {
    // The expression new int(4) allocates one int on the free store,
    // initializes that int to 4, and then returns a pointer to that int.
    int* p = new int(4);

    cout << "*p = " << *p << "\n";
    (*p)++;
    cout << "*p = " << *p << "\n";

    // When we are done with free store memory, we de-allocate it, which means
    // we tell the free store that the memory pointed to by p is no longer
    // needed and can, if necessary, be allocated later in future calls to
    // new.
    delete p;

    // If you don't delete p, then the memory that p pointed to stays
    // allocated and cannot be re-used. This is not a problem here since we
    // have allocated only a single byte. But in larger, long-running programs
    // losing memory in this way can eventually use up all of memory and crash
    // your program. This kind of error is called a **memory leak**, and it is
    // a very common error in C and C++. In C++, it is entirely up to the
    // programmer to prevent memory leaks. Explicitly calling delete is the
    // simplest way to do this, but in practice it turns out to be
    // surprisingly difficult to always call delete at the right time.
}

// Here's an example of a common problem you can run into with dynamic memory.
void test4() {
    int* p = new int(5);
    int* q = p;

    // Now p and q both point to the same int on the free store.
    cout << "*p = " << *p << "\n";
    cout << "*q = " << *q << "\n";

    // If we call delete on p, then the int p was pointing to is now deleted.
    // But the pointer q does not know that!

    delete p; // ok, but dangerous: how does q know this has happened?

    *q = 2; // oops: q is not pointing to allocated memory!
    cout << "*q = " << *q << "\n";
}

// When I run test4 on my computer, there's no compiler error or run-time
// error:
//
//    $ ./pointers
//
//    ... program runs without any apparent problem ...
//
// That's a problem: there code is definitely incorrect! This is where
// valgrind is immensely useful. Running the program using valgrind catches
// the memory errors:
//
//   $ valgrind ./pointers
//
//   ... whoa! valgrind reports 2 memory errors ...
//

// These print functions will be used in the test5.
void print(int* arr, int size) {
    cout << "[";
    for(int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
    }
    cout << "]";
}

void println(int* arr, int size) {
    print(arr, size);
    cout << "\n";
}

// Prints the elements in the range [begin, end), it prints *(begin + 0),
// *(begin + 1), *(begin + 2), ... *(end - 1).
//
// Notice that the range [begin, end) is asymmetric: *(begin + 0) is printed,
// but *(end + 0) is not printed.
void print(int* begin, int* end) {
    cout << "[";
    for(int* p = begin; p < end; ++p) {
        cout << *p << " ";
    }
    cout << "]";
}

void println(int* begin, int* end) {
    print(begin, end);
    cout << "\n";
}

// You can allocate arrays on the free store using new and delete[] (note the
// square brackets at the end of delete).
void test5() {
    // arr points to a newly allocated array of 5 ints on the free store. The
    // value of the ints is unknown.
    int* arr = new int[5];

    // We can access the individual elements of arr using pointer arithmetic
    // and the *-operator.
    *(arr + 0) = 1;
    *(arr + 1) = 2;
    *(arr + 2) = 3;
    *(arr + 3) = 4;
    *(arr + 4) = 5;

    // Equivalently, and often more conveniently, we can use the []-notation
    // to access individual elements. In general, the notation arr[i] is just
    // shorthand for *(arr + i).
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    arr[3] = 4;
    arr[4] = 5;

    // Print the elements of arr using pointer notation.
    for(int i = 0; i < 5; ++i) {
        cout << *(arr + i) << "\n";
    }

    // Print the elements of arr using []-notation.
    cout << "\n";
    for(int i = 0; i < 5; ++i) {
        cout << arr[i] << "\n";
    }

    // Print the elements of arr using a pointer (instead of an int) to point
    // to each element. In this case p is a pointer of type int* that initially
    // points to the first element of arr, and then each time through the loop
    // is incremented to point to the next element.
    cout << "\n";
    for(int* p = arr; p < arr + 5; p++) {
        cout << *p << "\n";
    }

    // Here we use a print function that takes as input and int* pointing to
    // the first element of the array, and the size of the array.
    cout << "\n";
    println(arr, 5);

    // Here we use a more general version of the print function that takes as
    // input a pointer to the first element we want to print, and a pointer to
    // one past the last element we want to print.
    cout << "\n";
    println(arr, arr + 5);

    // De-allocate arr using delete[] (not delete!) so that future calls to
    // could re-use this memory. You must use the []-bracket delete[] since
    // new was called using []-brackets.
    delete[] arr;
}

// sets all the values of arr to val
void fill(int* arr, int val, int size) {
    for(int i = 0; i < size; ++i) {
        arr[i] = val;
    }
}

// returns a pointer to a newly allocated array
int* make_int_arr(int size, int val = 0) {
    int* arr = new int[size];
    for(int i = 0; i < size; ++i) {
        arr[i] = val;
    }
    return arr;
}

void test6() {
    // arr1 points to a newly created array of 5 ints on the free store.
    int* arr1 = new int[5];

    // Set all the values of arr1 to 0.
    fill(arr1, 0, 5);

    // Print it to cout.
    println(arr1, 5);

    // make_int_arr(6, 0) returns a pointer to a newly allocated array of 6
    // ints on the free store, all initialized to 0. This is the standard
    // technique to use when you want a function to return an array, i.e.
    // return a pointer to an array on the free store.
    int* arr2 = make_int_arr(6, 0);
    print(arr2, 6);

    // Always remember to de-allocate memory!
    delete[] arr1;
    delete[] arr2;
}

struct Point {
    double x, y;
};

void test7() {
    // p points to a newly created Point object on the free store.
    Point* p = new Point{3.1, -4.2};

    // p points to the Point, and so *p is the Point itself. You can thus
    // access individual elements using the regular struct "."-notation
    cout << "x = " << (*p).x << "\n";
    cout << "y = " << (*p).y << "\n";

    // Pointers to structs (i.e. objects) are so common in C++ that
    // expressions like (*p).x are quite common, and so C++ provides a special
    // notation, i.e. the -> operator. The expression p->x is the same as
    // (*p).x.
    cout << "\n";
    cout << "x = " << p->x << "\n";
    cout << "y = " << p->y << "\n";

    // Always remember to de-allocate memory!
    delete p;
}

int main() {
    // test1();
    // test2();
    // test3();
    // test4();
    // test5();
    // test6();
    test7();
}

Table Of Contents

Previous topic

Next topic