C++ Pointers and Dynamic Memory Allocation
Tags: cpp, programming, performance, tutorial
Published: 2020-12-23 14:33:43

In C and C++, pointers allow you direct control of the way you access memory. This becomes very useful when learning to use build complex data structures or trying to save space when allocating memory.

One of the most basic ways pointers help is when you want to dynamically set the size of an array based on an external input not known beforehand to the compiler or you may want to change the size of the array in runtime. In C++, arrays must have a constant size which can't be changed, but with pointers, you can allocate just the space you need, allowing you to improve your program's space efficiency and make the shape of your data as flexible as the user needs.

----------------------------
A pointer storing an address
----------------------------

`&x` (referencing operator) = “address of”
`int* p` (pointer declaration) = “p is a pointer to an integer”
`int** p` (pointer declaration) = “p is a pointer to a pointer to an integer”

```cpp
+-----Example-------------------------------------------------------+
| int x = 6; // x is an integer with the value 6                    |
| int* a = &x; // a is a pointer that points to the address of x    |
| int** b = &a; // b is a pointer that points to the address of a   |
+-------------------------------------------------------------------+
```

### Dereferencing pointers

`*p` (dereferencing operator) = “content at the address stored in p”
`**p` = “content at the address stored in the address stored in p”

In the example above, `*a` and `x` can be used interchangeably. Modifying `*a` (ex. `(*a)++`) will also modify `x`.

--------------------------
A pointer storing an array
--------------------------

Before you assign a value to an address in memory, you need to be sure that the memory is unused.

The `new` operator will allocate a given size in memory to store consecutive values.

```cpp
+-----Example---------------------------------------------------------------------------+
| int* numbers = new int[3]; // numbers points to memory where 3 integers can be stored |
| *numbers = 5; // the first value in the memory numbers points to is now set to 5      |
| numbers[1] = 3 // using array notation, the value after the first value is now a 3    |
| *(numbers + 2) = 7 // using pointer notation, the value at index 2 is now a 7         |
| // The current array, 'numbers' is now storing the integers, {5, 3, 7}                |
+---------------------------------------------------------------------------------------+
```

In a two-dimensional array, the values the pointer points to are pointers pointing to arrays

```cpp
+-----Example-----------------------------------------------------------------------------------+
| int numOfRows = 4;                                                                            |
| int** numArr = new int*[numOfRows]; //numArr points to memory where 4 addresses can be stored |
| *numArr = new int[3]; // the first row of numArr points to memory where 3 ints can be stored |
| *(*(numArr + 1) + 2) = 3; // The value at coordinates 1,2 (numArr[1][2]) is now a 3           |
+-----------------------------------------------------------------------------------------------+
```

-------------------------
Dynamic Memory Allocation
-------------------------

The `delete[]` operator deallocates memory so that it can be used later.
To deallocate the two dimensional array, `numArr`, use:

```cpp
for (int i = 0; i < numOfRows; i++) {
	delete[] numArr[i]; // frees up the row at i of numArr
}
if (numOfRows > 0) {
	delete[] numArr; // frees up the address numArr itself
}
```

When you change the size of the data an array points to, you need to `delete[]` each row and the original address of the array.

Then, use the new operator to allocate the amount of data you will need.

If you need to keep the contents of the old array, you will need to create a temporary array to back up the values.

After you change the size with the new operator, copy the values back into the array from the temporary array.

You will need to do this for both shrinking and expanding an array.

The example program at the end includes a pointer array which changes size using dynamic memory allocation.

### Visualization

Below are two ways to visualize arrays and access their contents.

#### Array as a grid with subscript notation (left) and pointer dereferencing notation (right)

```
	+-----------+-----------+-----------+			+---------------+---------------+---------------+
	| arr[0][0] | arr[0][1] | arr[0][2] |			| *(*(arr+0)+0) | *(*(arr+0)+1) | *(*(arr+0)+2) |
	+-----------+-----------+-----------+			+---------------+---------------+---------------+
	| arr[1][0] | arr[1][1] | arr[2][2] |			| *(*(arr+1)+0) | *(*(arr+1)+1) | *(*(arr+1)+2) |
	+-----------+-----------+-----------+			+---------------+---------------+---------------+
	| arr[2][0] | arr[2][1] | arr[2][2] |			| *(*(arr+2)+0) | *(*(arr+2)+1) | *(*(arr+2)+2) |
	+-----------+-----------+-----------+			+---------------+---------------+---------------+
	| arr[3][0] | arr[3][1] | arr[3][2] |			| *(*(arr+3)+0) | *(*(arr+3)+1) | *(*(arr+3)+2) |
	+-----------+-----------+-----------+			+---------------+---------------+---------------+
```

#### Pointer map with subscript notation

```
					 +--------+      +-----------+-----------+-----------+
               +---> | arr[0] |----> | arr[0][0] | arr[0][1] | arr[0][2] |
    +-----+    |     +--------+      +----- -----+-----------+-----------+     +-----------+-----------+-----------+
    | arr |----+     | arr[1] |----------------------------------------------> | arr[1][0] | arr[1][1] | arr[1][2] |
    +-----+          +--------+      +-----------+-----------+-----------+     +-----------+-----------+-----------+
					 | arr[2] |----> | arr[2][0] | arr[2][1] | arr[2][2] |
					 +--------+      +----- -----+-----------+-----------+     +-----------+-----------+-----------+
					 | arr[3] |----------------------------------------------> | arr[3][0] | arr[3][1] | arr[3][2] |
					 +--------+                                                +-----------+-----------+-----------+
```

#### Pointer map with pointer dereferencing notation

```
                     +--------+      +---------------+---------------+---------------+
               +---> |*(arr+0)|----> | *(*(arr+0)+0) | *(*(arr+0)+1) | *(*(arr+0)+2) |
    +-----+    |     +--------+      +---------------+---------------+---------------+     +---------------+---------------+---------------+
    | arr |----+     |*(arr+1)|----------------------------------------------------------> | *(*(arr+1)+0) | *(*(arr+1)+1) | *(*(arr+1)+2) |
    +-----+          +--------+      +---------------+---------------+---------------+     +---------------+---------------+---------------+
                     |*(arr+2)|----> | *(*(arr+2)+0) | *(*(arr+2)+1) | *(*(arr+2)+2) |
                     +--------+      +---------------+---------------+---------------+     +---------------+---------------+---------------+
					 |*(arr+3)|----------------------------------------------------------> | *(*(arr+3)+0) | *(*(arr+3)+1) | *(*(arr+3)+2) |
					 +--------+                                                            +---------------+---------------+---------------+
```

-------
Example
-------

#### In this program:

- The user is asked for a number of rows and a value to start filling the cells with
- A pointer array changes size to hold the given number of rows
- The number of columns will be 12 throughout the program
- New rows are filled using the fill value provided (incrementing by 1 for each new row)
- The new array is printed

```cpp
#include <iostream>
using namespace std;

void changeSize(int** & arr, int & currentNumOfRows, int newSize, int fillValue);
int numDigits(int x);
void printArray(int** arr, int currentNumOfRows);

int main() {

    // declare a pointer that will point to an
    // array of pointers to integers (see diagrams above)
    int** arr = new int*;

    int currentNumOfRows = 0;

    int newSize, fillValue;

    while (true) {

        cout << "How many rows? ";

        cin >> newSize;

        // if newSize is less than current size, no rows added, so no need for fill value
        if (newSize > currentNumOfRows) {
            do {
                cout << "Enter the fill value: ";
                cin >> fillValue;
                if (fillValue < 0) {
                    cout << "Please enter a positive number." << endl;
                }
            } while (fillValue < 0);
        }

        // Loop will continue until a negative number is chosen
        if (newSize >= 0) {
            // change amount of memory 'arr' points to
            // (new amount of memory will be enough to store 'newSize' number of pointers)
            changeSize(arr, currentNumOfRows, newSize, fillValue);
            // print the new array
            printArray(arr, currentNumOfRows);
        }
        else {
            // exit the loop
            break;
        }

    }

    // free up remaining memory which is in current array
    for (int i = 0; i < currentNumOfRows; i++)
        delete[] arr[i];
    if (currentNumOfRows > 0)
        delete arr;

    return 0;
}

// changes amount of memory arr points to
// and fills new cells starting with fillValue
// incrementing by 1 for each row
// parameters:
// arr is a pointer to pointers to integers. 
// It is passed as a reference so that you can change
// the location it points to from within this function.
// currentNumOfRows is the number of rows the array has
// at the time the function is called. It will also
// change within the function.
// newSize is the new number of rows the array will point to.
// fillValue is the number to starting filling new rows with
void changeSize(int** & arr, int & currentNumOfRows, int newSize, int fillValue) {

    // when the new operator is used, the pointer will point
    // to a new location in memory with the required size
    // therefore, if we want to keep the data, we will need
    // to back it up in a temporary array

    /* CREATE A TEMPORARY ARRAY TO STORE ARRAY'S DATA */

    // create a pointer that points to the size of the array (before we change it)
    int** temporaryArr = new int*[currentNumOfRows];

    // for each row in original array (that we will backup and delete):
    for (int i = 0; i < currentNumOfRows; i++) {

        // in this example, each row in arr contains exactly 12 values
        // create a pointer to an array of 12 integers at temporaryArr[i]
        // which can be written as: *(temporaryArr + i) -- 
        // i.e. content of the address, 'i' values after the address of temporaryArr
        *(temporaryArr + i) = new int[12];

        // for each of the 12 values in row i:
        for (int j = 0; j < 12; j++) {
            // copy data from arr into temporary array
            *(*(temporaryArr + i) + j) = *(*(arr + i) + j);
        }

        // original array location is no longer being used,
        // so free up the memory for current row
        delete[] * (arr + i);
    }
    // free up the original address of arr
    delete[] arr;

    /* CHANGE THE SIZE OF ARRAY BY POINTING IT TO A LARGER AMOUNT OF MEMORY */
    arr = new int*[newSize];

    /* PUT THE DATA THAT WAS REMOVED BACK INTO ARRAY */

    // for each row in temporaryArr (that we will move back into arr and delete):
    // if i becomes greater than or equal to old size (if size is increasing)
    // or new size (if size is decreasing) stop loop
    for (int i = 0; (i < currentNumOfRows && i < newSize); i++) {

        // create a pointer to 12 integers at *(arr + i)
        *(arr + i) = new int[12];

        // for each of the 12 values in row i:
        for (int j = 0; j < 12; j++) {
            // copy data from temporaryArr back into arr
            *(*(arr + i) + j) = *(*(temporaryArr + i) + j);
        }

        // temporaryArr row is no longer being used, so free up the memory for current row
        delete[] * (temporaryArr + i);
    }
    // free up the original address of temporaryArr
    delete[] temporaryArr;

    /* FILL IN SOME VALUES INTO EMPTY SPOTS */

    int numOfAddedRows = newSize - currentNumOfRows; // original size - new size
    for (int i = currentNumOfRows; i < newSize; i++) { // for each new row starting at first new row
        // create a pointer to 12 integers at *(arr + i):
        *(arr + i) = new int[12];
        // now that memory is allocated, we can set the values:
        for (int j = 0; j < 12; j++) { // for each column in row
            // set *(*(arr + i) + j),
            // i.e. arr[i][j],
            // i.e. content of j values past address stored in content of i values past address of arr
            *(*(arr + i) + j) = fillValue + i - currentNumOfRows;
        }
    }

    /* CHANGE currentNumOfRows TO NEW SIZE */
    currentNumOfRows = newSize;
}

// prints out the array's values
void printArray(int** arr, int currentNumOfRows) {
    // to line up numbers in columns:
    int highestNum = -32767;
    for (int i = 0; i < currentNumOfRows; i++)
        if (*(*(arr + i) + 0) > highestNum)
            highestNum = *(*(arr + i) + 0);
    int maxNumOfSpaces = numDigits(highestNum); // get number of digits in largest number in column
    for (int i = 0; i < currentNumOfRows; i++) { // for each row in the array
        for (int j = 0; j < 12; j++) { // prints the 12 pieces of data in arr[i]
            // num of spaces needed to line up text = maxNumOfSpaces - digits in currentWord
            // print spaces that many times:
            for (int k = 0; k < maxNumOfSpaces - numDigits(*(*(arr + i) + j)); k++) {
                cout << ' ';
            }
            // print value
            cout << *(*(arr + i) + j);
            cout << ' ';
        }
        cout << endl;
    }
}

// get number of digits in an integer
int numDigits(int x) {
    return (x < 10 ? 1 :
        (x < 100 ? 2 :
        (x < 1000 ? 3 :
        (x < 10000 ? 4 :
        (x < 100000 ? 5 :
        (x < 1000000 ? 6 :
        (x < 10000000 ? 7 :
        (x < 100000000 ? 8 :
        (x < 1000000000 ? 9 :
        10)))))))));
}
```

#### Sample run of the program

```
How many rows? 5
Enter the fill value: 7
 7  7  7  7  7  7  7  7  7  7  7  7
 8  8  8  8  8  8  8  8  8  8  8  8
 9  9  9  9  9  9  9  9  9  9  9  9
10 10 10 10 10 10 10 10 10 10 10 10
11 11 11 11 11 11 11 11 11 11 11 11
How many rows? 3
7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9
How many rows? 10
Enter the fill value: 50
 7  7  7  7  7  7  7  7  7  7  7  7
 8  8  8  8  8  8  8  8  8  8  8  8
 9  9  9  9  9  9  9  9  9  9  9  9
50 50 50 50 50 50 50 50 50 50 50 50
51 51 51 51 51 51 51 51 51 51 51 51
52 52 52 52 52 52 52 52 52 52 52 52
53 53 53 53 53 53 53 53 53 53 53 53
54 54 54 54 54 54 54 54 54 54 54 54
55 55 55 55 55 55 55 55 55 55 55 55
56 56 56 56 56 56 56 56 56 56 56 56
How many rows? 15
Enter the fill value: 2
 7  7  7  7  7  7  7  7  7  7  7  7
 8  8  8  8  8  8  8  8  8  8  8  8
 9  9  9  9  9  9  9  9  9  9  9  9
50 50 50 50 50 50 50 50 50 50 50 50
51 51 51 51 51 51 51 51 51 51 51 51
52 52 52 52 52 52 52 52 52 52 52 52
53 53 53 53 53 53 53 53 53 53 53 53
54 54 54 54 54 54 54 54 54 54 54 54
55 55 55 55 55 55 55 55 55 55 55 55
56 56 56 56 56 56 56 56 56 56 56 56
 2  2  2  2  2  2  2  2  2  2  2  2
 3  3  3  3  3  3  3  3  3  3  3  3
 4  4  4  4  4  4  4  4  4  4  4  4
 5  5  5  5  5  5  5  5  5  5  5  5
 6  6  6  6  6  6  6  6  6  6  6  6
How many rows? 3
7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9
How many rows? 6
Enter the fill value: -1
Please enter a positive number.
Enter the fill value: 0
7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2
How many rows? 0
How many rows? -1
```

I hope you find this helpful, let me know if you find any questions or corrections.

\- Jonah Lawrence

Twitter: [@DenverCoder1](https://twitter.com/DenverCoder1)