Arrays and strings · about 45 min

Arrays and functions

Why this matters

As soon as programs grow, you want functions like "sum these numbers", "sort this list" or "find the largest". All of them take arrays. Passing arrays to functions in C works differently from passing plain numbers, and the difference is the first glimpse of pointers: what travels into the function is not the array but where it is. Getting this right explains why functions can change your arrays, why they always ask for a length, and one of gcc's more surprising warnings.

Writing a function that takes an array

#include <stdio.h>

int sum(const int a[], int n)
{
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += a[i];
    }
    return total;
}

int main(void)
{
    int week[7] = {3, 0, 5, 2, 8, 1, 4};
    int pair[2] = {10, 20};

    printf("week: %d\n", sum(week, 7));
    printf("pair: %d\n", sum(pair, 2));
    printf("first three days: %d\n", sum(week, 3));
    return 0;
}

week: 23
pair: 30
first three days: 8

The parameter int a[] has empty brackets: the function accepts an int array of any length.
The caller passes just the name, sum(week, 7), with no brackets.
The length travels as a second parameter. The same function works on arrays of any size, and even on just the first part of an array (sum(week, 3)).
const promises that sum only reads the elements. More on that below.

What is actually passed

You learned in the functions module that C passes arguments by value: the function receives a copy. If arrays were copied too, passing a million-element array would copy four megabytes on every call. C does not do that. When you use an array's name as a function argument, it is converted to the address of its first element, and that address is what gets copied into the parameter.

  main's stack frame                         sum's stack frame
 +------------------------------------+     +----------------------------+
 | week: | 3 | 0 | 5 | 2 | 8 | 1 | 4 | <---+-- a: address of week[0]    |
 |        0x1000                      |     | n: 7                       |
 +------------------------------------+     | total, i                   |
                                            +----------------------------+

Inside sum, a[i] means "the element i steps after the address in a", which is week[i] in main's memory. There is only one array.

This conversion is called array decay (the array "decays" to a pointer to its first element). A parameter written int a[] is really a pointer parameter; int *a means exactly the same thing. Pointers are the subject of the next module, which will make this precise. For now, the practical consequences are what matter.

Consequence 1: the function can change the caller's array

#include <stdio.h>

void scale(int a[], int n, int factor)
{
    for (int i = 0; i < n; i++) {
        a[i] *= factor;
    }
}

void try_change(int x)
{
    x *= 10;
}

int main(void)
{
    int v[3] = {1, 2, 3};
    int k = 5;

    scale(v, 3, 10);
    try_change(k);
    printf("v = %d %d %d, k = %d\n", v[0], v[1], v[2], k);
    return 0;
}

v = 10 20 30, k = 5

try_change modified its private copy of k. scale modified the elements at the address it was given, which are main's elements.

Consequence 2: the function cannot know the length

The address of the first element says nothing about how many elements follow. Inside the function, sizeof a gives the size of the address, not of the array:

#include <stdio.h>

void show_size(int a[])
{
    printf("inside function: sizeof a = %zu\n", sizeof a);
}

int main(void)
{
    int data[10] = {0};
    printf("in main: sizeof data = %zu\n", sizeof data);
    show_size(data);
    return 0;
}

main.c: In function 'show_size':
main.c:5:56: warning: 'sizeof' on array function parameter 'a' will return size of 'int *' [-Wsizeof-array-argument]
in main: sizeof data = 40
inside function: sizeof a = 8

8 bytes is the size of an address on a 64-bit machine. Writing a number in the brackets, as in void f(int a[10]), does not help: the 10 is ignored. That is why the C convention is "array plus length", seen everywhere in the standard library (memcpy(dest, src, n), qsort(base, n, ...)).

Consequence 3: you cannot return an array

A function's return type cannot be an array. To "produce" an array, the usual pattern is for the caller to provide one and the function to fill it:

void fill_squares(int out[], int n)
{
    for (int i = 0; i < n; i++) {
        out[i] = i * i;
    }
}

The caller owns the memory and decides how big it is. (Returning memory created inside a function needs malloc, in the dynamic memory module.)

const parameters

const int a[] means "through a, the elements are read-only". It documents to readers that the function will not change the array, and the compiler enforces it:

void clear(const int a[], int n)
{
    for (int i = 0; i < n; i++) {
        a[i] = 0;
    }
}

main.c:4:14: error: assignment of read-only location '*(a + (sizetype)((long unsigned int)i * 4))'

That message is gcc showing you its internal view of a[i]: the address in a plus i * 4 bytes. It is a preview of pointer arithmetic. Mark every array parameter const unless the function needs to change the elements.

A pattern: separate the work from the I/O

Notice that sum, scale and fill_squares do no input or output. Functions that take an array and a length and return a result are easy to test (the exercises in this lesson are checked by calling your functions directly with many arrays) and easy to reuse. Keep scanf and printf in main or in small dedicated functions.

Common mistakes

Writing brackets in the call: sum(week[], 7) is a syntax error (expected expression before ']' token), and sum(week[7], 7) passes the single (out-of-bounds) element week[7], an int, which GCC 14 rejects with error: passing argument 1 of 'sum' makes pointer from integer without a cast [-Wint-conversion].
Using sizeof on a parameter to get the length: you get 8 / 4 = 2 for every int array. Heed -Wsizeof-array-argument.
Passing the wrong length: the function trusts you. Pass 8 for a 7-element array and it reads past the end.
Assuming the function works on a copy: writes through an array parameter change the caller's data. Use const when that is not intended.
Starting a "maximum" at 0: for arrays that may contain negative numbers, start from the first element instead.

Recap

An array argument decays to the address of its first element; the function works on the caller's array, not a copy.
int a[] and int *a are the same parameter; the function cannot know the length, so pass it.
sizeof on an array parameter gives the pointer size; gcc warns.
Functions cannot return arrays; let the caller supply an output array.
Use const on array parameters that are only read.

Going further: read man 3 memset and man 3 memcpy. Both take an address and a byte count, which is the same "address plus length" convention you just learned.

Exercises

Exercise 1 · quiz

Why pass the length?

Why do C functions that process arrays, like int sum(const int a[], int n), take the number of elements as a separate parameter?

Because it makes the function faster
Because the function receives only the address of the first element, so it cannot know how many elements there are
Because C arrays store their length in element -1 and the function needs to verify it
It is only a convention; sizeof a / sizeof a[0] inside the function works just as well

Answer

Because the function receives only the address of the first element, so it cannot know how many elements there are

When you pass an array, C passes the address where it starts, nothing more. The function has no idea whether 3 or 3000 elements follow. Inside the function, sizeof a is the size of an address (8 bytes on the sandbox), and gcc warns with -Wsizeof-array-argument if you try. So the caller, which does know the length, passes it along.

Exercise 2 · quiz

Predict the output

What does this program print?

#include <stdio.h>

void update(int a[], int x)
{
    a[0] = 99;
    x = 99;
}

int main(void)
{
    int arr[2] = {1, 2};
    int y = 1;
    update(arr, y);
    printf("%d %d %d\n", arr[0], arr[1], y);
    return 0;
}

1 2 1
99 2 99
99 2 1
1 2 99

Answer

99 2 1

y is passed by value: update gets its own copy in x, and changing the copy does nothing to y. The array is different: update receives the address of arr's first element, so a[0] = 99 writes into main's array. Nothing was copied except the address.

Exercise 3 · write code

Where is the largest?

Write a function

int max_index(const int a[], int n)

that returns the index of the largest element among a[0] to a[n-1]. If the largest value occurs more than once, return the index of its first occurrence. You may assume n >= 1.

The main in the starter is just for your own experiments; the check calls max_index directly with many arrays (including all-negative ones) and prints what it got if something is wrong.

File: main.c

Starting point

#include <stdio.h>

int max_index(const int a[], int n)
{
    /* your code here */
    return 0;
}

int main(void)
{
    int t[5] = {4, 9, 2, 9, 1};
    printf("%d\n", max_index(t, 5));   /* should print 1 */
    return 0;
}

Example

expected output

Hint 1

Keep the index of the best element seen so far, starting with 0.

Hint 2

Loop from 1 to n-1. Use > (not >=) so a later equal value does not replace the first one.

Hint 3

Do not start with a 'best value' of 0: for an all-negative array no element would beat it. Compare against a[best] instead.

Reference solution

#include <stdio.h>

int max_index(const int a[], int n)
{
    int best = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[best]) {
            best = i;
        }
    }
    return best;
}

int main(void)
{
    int t[5] = {4, 9, 2, 9, 1};
    printf("%d\n", max_index(t, 5));   /* should print 1 */
    return 0;
}

Exercise 4 · write code

Reverse in place

Write a function

void reverse(int a[], int n)

that reverses the first n elements of a in place: it changes the caller's array, using no second array. After reverse on {1, 2, 3, 4, 5} with n = 5 the array holds {5, 4, 3, 2, 1}. It must work for even and odd n, and for n of 0 or 1 (nothing to do).

The check calls your function on several arrays and compares the results.