02 - nested arrays

Syntax

Notice order of layers. The outer layers of multidimentional arrays appear on the left in declarator syntax.

1
2
3
4
5
6
7

int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};
int arr[4][2][3] = {
	{{1, 2,  3}, { 4,  5,  6}},
	{{2, 4,  6}, { 8, 10, 12}},
	{{3, 6,  9}, {12, 15, 18}},
	{{4, 8, 12}, {16, 20, 24}}
};

For multidimentional arrays, only the first (outermost) layer can have inferred size:

1
2

int arr[][2] = {{1, 2}, {10, 20}}; // ok: inferred size 2
int arr[2][] = {{1, 2}, {10, 20}}; // error

Multidimentional traversal

When looping over multidimentional arrays, pay attention in which order layers are accessed:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>

int main()
{
	constexpr int size_y = 5;
	constexpr int size_x = 10;

	int arr[size_y][size_x] = {};

	// do not change these loops, they fill the array
	// with data that represents its order in memory
	for (int y = 0; y < size_y; ++y)
		for (int x = 0; x < size_x; ++x)
			arr[y][x] = size_x * y + x;


	std::cout << "proper multidimentional array loop:\n";
	for (int y = 0; y < size_y; ++y)
	{
		for (int x = 0; x < size_x; ++x)
			std::cout << arr[y][x] << ", ";

		std::cout << "\n";
	}

	std::cout << "badly written multidimentional array loop:\n";
	for (int x = 0; x < size_x; ++x)
	{
		for (int y = 0; y < size_y; ++y)
			std::cout << arr[y][x] << ", ";

		std::cout << "\n";
	}
}

The example above aims to present that a working set of nested loops may cause very inefficient memory traversal. Both sets of loops work but only the first one accesses elements in order of increasing memory addresses. The second one correctly accesses each element exactly once, but does it in a very "jumpy" way which will generally limit effectiveness of cache - modern hardware is designed to access memory sequentially.

For this reason, when looping over nested arrays you should start with outer layers first and go into inner layers in nested loops.

Translated indexes

Multidimentional arrays are often replaced with 1D arrays that map multidimentional indexes to a single dimention in order to simplify code that uses them.

Here is the same program as above but realized using this method instead:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>

int index_2d_to_1d(int y, int x, int size_x)
{
	return size_x * y + x;
}

int main()
{
	constexpr int size_y = 5;
	constexpr int size_x = 10;
	constexpr int size_total = size_x * size_y;

	int arr[size_total] = {};

	// do not change these loops, they fill the array
	// with data that represents its order in memory
	// (these could also be written using 1D index)
	for (int y = 0; y < size_y; ++y)
		for (int x = 0; x < size_x; ++x)
			arr[index_2d_to_1d(y, x, size_x)] = size_x * y + x;

	for (int i = 0; i < size_total; ++i)
	{
		if (i % size_x == 0)
			std::cout << "\n";

		std::cout << arr[i] << ", ";
	}
}

In such case looping over elements is much easier, you only need a small helper function to translate 2D index into 1D.

Which approach is more efficient?

I don't think there is any significant difference between both, assuming there is any. In the case of the first, when [] operator is nested it basically does the same thing as the helper function in the later example. It just hides the same computation inside pointer arithmetics while in the second example it is done explicitly. The goal of both is to move in a such way that memory is accessed sequentially.

How would 3D to 1D translation look like?

1
2
3
4

int index_3d_to_1d(int z, int y, int x, int size_y, int size_x)
{
	return size_y * size_x * z + size_x * y + x;
}

Is it possible to do a reverse index translation? From 1D back to multidimentional?

1
2
3
4
5
6
7
8

// 2D
x = index % size_x;
y = index / size_x;

// 3D
x = index % size_x;
y = index % (size_x * size_y) / size_x;
z = index / (size_x * size_y);

Exercise

Recall previous task with printing multiplication table. Now modify it so that first it fills an array with values and then loops over the array to print contained values. Do it in both ways (nested array and translated index).