ICS 45C Spring 2022, Notes and Examples: Single-Dimension Arrays

Background

Of course, you don't need to dream very big to dream up a program that has the need to store a collection of objects instead of just a single one: a collection of students enrolled in a course, a collection of financial instruments in an investment portfolio, a collection of statements in a function (if you're writing a compiler), and so on. Collections are, practically speaking, one of the hallmarks of a programming language's usability. If there's a built-in set of the obviously useful ones, and if it's reasonably straightforward to build your own when you need something more exotic, it's going to be much easier to write real programs that solve real problems.

It's quite common to need to store a homogeneous collection, in which each element has the same type. Like most programming languages, C++ provides mechanisms for solving this problem. The most basic of these mechanisms is called an array — or, more completely, a single-dimension array — which is our focus in this example.

As we'll see later this quarter, there are cleaner mechanisms available besides arrays, but arrays serve as the raw materials for how some of those other mechanisms are built. Our focus early in this course is to understand the underpinnings of C++, so we can build a good, reasonably complete mental model of what happens while a C++ program executes. For that reason, it's a good idea for us to start with the raw materials and work our way up. So we'll begin our exploration of collections by looking at arrays in some depth, then pivot to other, easier-to-use, less error-prone mechanisms later.

What is an array?

An array is a sequence of cells that live contiguously — one directly following another — in memory. Each cell has an index, with the first cell having the index 0, the second cell having the index 1, and so on. The cells are all of the same type (e.g., int, std::string, or whatever) and, hence, they all have the same size. (The latter part is actually really important: That the cells of an array are uniformly sized is why accessing an array cell, given its index, is relatively inexpensive.)

When an array is created, it is given a size, which specifies the number of cells it has. It retains that size for the rest of its lifetime, with no language-level mechanism available to extend the size of an array once it's been created. From the very beginning, each cell contains an object of the specified type — so, for example, in an array of ints, each cell contains an int object. Additionally, there is no standard, generally-applicable construct in C++ to ask an array its size; if you want to keep track of an array's size, you'll have to do so separately.

As we'll see, there are C++ expressions that will allow you to access individual cells in an array, and it is also possible to manipulate them in whole (e.g., by passing an entire array as an argument to a function). But there are a few conceptual hurdles we'll need to cross before we get to these.

Statically-allocated arrays

As with every other kind of object we've seen in C++, we have a choice about how our arrays are to be allocated and where they will be stored, with the most common two choices being static allocation on the run-time stack (via a local variable in a function) or dynamic allocation on the heap (using pointers and the new operator). Of these, static allocation is the simplest, which we tend to prefer because it gives us a couple of important benefits:

Automatic deallocation when the array falls out of scope
A likelihood of the array being in cache a lot of the time, as the current stack frame is accessed often and, hence, likely to be cached

However, statically allocating an array also leaves us with disadvantages, moreso than some other kinds of variables that we might statically allocate:

Run-time stacks are generally limited in size, given that most programs don't tend to need function calls that nest to an incredibly deep level. But this imposes a limitation on how much data you can store in local variables; at some point, a stack frame will simply be too big to be practical. (And, of course, the larger it is, the less benefit you'll see from caching.)
Arrays must be given a size at the time they're created. Statically-allocated objects are given a size at compile time, so a statically-allocated array must have a size that is known to the compiler (e.g., a hard-coded constant or another expression calculated only from constants). Quite often, though, we use data structures whose sizes vary depending on run-time factors such as user input; this would be impossible with a statically-allocated array.
Statically-allocated objects have fixed lifetimes; for example, local variables in a function die when the function ends. When we want more open-ended lifetimes, we can't use static allocation.

Nonetheless, there are substantial use cases where we can statically allocate arrays — namely, when we have small arrays of known size at compile time whose lifetimes match up nicely with the duration of some function call — so we'll start there.

We allocate arrays statically by declaring them as variables; we make a variable into an array by following its name with a size surrounded by brackets.

void foo()
{
    int a[10];
    // ...
}

Having declared the variable a this way, it will be statically allocated, meaning that the entire array — all 10 integer objects — will be on the run-time stack. On the ICS 45C VM, integers are four bytes each, so that means we've got 40 bytes of integer data stored on the run-time stack. 40 bytes isn't a lot, so this is certainly no problem, but it's important to realize that there's no other kind of indirection here, and there is no overhead; this is exactly equivalent, in terms of storage, to having 10 integer variables.

Accessing individual cells — to read their values or to write them — is done using a similar bracket-based syntax. When you write an expression comprised of the name of an array, followed by an index surrounded by brackets, the result is a reference to some cell in that array, meaning that you can both read from that cell and write to it, just as you would a variable of that cell's type (e.g., in the case of a above, each cell is an int).

void foo()
{
    int a[10];
    a[3] = 4;
    std::cout << a[3] << std::endl;
}

From a language perspective, C++ arrays do not appear to know how big they are; there's simply no universal syntax to ask the question "How many cells does this array have?" Furthermore, no checking is done to ensure that accesses to array cells are legal. Given the array a above, accesses to individual cells such as a[12] or a[-3] would be legal — in the sense that they would compile, at worst, with warnings — but nonsensical, quite possibly dangerous, and would result in undefined behavior (i.e., there's no guarantee what will happen, and it may be different on different operating systems, different compilers, or even different versions of the same compiler). It's up to us as C++ programmers to avoid these out-of-bounds accesses, but it's important to realize that they will be allowed, and may lead to such undesirable consequences as assigning values willy-nilly into memory that lives outside of the array's boundaries, changing the guts of some other object (that might well have a completely different type!), or even writing over some of a program's machine code while it runs.

When the function foo() ends, the array a will be destroyed automatically, taking with it all of the objects in the array; no special cleanup will be needed.

Dynamically-allocated arrays

When a statically-allocated array can't be used — because you don't know the appropriate size at compile time, because you know the array is too large to reasonably fit on the run-time stack, because you need the array to outlive the function in which it's created — there exists the option of a dynamically-allocated array instead. Dynamically allocating an array involves the use of the new operator, similar to dynamic allocation of other objects; the difference is that an array requires us, additionally, to specify a size.

Dynamically allocating an array is done using a new expression, which dynamically allocates enough memory to store the entire array, then returns a pointer to the array's first cell.

int* a = new int[10];

The expression new int[10] allocates a block of memory on the heap large enough to store 10 integers — on the ICS 45C VM, that would be 40 bytes — and returns a pointer to the first one. The location of the second directly follows the first, the third directly follows the second, and so on, and all of the cells are the same type. So given a pointer to the first cell and an index, it is possible, behind the scenes, to calculate the index of any given cell using the following calculation:

address of cell i = (address of cell 0) + (sizeof(int) * i)

Note that it's no more expensive to calculate the address of a cell with a large index than with a small one. This calculation is simply a multiplication and an addition; if we were to assume that memory access takes constant time given an address, accessing any cell in an array would take constant time. (In practice, memory access times can vary due to effects like caching, though you can reasonably think of main memory accesses — those that aren't already in cache — as taking constant time.)

Interestingly, the type of pointer you get back doesn't specify anything about an array. When we allocated an array of ints dynamically, what we got back was an int*, i.e., a pointer to an int. Arrays, in general, are implemented as pointers to their first cells, and it's up to us to know whether a particular int* is pointing to a single int or an array of ints (and, in fact, there's no standard way to ask!).

Once you have a pointer to an array, you can access its cells similarly to those of a statically-allocated array:

int* a = new int[10];
a[3] = 4;
std::cout << a[3] << std::endl;

The expression a[3] is equivalent to the hypothetical expression *q, where q is a pointer to an int located three cells (on the ICS 45C VM, 12 bytes) beyond the one that a points to. In other words, a[3] gives you the integer in that cell (technically, a reference to it), rather than a pointer to that cell.

When you're done with a dynamically-allocated array, you would need to explicitly deallocate it, just as you would any other dynamically-allocated object. However, it's important to note that you use a different operator, delete[ ], to do so. Like delete, you give delete[ ] a pointer to an array, and it deallocates the entire array (and all of the objects in all of its cells) for you.

delete[] a;

It's up to you to know which pointers point to arrays, and to use delete[ ] when it's warranted. Using delete on a pointer to an array instead of delete[ ], or using delete[ ] on a pointer to a single value instead of delete, results in "undefined behavior" (which means that compiler writes can generate any code they'd like in this case; some do the right thing, but others don't).

Just like uses of delete that we've seen previously, the pointer a is unaffected, though it is now pointing to unallocated memory, so it is now dangling and should no longer be used.

Passing arrays as parameters to functions

The simplest way to pass an array as a parameter to a function, regardless of how the array was allocated, is to pass a pointer to its first element. But since there's no way for the function to ask the array's size, you would also need to pass its size as a separate parameter. For example, consider this function, which completely fills an array of ints with zeroes.

void zeroFill(int* a, unsigned int size)
{
    for (unsigned int i = 0; i < size; ++i)
    {
        a[i] = 0;
    }
}

Note that this function will gleefully write as many zeroes into memory as you tell it to, regardless of the actual underlying size of the array that a points to. In other words, this would be legal (though obviously erroneous):

int* x = new int[10];
zeroFill(x, 50);       // Writes 50 zeroes to memory, starting with the cell where x points!

It's up to us to handle these details correctly, and, in general, we'll receive no help from the compiler to ensure this. In some cases, we might get warnings (though, in this case, I'd expect that to be rare-to-nonexistent). In others, we'll get crashes. In still others, the program will continue muddling forward with potentially bizarre behavior, with a bunch of 0-bits having been written to memory that was storing some other value we may have been intending to use.

(The moral of this story is partly that arrays are a difficult mechanism to use correctly, so we're wise to use cleaner, safer ones when we can afford them. We'll cross that bridge a little later this quarter.)

Pointer arithmetic

Pointers are memory addresses, and memory addresses are numbers. So it's not entirely nonsensical to think that you can perform certain kinds of arithemtic on pointers, similar to the arithemtic you can perform on ints. In C++, which allows this kind of thing, it is called pointer arithmetic. Pointer arithmetic is more limited than the arithmetic you can do on ints. For example, multiplication and division are not supported. Addition involves a pointer and an integer. Subtraction might involve a pointer and a constant integer, or it might involve two pointers.

Consider the following short example, which demonstrates a few ways that pointer arithmetic works in C++:

int a[10];                           // a is effectively a pointer to the first element of the array
int b[10];                           // b is also effectively a pointer
std::cout << a << std::endl;         // writes the address of a[0]
std::cout << (a + 1) << std::endl;   // writes the address of a[1]
*(a + 1) = 3;                        // stores 3 in a[1]
std::cout << (a - 1) << std::endl;   // writes the address of a[-1]
std::cout << (a - b) << std::endl;   // writes the distance in memory between a[0] and b[0] (divided by the size of an int)

In general, we can see that pointer arithmetic works by considering the type of object the pointers are said to point to. For example, a + 1 doesn't just add the integer value 1 to the address of a; instead, it adds the size of an integer to the address of a or, in other words, calculates a position one integer beyond where a points. In that sense, pointer arithmetic is very much like array indexing and, in fact, the array-indexing operations you write are ultimately translated by a compiler into the corresponding pointer arithemtic operations instead.

Given this technique, we can write some kinds of code differently; for example, our function above that zero-fills an array could be written this way:

void zeroFill(int* a, int size)
{
    int* end = a + size;

    for (int* p = a; p != end; ++p)
    {
        *p = 0;
    }
}

In this version of the function, p iterates over the array that a points to, visiting each cell. a + size is the address of the cell just beyond the last cell in the array, which makes an effective stopping point for the loop. ++p means "Move p so that it points to the next integer after the one that p points to now."

Given a naively-implemented compiler, a pointer-based solution like this one is potentially faster than its array-indexing counterpart, because it replaces the array index calculation (a multiplication and an addition) in each step with a simple addition (the increment operation) instead. However, I should point out that compilers with strong optimizers built into them might well recognize the pattern in the original version of our zero-filling function and transform it into the pointer arithmetic version for us. For example, as of this writing, when optimizations are turned on in our compiler (Clang), both versions of zeroFill above are translated into identical code: a call to the C standard library function memset.

My general rule is to start by writing code that's clear, then replace it with code with optimizations if (a) I find that I need them (i.e., some frequently-used part of my code is running slower than I need it to), and (b) the optimization isn't being performed automatically. Knowing the lower-level tools lets me hand-optimize things when I need to. But there is still a lot of premium to be placed on writing code that reads more clearly.