A bit about multi-dimensional arrays

Introduction

Linear 1D arrays are all fine, but you'll understand with experience (maybe you already do) that they're not enough.

Maybe, instead of just storing the marks for a single subject of 30 students, you want to store marks that those 30 students have scored in 5 different subjects?

Or maybe you want to write an algorithm that solves a Rubik's cube given its initial state.

Or you have a problem that will be solved using Dynamic Programming with a complex state dependent on 3-4 variables. (This, you'll probably understand later on)

In the above cases, don't you think having support for 2D, 3D and 4D arrays, respectively, will be helpful? Well, I'm not sure about you, but I certainly feel so, and please feel free to share your thoughts as feedback if you disagree.

In an Array's form

Declaring a multi-dimensional array involves specifying the array's dimensions in the declaration. It's somewhat similar to declaring a 1D array.

Declaring

// The skeleton:
// data-type array-name[dim-1-size][dim-2-size][...so on];

// Examples:
int marks[30][5]; // 30 students, 5 subjects
char grade[30][5]; // Same: 30 students, 5 subjects
string teacher_remarks[30][5]; // Same

// Example for variable sized array:
int n, m, k; cin >> n >> m >> k;
int arr[n][m][k];

Initialisation

int pixels[4][3] = {
  {1, 1, 1},
  {0, 0, 1},
  {0, 1, 0},
  {1, 0, 0}
};


int incomplete_pixels[4][3] = {
  {1, 1, 1},
  {1, 0, 1}
}; // Rest of the rows will be 0.


int pixels_more_than_req[4][3] = {
  {1, 1, 1, 0},
  {1, 0, 1, 1}
}; // Will give an error because the number of columns is 3, yet 4 are initialised.

In a Vector's form

For a vector, it's basically just changing the template class for the vector; instead of making a vector<int>, we can make a vector<vector<int> >. Feel free to see some examples below:

Declaring

// Skeleton for 2D:
// vector<vector<data-type> > vector-name(dim-1-size,vector<data-type>(dim-2-size));

// Examples:
vector<vector<int> > marks(30, vector<int>(5)); // 30 students, 5 subjects
vector<vector<char> > grade(30, vector<char>(5)); // Same: 30 students, 5 subjects
vector<vector<string> > teacher_remarks(30, vector<string>(5)); // Same

// Example for variable sized array:
int n, m, k; cin >> n >> m >> k;
vector<vector<vector<int> > > vec(n, vector<vector<int> >(m, vector<int>(k)));

Initialisation

vector<vector<int> > pixels = {
  {1, 1, 1},
  {0, 0, 1},
  {0, 1, 0},
  {1, 0, 0}
}; // Will create a 4*3 vector.

vector<vector<int> > pixels_sized(4) = {
  {1, 1, 1},
  {0, 0, 1},
  {0, 1, 0},
  {1, 0, 0}
}; // Specifying the size and initialising will give an error.

vector<vector<int> > pixels_dynamic = {
  {1, 1, 1},
  {0},
  {0, 1, 0, 3},
  {1, 0}
}; // Having different row sizes is also not a problem.

Accessing elements

Accessing is the same in both cases.

To access an element at the index i, j in the case of 2D, you can write arr[i][j]. (assuming the name of the vector/array is arr).

Similarly, for 3D, if the index is i, j, k, then it could be done using arr[i][j][k].

I'm sure you get the catch by now.

How are they stored in memory?

If I talk about 2D arrays, there are 2 ways that could be used to store the elements. Well, there, of course, can be many more ways, but we're going to talk about 2 of them. Before starting, let me clarify, that just like the plain old 1D arrays, the multi-dimensional ones are also stored in a contiguous fashion.

Now, there are two popularly-known ways using which it could be done:

Column-Major

As the title might be suggest, store the elements column-wise. For an array with 2 rows and 3 columns, the order of storing the elements would be arr[0][0] -> arr[1][0] -> arr[0][1] -> arr[1][1] -> arr[0][2] -> arr[1][2]

Row-Major

Here, we store the elements row-wise. For an array with 2 rows and 3 columns, the order of storing the elements would be arr[0][0] -> arr[0][1] -> arr[0][2] -> arr[1][0] -> arr[1][1] -> arr[1][2]

Conclusion

Specifically, for 2D, as far as I could find online, and after trying it out on the C++ compiler in my mac, the data is stored in the row-major form.

Now, if you'd like to extend it to more than 2 dimensions, my hunch is that may be it's like that the elements corresponding to the 0^th index of the first dimension are stored first, and then going forward.

For example, if there's a 3D array, then arr[0] is basically a 2D array, right? So, what I mean is that, first, all the elements of that 2D array are stored, then we move to the data of arr[1] and so on...