Pointer Arithmetic for Multi-Dimensional Arrays

How Multi-Dimensional Arrays are Stored in Memory

The first thing to understand is that computer memory is a single, one-dimensional sequence of bytes. A multi-dimensional array must be "flattened" into this linear space. C, C++, and many other languages do this using row-major order. This means the first row is stored contiguously, followed by the second row, and so on.

The opposite is column-major order, used by languages like Fortran and MATLAB, where columns are stored contiguously. Given your work involves integrating with various systems and possibly analyzing data from different sources (like MATLAB simulations), being aware of these conventions is valuable.

This contiguous, row-by-row layout is the foundation for all multi-dimensional array pointer arithmetic in C.

Pointer Types and Arithmetic in 2D Arrays

Let's connect this to our previous lesson. Consider this declaration:
int arr[3][4];

This is a 2D array. Conceptually, it's an array of 3 elements, where each element is an array of 4 integers.

• The name arr refers to the entire array. When used in an expression, it decays to a pointer to its first element.
• What is the first element of arr? It's the first row, arr[0], which is an array of 4 integers.
• Therefore, arr decays to a pointer to an array of 4 integers. Using the syntax we learned, its type is int (*)[4].

This type is crucial because it tells the compiler the size of the object being pointed to—an entire row. This is how pointer arithmetic scales correctly.

• arr points to the start of the first row (&arr[0]).
• arr + 1 points to the start of the second row (&arr[1]). The address is incremented by sizeof(int[4]), which is 4 * sizeof(int) bytes.
• *arr (which is the same as arr[0]) refers to the first row. In an expression, it decays to a pointer to its first element, &arr[0][0]. Its type is int *.
• *arr + 1 points to the second integer in the first row (&arr[0][1]). The address is incremented by just sizeof(int).

The following video provides an excellent visualization of these concepts and the different pointer types involved.

The Equivalence of Indexing and Pointer Arithmetic

With this understanding, we can now translate standard array indexing arr[i][j] into its pointer-based equivalent. The compiler effectively performs this transformation for you.

arr[i][j] is equivalent to *(*(arr + i) + j)

Let's break this down piece by piece, using our int arr[3][4] example:

1. arr: A pointer to the first row (type int (*)[4]).
2. arr + i: Pointer arithmetic. This yields a pointer to the i-th row. The address is (address of arr) + i * sizeof(int[4]). The type is still int (*)[4].
3. *(arr + i): Dereferencing this pointer gives us the i-th row itself (arr[i]). When used in an expression, this array name decays to a pointer to its first element, &arr[i][0]. The type is now int *.
4. *(arr + i) + j: More pointer arithmetic. Since the pointer type is now int *, we add j * sizeof(int) to the address. This gives us a pointer to the j-th element in the i-th row (&arr[i][j]).
5. *(*(arr + i) + j): The final dereference, which retrieves the actual integer value at that address.

The following document provides a superb textual analysis of this equivalence and explains why the compiler must know the array's column dimension to make this work.

Generalizing to 3D and Beyond: Performance Matters

The same logic extends naturally to higher dimensions. For a 3D array C[d1][d2][d3], the name C is a pointer to a 2D array of size d2 x d3. The expression C[i][j][k] becomes *(*(*(C + i) + j) + k).

This deep understanding of memory layout is not merely academic; it has critical performance implications. In your work with ADAS, you process large data sets (camera images, RADAR cubes, etc.) where performance is paramount. Traversing this data in the order it's stored in memory (row by row in C) is crucial for CPU cache efficiency.

When you access elements sequentially, you benefit from spatial locality. The CPU can pre-fetch subsequent memory into its fast L1/L2 caches, leading to huge speedups. Accessing elements out of order (e.g., column by column in a row-major array) can lead to constant cache misses, forcing the CPU to wait for data from slow main memory.

Conclusion

Today we've connected the abstract syntax of pointer-to-array types with the concrete reality of memory layouts and pointer arithmetic. You can now not only read but also understand and apply the pointer logic that underpins C's multi-dimensional arrays.

Key Takeaways:

• C stores multi-dimensional arrays in a contiguous block using row-major order.
• The name of a 2D array, T arr[R][C], decays to a pointer of type T (*)[C]—a pointer to an array.
• Pointer arithmetic on this type scales by the size of a full row (C * sizeof(T)).
• The indexing expression arr[i][j] is equivalent to the pointer expression *(*(arr + i) + j).
• Traversing data in its memory-storage order (row-by-row in C) is crucial for performance due to CPU caching and spatial locality.

Preview of the Next Lesson:
We've explored a specific, powerful type: the pointer to an array. In our next lesson, we will generalize this concept and explore pointers to pointers. This will enable us to tackle a classic C problem: how to write a function that can modify a pointer variable belonging to its caller. This technique is essential for managing dynamic resources and implementing more complex data structures.