Pointers

Addresses of variables and pointers

In a program, all our data has an address where it is stored. During each actual execution of a program, the physical memory locations of variables are not necessarily the same. However, when programming, we can still obtain the address of data in memory through certain statements.

An address is also data. The type of variable used to store an address has a special name: a "pointer variable", sometimes simply called a "pointer".

An address is merely ordinary scalar data. To target different types of data, "pointer variables" also have different types. For example, there can be a pointer variable of type int, whose stored address (that is, the value stored in the pointer variable) corresponds to the starting address of a 32-bit space; there can also be a pointer variable of type char, whose stored address corresponds to the starting address of an 8-bit space.

In fact, a user can also declare a pointer variable that points to a pointer variable.

Suppose the user defines a structure:

struct ThreeInt {
  int a;
  int b;
  int c;
};

Then a pointer variable of type ThreeInt corresponds to a space of 3 × 32 = 96 bit.

Declaration and use of pointers

In C/C++, the type of a pointer variable is formed by appending an asterisk * to the type name. For example, the type name of a pointer variable of type int is int*.

We can use the & symbol to obtain the address of a variable.

To access the space corresponding to the address stored in a pointer variable (also called the space the pointer points to), we need to dereference the pointer variable, using the * symbol.

int main() {
  int a = 123;  // a: 123
  int* pa = &a;
  *pa = 321;  // a: 321
}

The same applies to structure variables. To access a member of the structure pointed to by a pointer, you first need to dereference the pointer and then use the . member-access operator. However, it is recommended to use the more convenient "arrow" operator ->.

struct ThreeInt {
  int a;
  int b;
  int c;
};

int main() {
  ThreeInt x{1, 2, 3}, y{6, 7, 8};
  ThreeInt* px = &x;
  (*px) = y;    // x: {6,7,8}
  (*px).a = 4;  // x: {4,7,8}
  px->b = 5;    // x: {4,5,8}
}

Pointer offsets

Pointer variables can also be added to or subtracted from integers. For a pointer of type int, adding 1 (incrementing by 1) offsets the address it points to by 32 bits (that is, 4 bytes); adding 2 offsets the address by 2 × 32 = 64 bits. Similarly, for a pointer of type char, each increment offsets the address it points to by 8 bits (that is, 1 byte).

Accessing arrays using pointer offsets

As mentioned earlier, an array is a contiguous block of storage. In C/C++, using the array name directly gives the starting address of the array.

int main() {
  int a[3] = {1, 2, 3};
  int* p = a;  // p points to a[0]
  *p = 4;      // a: [4, 2, 3]
  p = p + 1;   // p points to a[1]
  *p = 5;      // a: [4, 5, 3]
  p++;         // p points to a[2]
  *p = 6;      // a: [4, 5, 6]
}

When accessing elements of an array through a pointer, we often need to use a "pointer offset"; in other words, access them by adding an offset to a base address (the starting address of the array).

We commonly use the [] operator to access the element at a specified offset in an array, such as a[3] or p[4]. This is equivalent to performing pointer arithmetic and then dereferencing: p[4] and *(p + 4) are two equivalent forms.

Null pointers

Before C++11, C++, like C, used the NULL macro to represent a null pointer constant. In C++, NULL was generally implemented as follows:

// Before C++11
#define NULL 0

Mixing null pointers and the integer 0 causes many problems in C++, for example:

int f(int x);
int f(int* p);

When calling f(NULL), the function actually called has type int(int), not int(int *).

To solve these problems, C++11 introduced the nullptr keyword as a null pointer constant.

C++ specifies that nullptr can be implicitly converted to any pointer type; the result of this conversion is the null pointer value of that type.

The type of nullptr is std::nullptr_t, called the null pointer type. A possible implementation is as follows:

namespace std {
typedef decltype(nullptr) nullptr_t;
}

In addition, since C++11, the implementation of the NULL macro has also been changed to:

// Since C++11
#define NULL nullptr

Advanced uses of pointers

Using pointers allows programmers to operate on data in various places during program execution without being limited by scope.

Using pointer-type parameters

In C/C++, parameters used when calling a function (or procedure) are passed to the called procedure by copying (except references, which will be introduced later). By default, a function can return a result to the caller only through its return value. However, if a function wants to modify data outside itself, or the data of a structure/class is relatively large and should not be copied, the function can receive the address of external data and thereby access or even modify that data.

The my_swap function below receives two pointers of type int and uses a temporary variable to swap the values of two variables of type int.

void my_swap(int *a, int *b) {
  int t;
  t = *a;
  *a = *b;
  *b = t;
}

int main() {
  int a = 6, b = 10;
  my_swap(&a, &b);
  // After the call, the value of a in the main function becomes 10, and the value of b becomes 6
}

C++ introduced the concept of references, which are easier to use and safer than pointers. For details, see C++: References and Differences between C and C++: Pointers and references.

Dynamic instantiation

In addition, programming often involves dynamic memory allocation: at runtime, a program dynamically requests from or returns to the operating system the memory needed to store data. When a program requests memory by calling an operating-system interface, the operating system returns the address of the space requested by the program. To use this space, we need to store its address in a pointer variable.

In C++, we use the new operator to obtain a block of memory and the delete operator to release the space pointed to by a pointer.

int* p = new int(1234);
/* ... */
delete p;

The statement above uses the new operator to request a space the size of an int from the operating system, initializes its value to 1234, and declares an int pointer p pointing to this space.

Likewise, new can be used to allocate a new object:

class A {
  int a;

 public:
  A(int a_) : a(a_) {}
};

int main() {
  A* p = new A(1234);
  /* ... */
  delete p;
}

As above, a "new expression" attempts to allocate a space of the corresponding size, attempts to construct the object in that space, and returns the address of that space.

struct ThreeInt {
  int a;
  int b;
  int c;
};

int main() {
  ThreeInt* p = new ThreeInt{1, 2, 3};
  /* ... */
  delete p;
}

Note that when memory requested with new is no longer in use, delete must be used to release it. A block of memory cannot be released twice or more. Using the null pointer nullptr with the delete operation is legal.

Dynamically creating arrays

The new[] operator can also be used to create an array. In this case, new[] returns the starting address of the array, that is, the address of its first element, which can be stored in a pointer of the corresponding type. To release it, use the delete[] operator.

size_t element_cnt = 5;
int *p = new int[element_cnt];
delete[] p;

The elements of an array are stored contiguously; that is, p + 1 points to the successor of p.

Two-dimensional arrays

When storing data in matrix form, a data type such as a "two-dimensional array" may be used. Semantically, a two-dimensional array is an array of arrays. Computer memory can be viewed as a very long one-dimensional array. When storing a two-dimensional array in computer memory, the question of whether it is "contiguous" arises.

"Contiguous" means that the end of any row of the two-dimensional array is adjacent in physical address to the beginning of the next row; in other words, the entire two-dimensional array can be viewed as a one-dimensional array. Otherwise, the two are not necessarily physically adjacent.

For a "contiguous" two-dimensional array, all data in the array can be traversed using only one loop and a continuously incremented pointer. For a non-contiguous two-dimensional array, because the rows are not contiguous, you first need to obtain the address of the beginning of a row and then access the elements in that row.

Dynamically creating two-dimensional arrays

In C/C++, a two-dimensional array with N rows and M columns can be declared using a statement such as the following; its space is physically contiguous.

int a[N][M];

This declaration requires N and M to be constant expressions that can be determined at compile time.

In C/C++, the index of the first element of an array is 0. Therefore, an expression such as a[r][c] represents the (r + 1)-th row and (c + 1)-th element of row r + 1 in the two-dimensional array a; we also call the index of this element (r,c).

In practice, however, the size of a (two-dimensional) array may not be fixed, so dynamic memory allocation is needed.

A common approach is to declare a one-dimensional array of length N × M and use the index r * M + c to access the element with index (r, c) in the two-dimensional array.

int* a = new int[N * M];

This method guarantees that the two-dimensional array is contiguous.

Alternatively, memory can be obtained and used according to the concept of an "array of arrays". An array containing several arrays is actually an array containing the starting addresses of several arrays, that is, an array containing several pointer variables.

We need a variable to store the starting address of this "array of arrays"—that is, the address of a pointer. This variable is a "pointer to a pointer", sometimes also called a "double pointer", for example:

int** a = new int*[5];

Next, we need to allocate space for each array:

for (int i = 0; i < 5; i++) {
  a[i] = new int[5];
}

At this point, the memory has been obtained. To release memory obtained in this way, perform the reverse operation: first release each array, then release the array storing the starting addresses of these arrays, as follows:

for (int i = 0; i < 5; i++) {
  delete[] a[i];
}
delete[] a;

Note that a two-dimensional array obtained this way is not guaranteed to be contiguous.

There is another method, which uses a "pointer to an array".

int main() { int a[5] = {1, 2, 3, 4, 5}; }

int main() {
  int(*a)[5] = new int[5][5];
  int* p = a[2];
  a[2][1] = 1;
  delete[] a;
}

The memory obtained in this way is also contiguous, but a[n] can directly obtain the starting address of the (n + 1)-th row of the array. Therefore, using a[r][c] accesses the element with index (r, c).

Since a pointer to an array is also a definite data type, except for the first dimension of the array, the lengths of all other dimensions must be constant values determinable by the compiler. Otherwise, the compiler cannot translate an expression such as a[n] (a is a pointer to an array).

Pointers to functions

For an introduction to functions, see the C++ Functions chapter.

Simply put, to call a function, you need to know its parameter types, number of parameters, and return type; these are collectively called the interface type.

A function can be called through a function pointer. Sometimes several functions have the same interface type. Function pointers can be used to dynamically choose which function to call according to the program's execution. In other words, without modifying a function, its behavior can be changed simply by modifying the parameter passed to it (the function pointer).

Suppose we have several binary operation functions for the int type. Each function has two int parameters and also returns an int. Here is an example using a function pointer:

#include <iostream>

int (*binary_int_op)(int, int);

int foo1(int a, int b) { return a * b + b; }

int foo2(int a, int b) { return (a + b) * b; }

int main() {
  int choice;
  std::cin >> choice;
  if (choice == 1) {
    binary_int_op = foo1;
  } else {
    binary_int_op = foo2;
  }

  int m, n;
  std::cin >> m >> n;
  std::cout << binary_int_op(m, n);
}

The typedef keyword can be used to declare a function pointer type.

typedef int (*p_bi_int_op)(int, int);

We can then use p_bi_int_op as a type, namely, a pointer to a function whose parameters are two ints and whose return value is also an int.

std::function can be used to refer to a function more conveniently. (To be continued)

Function pointers can be used to implement "callback functions". (To be continued)

References and notes