---

Single-dimension arrays in C++

In C++, you've no doubt seen before that there are single-dimension arrays, and that they come in two flavors: statically-allocated and dynamically-allocated.

As with anything else in C++, the statically-allocated version of an array has to be allocated by the compiler, so it must be possible to determine the size of the array at compile time; that means the size appears as part of the array's declaration, at which time the compiler must provide for its allocation.

int a[10];

Note that there is also a feature called variable-length arrays in recent versions of C, which is supported as an extension by some C++ compilers, but that is not officially part of the C++ standard. It allows you to do what appears to be static allocation of an array whose size is not known until run time:

void foo(unsigned int n)
{
    int a[n];

    // ...
}

While this feature can be implemented a bit differently by different compilers that allow it — because it is not, after all, a part of the C++ language, but is instead an extension provided by the compiler — our compiler allocates it dynamically on the run-time stack (i.e., it pushes it to the top of the stack when the time comes, then pops it when it falls out of scope). This is potentially problematic for a few reasons, not the least of which is that the run-time stack is generally allocated with a fairly limited size, so if n has a large value, that can cause problems up to and including program crashes.

Meanwhile, we can dynamically allocate arrays using the new operator, with the result being a pointer to the array's first element. Because it's allocated dynamically, its size can be determined at run time (e.g., by an expression with an integral type), and there are fewer restrictions on how large they can be.

int* a = new int[size];

Note, too, that even a statically-allocated array can be passed as a parameter, in which case you're really passing a pointer to its first element. So, ultimately, the function below could accept an array regardless of how it was allocated. And recall that you would need to pass the array's size as an additional parameter, since arrays don't carry size information with them and don't do any automated bounds checking. (This is one reason to consider using std::vector instead, which you can think of as a single-dimension array that is managed with the RAII technique, and which also provides the option of bounds checking by using the at() member function in place of the [ ] operator.)

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

For a longer treatment of this prerequisite topic, you can also check out the Single-Dimension Arrays notes from my most recent ICS 45C offering.

---

Multidimensional arrays in C++

Some data is inherently multidimensional, so the ability to store it in a data structure that lets you index in multiple dimensions can make it much easier to work with it. As always, we choose data structures on the basis of how convenient and how performant it will be for us to use them to solve the problems we're actually trying to solve. Something we can use to manage multidimensional data simply and efficiently would be a useful tool to add to our toolbox.

C++ offers the ability to create multidimensional arrays, though, like most things in C++, it's important that you understand some of their underlying implementation details, because they're limited in ways that don't necessarily make sense until you understand the details of how they work.

Statically-allocated multidimensional arrays

The most direct way to create a multidimensional array in C++ is to statically allocate it, which we do by including the size of each of its dimensions as part of its declaration. Because statically-allocated arrays have to be allocated at compile time, the bounds of each dimension must be constants (or, at the very least, constexprs, i.e., expressions that can be evaluated at compile time). Once defined, we can access its individual cells by indexing it in all dimensions. In the example below, we create a two-dimensional array and store a value in all of its cells.

int a[4][5];

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

From a purely conceptual perspective, you can think of this data as representing whatever you'd like. Speaking strictly conceptually, the "meaning" of the dimensions is determined by the problem you're trying to solve; as long as you index it correctly (i.e., you use the index appropriate for each dimension), you'll get the values you want. So, for example, you could think of the data in your mind as a matrix with four rows and five columns, in which case you'd have to index it by specifying a row first and then a column:

0	0	0	0	0
0	1	2	3	4
0	2	4	6	8
0	3	6	9	12

Or, alternatively, you could think of it as a matrix with four columns and five rows, in which case you'd have to index it by specifying a column first and then a row:

0	0	0	0
0	1	2	3
0	2	4	6
0	3	6	9
0	4	8	12

Speaking strictly conceptually, neither of these is inherently "correct"; it's purely a matter of how you've chosen to organize your data, and how you've chosen to think about it, with the only constraint being that you're consistent in your uses of the two dimensions, such that the first dimension in your indexing operation matches the first dimension when you allocated, and the second matches the second.

How multidimensional arrays are stored in memory

However, we also have to be cognizant of how multidimensional arrays are actually stored in memory, because that implementation technique imposes some constraints on how we use them, how we pass them as parameters, and so on. C++ stores multidimensional arrays in what is sometimes called row-major order, though this term only makes sense if you have the same mental bias about what constitutes a "row" and what constitutes a "column" as the person who coined that term. So, an alternative way to think about it is to think of it as first-dimension-major order, which is to say that all elements with the same index in the first dimension will be contiguous, and that the groups of elements with consecutive values in that dimension are also contiguous to one another. Our example two-dimensional array above would be laid out in memory like this, in one long, contiguous block of memory:

a[0][0]	a[0][1]	a[0][2]	a[0][3]	a[0][4]	a[1][0]	a[1][1]	a[1][2]	a[1][3]	a[1][4]	a[2][0]	a[2][1]	a[2][2]	a[2][3]	a[2][4]	a[3][0]	a[3][1]	a[3][2]	a[3][3]	a[3][4]
0	0	0	0	0	0	1	2	3	4	0	2	4	6	8	0	3	6	9	12
a[0]					a[1]					a[2]					a[3]

You might wonder why C++ "flattens" a multidimension array in memory, but it's important to realize that all of memory can be thought of as essentially one giant array, with a pointer or a reference representing an index into that giant array. Ultimately, everything is flattened in one way or another, with pointers and references used to help us find things that aren't immediately contiguous to one another. Some technique for flattening needs to be used; C++ uses the technique above.

You might also wonder why it's important for us to know this underlying implementation detail. If it's being done by the compiler automatically, why should we have to care about it? Is it just intellectual curiosity that makes us wonder about it, or does it have a bearing on how we use it? To understand the answer to this question, we need to also understand how individual cells in a multidimensional array are found.

How indexing into a multidimensional array actually works

You have likely seen previously that C++ indexes into a single-dimension array by performing an address calculation. If you've declared the following array:

int x[10];

then you can think of the value of x as really being a pointer to the first element in the array. (This is why, if you were to pass x as an argument to some function, int* would be a compatible type for the corresponding parameter.)

If you index into that array with the expression x[i], the compiler needs to generate code that finds the appropriate element. Since all of the elements are contiguous, and since they're all the same type (and, therefore, the same size), the calculation, conceptually, is address of x + (sizeof(int) * i), a calculation that you can also write in C++ by using pointer arithemtic: x + i.

Indexing into a multidimensional array is actually fairly similar, except it's a multi-step process (one for each dimension). For example, in our two-dimensional array a declared earlier in these notes, the expression a[i][j] would result in the following calculation being necessary. (Sticking with C++ implementation terminology, we'll use "rows" to describe the first dimension and "columns" to describe the second.)

• We know already where a[0][0] is, because a can be thought of as a pointer to the first element of the two-dimensional array.
• We first need to know where a[i][0] is, which will get us to the correct row. This can be done with the following conceptual calculation: address of a + (sizeof(int) * i * 5), where 5 appears because it's the number of columns in each row.
• Then, we need to know where a[i][j] is. If we've already got the address of a[i][0], we can do this: address of a[i][0] + (sizeof(int) * j).

Putting all of this together, expressed using C++ pointer arithemtic syntax, we have: a + (i * 5) + j. Note that the constant 5 (the number of columns) appears in this formula, but the constant 4 (the number of rows) does not. Extending this idea to a third dimension, a fourth dimension, and so on, we would see a fundamental truth: The size of every dimension except the first would have to be known in order to do this calculation.

Passing a multidimensional array to a function

We've seen before that arrays can be represented easily as pointers to their first element, so you might expect to be able to pass a multidimensional array the same way. And you've seen, also, that arrays do not store size information, so we would expect also to have to pass the size of its dimensions as additional parameters. That would lead you to believe that you could write this:

void fillTwoDArray(int* a, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            a[i][j] = i * j;
        }
    }
}

However, if you think about the realities of how a two-dimensional array is implemented, you'll see that this can't possibly work. The compiler will need to compile the expression a[i][j] into machine code that finds the appropriate cell in the two-dimensional array. But, as we've seen, the formula for doing that has an important input that can't be left out: the size of the second dimension! And even though that's technically been passed as a parameter to our function, C++ isn't aware of the correlation.

For the same reason, the following reasonable-looking line of code won't compile, either:

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

because two-dimensional arrays can't be represented simply by a pointer to their first element.

Passing a multidimensional array as a parameter to a function

In order to make our fillTwoDArray function work, the size of the second dimension has to be expressed as part of its type, making the following version legal.

void fillTwoDArray(int a[][5], int rows)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            a[i][j] = i * j;
        }
    }
}

It should be noted, though, that this function is more limited; it only works for a two-dimensional array whose second dimension is size 5. We could overcome that limitation by using a function template instead.

template <int Columns>
void fillTwoDArray(int a[][Columns], int rows)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < Columns; ++j)
        {
            a[i][j] = i * j;
        }
    }
}

Note that the reason the function template can work is because template parameters are always determined at compile time, so Columns will be a constant expression, which will appear in a call to the function:

fillTwoDArray<5>(a, 4);

---

Dynamically-allocated multidimensional data

Unfortunately, as we've seen, multidimensional arrays in C++ are limited to scenarios where we can determine the size of all of their dimensions except the first at compile time. Even if we dynamically allocate them, the only dimension whose value can be determined dynamically is the first one. So what do we do if we want dynamically-allocated multidimensional data, whose size we can't determine, in any dimension, until the program runs? There are a few possible answers to this.

Dynamically-allocated multidimensional arrays

While you can't dynamically allocate a multidimensional array directly, there is an alternative that works: Dynamically allocating a single-dimension array of dynamically-allocated single-dimension arrays.

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

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

This would be implemented with a being a pointer to the first element of a single-dimension array, in which each element is a pointer to the first element of some other single-dimension array. Indexing into this requires doing an address calculation, then following a pointer to one of the "subarrays," then doing another address calculation into the subarray. Syntactically, though, it would be identical:

for (int i = 0; i < rows; ++i)
{
    for (int j = 0; j < columns; ++j)
    {
        a[i][j] = i * j;
    }
}

A single-dimension array treated as multidimensional

Another option would be to allocate a single-dimension array dynamically, then do the address calculation yourself to make it act as though it was multidimensional. This would leave you the ability to use a dynamic number of rows and columns in the calculation, with the tradeoff being that you'd have to implement the calculation — though it would be something you could put into a short, inlineable function, so it would quite likely perform well. (And it wouldn't be a bad idea to write a function to do the indexing, for the simple reason that rewriting the same formula repeatedly would leave you the opportunity to make a mistake in one or more of its uses.)

int* a = new int[rows * columns];

for (int i = 0; i < rows; ++i)
{
    for (int j = 0; j < columns; ++j)
    {
        a[i * columns + j] = i * j;
    }
}

This is, more or less, a manually-implemented version of what C++ does already with multidimension arrays. The only trick is that writing the code ourselves allows us to write our own calculation that is capable of working purely with dynamic values that aren't known until run time.

A vector of vectors

A third option would be to use a std::vector, in which each element is a std::vector of values. From a performance perspective, this would be quite similar to the "pointer to an array of pointers to arrays" solution above, but with some of the underlying details automated for you.

// This version of the std::vector constructor allows you to give it a size
// and fill in all of these cells with the same value automatically, which is
// a handy way to make it start out with the right size.
std::vector<std::vector<int>> a(rows, std::vector<int>(columns));

for (int i = 0; i < rows; ++i)
{
    for (int j = 0; j < columns; ++j)
    {
        a[i][j] = i * j;
    }
}