Pointers · about 55 min

Pointer arithmetic and arrays

Why this matters

In the arrays module you saw that an array passed to a function becomes "the address of its first element", and that gcc described a[i] as *(a + i * 4). This lesson makes that precise. In C, arrays and pointers are tied together by one rule: indexing is pointer arithmetic. Once you see it, a lot of C code that looked cryptic (while (*p) p++;, end - begin, *dst++ = *src++) becomes readable, and you understand exactly what the machine does when you write a[i].

Adding an integer to a pointer

If p points to an element of an array, p + 1 points to the next element, not the next byte. The compiler multiplies by the element size for you:

  p + n  holds the address  (address in p) + n * sizeof(*p)
#include <stdio.h>

int main(void)
{
    int a[4] = {10, 20, 30, 40};
    int *p = a;                 /* same as &a[0] */

    for (int i = 0; i < 4; i++) {
        printf("p + %d = %p   *(p + %d) = %d\n", i, (void *)(p + i), i, *(p + i));
    }
    printf("(p + 3) - p = %td elements\n", (p + 3) - p);
    return 0;
}

One run printed:

p + 0 = 0x7fff16341ac0   *(p + 0) = 10
p + 1 = 0x7fff16341ac4   *(p + 1) = 20
p + 2 = 0x7fff16341ac8   *(p + 2) = 30
p + 3 = 0x7fff16341acc   *(p + 3) = 40
(p + 3) - p = 3 elements

The addresses differ on each run, but they always go up by 4, the size of an int.

          p        p+1      p+2      p+3      p+4 (one past the end)
          |        |        |        |        |
          v        v        v        v        v
       +--------+--------+--------+--------+
  a    |   10   |   20   |   30   |   40   |
       +--------+--------+--------+--------+
       ac0      ac4      ac8      acc      ad0

Pointer arithmetic is only defined within one array (plus the position just past its end). Moving a pointer before the start or more than one past the end is undefined behavior even if you never dereference it.

a[i] is *(a + i)

The C standard defines the subscript operator this way: E1[E2] means *((E1) + (E2)). Two facts make that work with arrays:

  1. Array decay. In almost every expression, an array's name is converted to a pointer to its first element. int *p = a; is the same as int *p = &a[0];.
  2. Scaling. a + i then points at element i, and * reads it.

So these are all the same element:

a[2]      *(a + 2)      p[2]      *(p + 2)      /* with p == a */

Indexing works on any pointer, relative to where it points:

#include <stdio.h>

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

    for (const int *p = a; p < a + 5; p++) {
        sum += *p;
    }
    printf("sum = %d\n", sum);

    int *q = &a[2];
    printf("q[0] = %d, q[1] = %d, q[-1] = %d\n", q[0], q[1], q[-1]);
    printf("index of q = %td\n", q - a);
    return 0;
}
sum = 14
q[0] = 4, q[1] = 1, q[-1] = 1
index of q = 2

q[-1] is fine here because q - 1 is still inside the array (it is a[1]).

The first loop is the classic pointer loop: start at the beginning, stop at one past the end, p++ moves to the next element. It does the same as an index loop. At -O0 it may save an instruction; with optimization on, compilers produce the same code for both. Use whichever reads better.

Subtracting pointers

Subtracting two pointers into the same array gives the number of elements between them (not bytes). The result has type ptrdiff_t (a signed integer type from <stddef.h>), printed with %td. That is how you turn a pointer back into an index: p - a.

Comparisons (<, <=, ==, !=) between pointers into the same array compare positions, which is what makes p < a + 5 a loop condition. Comparing pointers into different objects with < is undefined; == and != are always allowed (and comparing with NULL is how you check for "no object").

You cannot add two pointers (p + q is an error: invalid operands to binary +), and there is no multiplying them. Only pointer plus integer, pointer minus integer, and pointer minus pointer.

Ranges: begin and end

A pair of pointers, begin and end, where end points one past the last element, describes a range: the elements from *begin up to but not including *end. The length is end - begin, and an empty range has begin == end. That is why C explicitly allows forming (but not dereferencing) the one-past-the-end pointer: loops like for (p = begin; p != end; p++) need it. You will see this "half-open range" style throughout C and C++ code.

Where arrays and pointers differ

Array decay is so pervasive that people say "arrays are pointers". They are not. An array is a block of elements; a pointer is a variable holding one address. Decay does not happen in three places:

#include <stdio.h>

void show(int *a)
{
    printf("in show: sizeof a = %zu\n", sizeof a);
}

int main(void)
{
    int a[5] = {0};
    int *p = a;
    printf("sizeof a = %zu, sizeof p = %zu\n", sizeof a, sizeof p);
    printf("a = %p, &a[0] = %p, &a = %p\n", (void *)a, (void *)&a[0], (void *)&a);
    printf("a + 1 = %p, &a + 1 = %p\n", (void *)(a + 1), (void *)(&a + 1));
    show(a);
    return 0;
}
sizeof a = 20, sizeof p = 8
a = 0x7fff21252080, &a[0] = 0x7fff21252080, &a = 0x7fff21252080
a + 1 = 0x7fff21252084, &a + 1 = 0x7fff21252094
in show: sizeof a = 8
  1. sizeof a is the whole array (20 bytes); sizeof p is one pointer (8).
  2. &a is the address of the whole array. Numerically it equals &a[0], but its type is "pointer to array of 5 ints", so &a + 1 jumps 20 bytes (0x...80 to 0x...94), past the entire array.
  3. A string literal initializing a char array (char s[] = "hi";) copies the characters instead of decaying.

Also, an array name is not a variable you can change: a++ or a = p fail with lvalue required as increment operand and assignment to expression with array type. A pointer variable can be moved freely.

Inside show, the parameter a is a pointer, so sizeof gives 8. That is the full story behind the warning you met in the arrays module.

Common mistakes

Recap

Going further: write a loop that prints a double array using a double * and check, by printing addresses with %p, that each step moves 8 bytes. Then try a char * over the same memory (cast with (char *)) and watch it move one byte at a time.

Exercises

Exercise 1 · quiz

Predict the output

What does this print?

int a[5] = {10, 20, 30, 40, 50};
int *p = a + 1;
printf("%d %d %d\n", *(p + 2), p[1], *p + 1);
Answer

  • 40 30 21

p points at a[1] (20). p + 2 points at a[3], so *(p + 2) is 40. p[1] means *(p + 1), which is a[2], 30. In *p + 1 the dereference happens first (unary * binds tighter than +), so it is 20 + 1 = 21, not *(p + 1). Indexing works relative to wherever the pointer points.

Exercise 2 · quiz

How far does + 3 move?

d is a double * holding the address 1000. On the sandbox, where double is 8 bytes, what address does d + 3 hold?

Answer

  • 1024

Pointer arithmetic counts in elements, not bytes: d + 3 means "three doubles further", which is 3 * 8 = 24 bytes, so 1024. This is what makes *(d + i) land exactly on element i of a double array. The same + 3 on a char pointer would move 3 bytes, and on an int pointer 12.

Exercise 3 · quiz

Same thing, different spelling

a is an int array and i an int index within it. Which expressions mean exactly the same as a[i]? Select all that apply.

Answer

  • *(a + i)

  • i[a]

  • *(&a[0] + i)

The C standard defines a[i] as *((a) + (i)). Since addition commutes, i[a] is *(i + a), the same thing (legal, but never write it). &a[0] is what a decays to anyway. *a + i is a[0] + i: the first element plus i, a different value.

Exercise 4 · write code

Sum a range given by two pointers

Write

int sum_range(const int *begin, const int *end)

that returns the sum of the elements from begin up to, but not including, end. Both point into the same array; end may equal begin (an empty range, sum 0). Use a pointer that walks from begin to end; do not use an index.

For example, with int a[] = {1, 2, 3, 4, 5};, sum_range(a, a + 5) is 15 and sum_range(a + 1, a + 3) is 5 (2 + 3).

File: main.c

Starting point

#include <stdio.h>

int sum_range(const int *begin, const int *end)
{
    /* walk a pointer from begin to end */
    return 0;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    printf("%d %d\n", sum_range(a, a + 5), sum_range(a + 1, a + 3));
    return 0;
}

Example

expected output

15 5
Hint 1

for (const int *p = begin; p != end; p++) visits every element of the range.

Hint 2

Add *p (the element), not p (the address).

Reference solution
#include <stdio.h>

int sum_range(const int *begin, const int *end)
{
    int sum = 0;
    for (const int *p = begin; p != end; p++) {
        sum += *p;
    }
    return sum;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5};
    printf("%d %d\n", sum_range(a, a + 5), sum_range(a + 1, a + 3));
    return 0;
}

Exercise 5 · write code

Find and report the position

Write

const int *find(const int *a, int n, int target)

that returns a pointer to the first element of a[0]..a[n-1] equal to target, or NULL if there is none.

Then complete main: it reads a target and then up to 100 numbers (already written for you), calls find, and prints either

found <target> at index <i>

or

<target> not found

Compute the index from the returned pointer with pointer subtraction (p - values), printed with %td. For input 7 3 7 1 7 (target 7, then the numbers 3 7 1 7) the output is found 7 at index 1.

File: main.c

Starting point

#include <stdio.h>

const int *find(const int *a, int n, int target)
{
    /* return a pointer to the first match, or NULL */
    return NULL;
}

int main(void)
{
    int target;
    int values[100];
    int n = 0;

    if (scanf("%d", &target) != 1) {
        return 1;
    }
    while (n < 100 && scanf("%d", &values[n]) == 1) {
        n++;
    }

    /* call find and print the result */
    return 0;
}

Example

input

7  3 7 1 7

expected output

found 7 at index 1

Example

input

4
1 2 3

expected output

4 not found
Hint 1

Loop for (const int *p = a; p < a + n; p++) and return p; as soon as *p == target. After the loop, return NULL;.

Hint 2

In main: const int *p = find(values, n, target); then test p != NULL before using it.

Hint 3

Subtracting two pointers into the same array gives the number of elements between them, of type ptrdiff_t, printed with %td.

Reference solution
#include <stdio.h>

const int *find(const int *a, int n, int target)
{
    for (const int *p = a; p < a + n; p++) {
        if (*p == target) {
            return p;
        }
    }
    return NULL;
}

int main(void)
{
    int target;
    int values[100];
    int n = 0;

    if (scanf("%d", &target) != 1) {
        return 1;
    }
    while (n < 100 && scanf("%d", &values[n]) == 1) {
        n++;
    }

    const int *p = find(values, n, target);
    if (p != NULL) {
        printf("found %d at index %td\n", target, p - values);
    } else {
        printf("%d not found\n", target);
    }
    return 0;
}