Pointers, Arrays, and Strings

An object has a value stored in memory. The value is a semantically meaningful abstraction of the actual bit pattern that represents the value in memory. For example, in the code above, object i holds the integer value 5. On some platforms that value might correspond to the bit pattern 00000000000000000000000000000111; on other platforms the representation of 5 might be 00000111000000000000000000000000; on yet another platform it might be 0000011100000000. Arguably it doesn’t even make sense to talk about bit patterns, since bits can not be addressed individually. We’ll discuss that in a minute. The main point here is that the values we consider are those defined by the semantics of the objects. We therefore ignore the specific representation of those values in memory. Referring to the example, from our perspective, which is the point of view of a C/C++ program, object i has the ordinary numeric value 5.

An object also has a type. The type defines the set of possible values for the object, as well as the semantics of expressions involving the object. Notice that the type of the object is not a piece of information stored within the object. Rather, it’s a property of how the program uses the object. For objects that are explicitly declared in a program, as in the example above, the type is the one given by the declaration. So int i declares an object of type int. Pretty obvious. But there are also cases in which an object acquires a type by other mechanisms. We’ll see that another time.

Another property of the object is its size. This one is concrete and relatively simple. An object spans a contiguous region of memory. The size of the object is the number of bytes it spans. If you have the object or its type, you can get the size with the sizeof operator.

#include <stdio.h>

int main () {
    int i;      
    printf ("The size of i is %zu bytes\n"
            "The size of an int is %zu bytes -- no surprise\n",
            sizeof(i), sizeof(int));
}

Thus the sizeof operator can be applied to a variable or more generally to an expression (e.g., i), or to a type definition (e.g., int). The size is known at compile time. It is the compiler that decides how to represent an int or whatever other object you might want to define, so the compiler most definitely knows the size of each object. In other words, sizeof(a) is not an invocation of a sizeof function. There is no such function, and in fact there is no run-time call of any function, and furthermore the expression used as the operand of sizeof is not even evaluated. Instead, what matters is the type of the expression, and therefore writing sizeof(a) is equivalent to writing the literal value 4 or whatever the size is.¹

One last point about sizeof. As we said, sizeof gives you the size of an object measured in bytes. Don’t confuse that with the number of elements of an array or the length of a string. To see the difference, try the following program. Do it now! I know we haven’t seen strings or arrays in detail yet, but the example is intuitive enough.

#include <stdio.h>
#include <string.h>

int main () {
    int A[10];
    char * s = "Use the Force, Luke!";
    printf ("The size of `int A[10]' is %zu bytes\n", sizeof(A));
    printf ("The size of `char * s' is %zu bytes\n", sizeof(s));
    printf ("s = \"%s\"\n", s);
    printf ("strlen(s) is %zu bytes\n", strlen(s));
}

Okay, so we measure the size of an object in bytes. But what is a byte, exactly? Excellent question. When we talked about input/output, we defined a byte as a number between 0 and 255. That definition is good enough to understand input/output, and the numeric range 0–255 is indeed correct on most common modern platforms. However, that definition does not capture the fundamental notion of bytes that is essential to the memory model of C/C++, which is what we’re after.

Here’s the real definition: a byte is the smallest chunk of memory that you can address individually. You can address an individual int object, but that is not the smallest addressable unit (on most modern architectures). A single bit is definitely the smallest unit of memory, but bits can not be addressed individually (on most modern architectures). Most often (on common modern architectures), a byte consists of 8 bits, and therefore can store up to 256 values that can therefore be interpreted as numbers between 0 and 255.

In C/C++, a byte corresponds to a char. So, the size of a char object is 1, by definition. That’s the size in bytes. The size in bits is instead platform dependent, and is given by the CHAR_BIT constant defined in limits.h. And again, the most common value for CHAR_BIT is 8. The char type is intended for the interpretation of bytes as characters. To interpret bytes as numbers we have signed char (typically from -128 to 127) and unsigned char (again, typically from 0 to 255). In fact, char is also a numeric type, and its range is that of either signed char or unsigned char, depending on the platform.

Since bytes are the smallest units of memory you can address individually, and since unsigned char is the most basic type of byte values in C, we can think of the memory of a C program as a big array of unsigned char objects. And since an object is essentially a contiguous region of memory, the representation of an object—meaning the content of the memory that represents the object—can also be seen as an array of unsigned char. This is not just a conceptual image of the representation of an object. You can in fact copy the representation of an object as a whole into an array of unsigned char. To do that, you must use the memcpy function of the C/C++ standard library. Still, the point is that you can do that for any object regardless of the semantic value of the object. For example, the code below prints the memory representation of an int object.

#include <stdio.h>
#include <string.h>

int main () {
    int a;
    unsigned char a_rep[sizeof(a)];
    printf ("input an integer: ");
    scanf ("%d", &a);
    memcpy(a_rep, &a, sizeof(a)); /* copy the representation of a into a_rep */
    printf ("the representation of %d (int) is:\n", a);
    for (int i = 0; i < sizeof(a); ++i)
        printf ("%hhu ", a_rep[i]);
    printf ("\n");
}

We can also copy object representations in the opposite direction, from an array of unsigned char into an object, and also between objects of the same type. In the example below we again use memcpy, this time to construct an int value by writing its representation from a sequence of bytes.

#include <stdio.h>
#include <string.h>

int main () {
    int a;
    unsigned char a_rep[sizeof(a)];
    printf ("input the %u byte values that make up the representation of an integer: ");
    for (int i = 0; i < sizeof(a); ++i)
        scanf ("%hhu ", &(a_rep[i]));
    memcpy(&a, a_rep, sizeof(a)); /* copy the bytes in a_rep into object a */
    printf ("the int value of ");
    for (int i = 0; i < sizeof(a); ++i)
        printf ("%hhu ", a_rep[i]);
    printf ("is %d\n", a);
}

Keep in mind that object representations are platform dependent. Still, the memory copy illustrated above is perfectly valid and safe in both directions.

Quiz 1: What’s the value of sizeof(char)?

Quiz 2: Is sizeof(char) platform-dependent?

Yet another property of an object is its lifetime. This is the portion of the execution of the program (possibly the whole execution) during which the object exists and has a stored value at an immutable position in memory. Just as a quick example, consider the following code:

#include <stdio.h>

int main () {
    unsigned int count = 0;
    for (int c = getchar(); c != EOF; c = getchar())
        if (c == ' ')
            ++count;
    printf ("%ud\n", count);
}

The lifetime of count is the entire execution of the main function. However, the lifetime of c is the execution of the for loop. Understanding this concept and in each case knowing the exact lifetime of an object is absolutely essential. So, this is a topic we will definitely return to.

With all these properties, you might think that the concept of object is complicated. Nah. In essence, it is quite straightforward: objects are values stored in memory. Big deal. But then, what’s the big fuss, uh?! (And just as an aside, does it even make sense to talk about a value not stored in memory?)

Well, this is a big deal. Get this: I’d go as far as claiming that this is the most important notion to understand programming, in C/C++ and many other languages. I said it! (And then yes, there are most definitely values that aren’t stored in memory, and we’ll discuss those as well at some point.) So why is this notion of object such a big deal? Sit up, take a deep breath, and listen carefully. This is a big one.

In addition to its value, size, lifetime, etc., an object has an address, a memory address. The address is what it says it is: it’s an indication of the location of the object in memory. And since the address of an object stays constant during the lifetime of the object, you can use that address to refer to the object in your program. Furthermore, addresses are themselves values that can be stored and processed like any other object. This is indeed a huge deal—YUGE!

This notion—the idea of a memory address that can be used to access an object, and that is itself an object—is so important that C and C++ have specific language constructs to represent and use those addresses, namely pointers. A pointer is an abstraction of a memory address. The actual representation of memory addresses is platform dependent and ultimately irrelevant for us, and even the addresses themselves, meaning the values of pointers, have no meaning in and of themselves. What is important is that a pointer can “point to” an existing object, and therefore allows the program to use that object. I told you, this is huge.

Still not convinced, eh? You might think, we have those objects and we know their names, since we declared them ourselves. And we can of course refer to each object by name. You can write things like i = 7; printf("%d\n", i); which first writes the value 7 into the object we called i, and then reads and prints the value of the same object. Not only that: we have seen a lot of code until now, and none of that uses pointers, right? What else do we need pointers for?

Well, first of all, wrong, the code we saw uses pointers here and there. Even the very first “Hello, World!” example does in fact use pointers. But more importantly, think about it, how would you implement a dynamic data structure? I mean something like a linked list or a binary tree. How would you do that without pointers?²

You might still argue that other programming languages like Java and Python don’t have pointers. So, pointers can’t be so fundamental, right? WRONG! Big mistake. Pointers are everywhere in Java and Python. Java and Python programmers just don’t call them that way. In Java, except for basic types like int and double, all objects are accessed by pointers. If you declare a string with String s or an array of integers with int [] A, you are not declaring any object of type String or any array. You’re declaring pointers to those objects: s is a pointer to an object of type String, and A is a pointer to an array of int. The objects themselves don’t even exist with just those declarations, and in fact the initial value of s and A is the “null” pointer. So, Java is all about pointers, except that they are called “references.” Same thing in Python. In fact, while in Java there are at least some objects that you can actually declare and access directly, namely variables of the basic types such as int i = 7, in Python literally everything is a pointer. Even a simple assignment like x = 7 that supposedly assigns what looks like an integer value to x actually assigns a pointer to an object of type int whose semantic value is 7.

Now we have some pointer variables. Let’s see how to use them. Initially the values of i and p are indeterminate, since the two objects have not been initialized. So let’s give them some values. For int objects we can write literal values directly in the program. For example, we can write i = 5; and that would store the int value 5 into i. That makes sense and is useful because the semantics of the int type—meaning, the concept of an integer, its arithmetic operations, order relations, etc.—is well defined at the application level.

Things are different for pointers. Memory addresses are platform dependent, and furthermore they can change from one execution to the next. And even if they didn’t, their specific values are meaningless at the level of applications. So, it makes no sense for us to try to assign a predetermined, literal value to p. Actually, that’s not completely true. There is one literal value that makes sense as a pointer value. That’s the “null” pointer, and we’ll discuss that later. But other than that, the only values that make sense for pointers are given by the address of specific existing objects. In our example, we do have an int object, i, so what we can do is take its address and assign it to p. With that, we can say that p point to i.

i = 7;                        /* the value of i is 7 */
p = &i;                       /* the value of p is the address of i */

The address-of operator (&) applies to an object and returns the address of that object. In the example above, the address-of operator takes the address of a named variable (i). However, it can take the address of any object. For example, here we apply it to an int object that is itself a member of an array object.

int A[10];
int * p;

p = &(A[5]);                  /* p points to A[5] */

Notice that the type of the address-of expression is correct: A[5] identifies an object of type int, and therefore the address-of operator takes its address as an int * value (pointer to int), which is the same type declared for p. So, we’re good.

We now have an int i and an int * p where p points to i. We can now refer to i either by name or through p. Here’s the full example:

#include <stdio.h>

int main () {
    int i;
    int * p;
    i = 7;
    p = &i;
    *p = 8;
    printf ("i = %d\n", i);
}

The expression *p is given by the dereference (or indirection) operator (*) applied to pointer p. That expression identifies the object referenced, or “pointed to” by p. And since p points to i, writing *p is equivalent to writing i. For example, you can write *p = *p + 1; and that would be equivalent to writing i = i + 1. I want to reemphasize that the expressions i and *p identify the exact same object.

C uses call-by-value semantics. What that means is that a function parameter is a copy of the arguments passed by the caller. Which in turn means that no matter how the function changes the value of the parameters, those changes will not affect the arguments passed by the caller. In other words, it would seem that functions can return a value to the caller, but other than that can not change the value of a variable of the caller context.

This is of course a good thing, since you wouldn’t want a function you call to mess around with your variable, would you? Except that sometime that’s exactly what you want. For example, you might want to develop a very powerful function that reads some formatted data from the input and then returns that data to the caller. If the data consists of a single value, say an int, that you can have the function return that value. But what if you are reading, say, the coordinates of a 2D point? How can you have your input-reading function return two int values?

This is where pointers come to the rescue. In fact, we have already seen a powerful input-reading function that can read multiple values. It’s scanf. So scanf can read two int, and to do that takes two int pointers as arguments, as in the example below:

#include <math.h>

int main () {
    int xa, ya;
    int xb, yb;
    int first = 1;
    double len = 0;
    while (scanf (" ( %d, %d)", &xb, &yb) == 2) {
        if (first) {
            first = 0;
        } else {
            len += sqrt((xb - xa)*(xb - xa) + (yb - ya)*(yb - ya));
        }
        xa = xb;
        ya = yb;
    }
    printf ("polygon length = %lf\n", len);
}

Did you try the example above? Pretty neat! Don’t fool yourself. I know you didn’t try it. How do I know? Because that program uses the sqrt function from the math library, and most likely your compiler must be told to link that library. Okay, perhaps you did compile and run the program, in which case I’m super happy and I apologize for the unwarranted snarky tone. Anyway, this is how you compile that program. Assuming the code is in a source file path_length.c, do the following:

cc path_length.c -lm -o path_length

And now you can compute the length of a polygonal chain (with integer coordinates). And notice the wonders of scanf. You can read from a formatted input. And did you notice that you can tell scanf to skip white spaces in the input? Aren’t you happy you went through the trouble of compiling that program now?!

Another, very simple example of a function that is intended to manipulate variables from the caller context is the swap function. The idea is to swap the values of two variables, say int variables. How do we do that? Simple, again, we pass the pointers to those integer variables.

#include <math.h>

void swap (int * p, int * q) {
    int tmp = *p;
    *p = *q;
    *q = tmp;
}

int main () {
    int i = 7;
    int j = 5;
    swap (&i, &j);
    printf ("i = %d\nj = %d\n", i, j);
}

Now, did you try this yourself?

Good!

In general, different pointer types are not compatible with each other. This is even when the types they point to are themselves compatible. For example, you may not assign a char * value to an int * object, even though assigning a char value to an int object is perfectly okay.

int i;
char c;
int * p;                /* pointer to int */
int ** pp;              /* pointer to pointer to int */

c = 'a'; 
i = c;                  /* correct: types are compatible */
p = &i;                 /* correct: same type no both sides of = */
p = &c;                 /* error: assigning char * to int * */
pp = &i;                /* error: int* is not compatible with int** */
pp = &p;                /* correct: same type */

It is useful, however, to have a common, generic pointer type. In C (but not in C++) a void * serves that purpose. In fact, any pointer type can be implicitly converted to and from a void *. Here’s an example:

int i;
int * p
int * q;
void * x;

p = &i;
x = p;                          /* x can take values of any pointer type */
q = x;                          /* x can be converted into any pointer type */

assert (q == &i);               /* the implicit conversions maintain
                                   the original pointer*/

As a universal pointer type, void * can be used represent references to polymorphic objects. For example, that is what you would do with an interface (reference) in Java. Yet more generally, void * can be used whenever you want to refer to any object, which is something you’d want to do quite often in C. You do that when you don’t care about the object type, or when the object has yet to acquire a type. Either way, void * is your friend. For example, the standard memcpy function copies objects (referred by pointer) regardless of their type, and in fact memcpy is declared as follows:

void * memcpy (void * dest, const void * src, size_t n);

Okay, that makes sense, but what is this business of objects acquiring a type? Does that mean that objects in C are like larvae that morph into caterpillars and then into butterflies? Well… Nah. It’s quite simple, really. We’ll see this in detail later, and many times after that, but here’s a quick preview.

#include <stdlib.h>

int * new_array_ramp (int n) {  /* return an array of n int */
    int * ramp = malloc (n*sizeof(int));
    if (ramp != 0)
        for (int i = 0; i < n; ++i)
            ramp[i] = i;
    return ramp;
}

This function returns an array of int consisting of \(n\) elements whose values are initialized to \(0,1,\ldots,n-1\). The array object is created (as a whole) with the standard malloc function. malloc needs to know the size of the object, but not its type. In fact, malloc returns a void * representing a pointer to a fresh portion of memory of the given size. That object—the chunk of memory allocated and returned by malloc—has no declared type, and instead acquires an effective type with the first write operation. The same goes for memcpy: if the destination object has no declared type, the destination acquires the effective type of the source.

Pointer values are platform dependent and totally irrelevant to the application semantics. I know we said that already, but it’s worth repeating. There is no circumstance in which a programmer could use or even just assign a specific pointer value and be guaranteed to have a valid pointer, meaning a pointer corresponding to an address of a valid (live) object. On the other hand, it is useful to have a pointer value guaranteed not to be a valid pointer. That is what the “null” pointer is: a pointer value that will never be the address of an object.

The null pointer can therefore be returned by functions that return pointers to indicate a failure or some other special condition.

int main () {
    int * A = malloc (sizeof(int)*100000);
    if (A == NULL) {
        printf ("Out of memory!\n");
        return EXIT_FAILURE;
    } else {
        int i, x;
        for (i = 0; i < 100000 && scanf (" %d", &(A[i])) == 1; ++i);
        while (i > 0)
            printf ("%d\n", A[--i]);
        return EXIT_SUCCESS;
    }
}

The null pointer can also be used as the terminator value for data structures such as linked lists or trees.

struct linked_list {
    int value;
    struct linked_list * next;
};

void print_list (const struct linked_list * l) {
    while (l) {                 /* null pointer == 0 (meaning false) */
        printf ("%d\n", l->value);
        l = l->next;
    }
}

The NULL macro defined in stdlib.h and many other standard headers defines the null pointer value for C and C++ programs. However, in C++ and also in the recent C23 version of C, you can and should use the nullptr keyword. The numeric constant 0, when used as a pointer, also denotes the null pointer. In fact, the null pointer compares equal to 0, and therefore is interpreted as false when used as a Boolean expression.

Arrays are related to pointers. Since the elements of an array are laid out in memory one after the other, there is a linear relation between the index of an element in the array and the pointer to that element. But wait: we said many times that pointer values have no meaning, so how come now we treat them as numbers? The trick is that we don’t really care about the specific values of pointers. Rather, we care about the relation between pointer values, and we abstract those relations in such a way that operations on indexes in an array correspond directly to analogous operations with pointers. Let’s see this with an example:

int A[10];

printf ("A:");
for (int i = 0; i < 10; ++i) {
    A[i] = i*i;
    printf (" %d", A[i]);
}
printf ("\n");

printf ("A:");
for (int * p = &(A[0]); p != &(A[10]); ++p)
    printf (" %d\n", *p);
printf ("\n");

Here we use a pointer that initially takes the address of the first element of an array, and then we access all the elements of the array, in sequence, by incrementing the pointer. Again, the pointer values don’t make sense to us, so we define the pointer increment ++p such that the code works that way. In essence, if p points to an element of an array, then p+1 points to the next element. More generally, if p points to the $i$-th element of the array and n is an integer, then p + n is also a pointer, that points to the element in position \((i+n)\) in the array. This kind of sum between a pointer and an integer is illustrated in the example below:

int A[10];

printf ("A:");
for (int i = 0; i < 10; ++i) {
    A[i] = i*i;
    printf (" %d", A[i]);
}
printf ("\n");

printf ("A:");
int * p = &(A[0]);
for (int i = 0; i < 10; ++i) {
    printf (" %d\n", *(p + i));
printf ("\n");

So again, if we have a pointer p pointing to some element of an array, we ca write int * q = p + n; where n is an integer and q points n elements down in the array. It is therefore only natural to also define a difference operation between arrays. For example:

int A[10];
/* ... */
int * p = &(A[0]);
for (int * q = p; q != p + 10; ++q) {
    printf ("A[%ld] = %d\n", q - p, *q);