I use C, commericaly since 1991. This is where I record what I know about allocating and managing 2D/1D arrays in C. And I keep on revisiting this doc and clarifying it ever more. Many times I cought myself re-discovering what I have stored in here. Please do not repeat the same mistake.
Short answer is this:
+ -- int (*arp)[2][3] // 2D array pointer
V
+------------- int arr[2][3] -----------+
| |
| | int[3] | int[3] | |
| +-----+-----+-----+-----+-----+-----+ | matrix[1] is array pointer to the second row
| | 0 | 1 | 2 | 3 | 4 | 5 | <--- matrix[1][2] is int value
| +-----+-----+-----+-----+-----+-----+ |
| | matrix[0] | matrix[1] | |
+------^--------------------------------+
|
+ int(*matrix)[3] // 1D array pointer
Long answer follows.
In C, 2D array is array of arrays. What does that mean? You have a declaration in your code:
int arr[2][3];Compiler does not know or care about rows and columns. If compiler could talk, it would explain the above declaration as:
array of 3 integers repeated twice;
for which I have reserved on the stack,
6 times size of a integer;
as one contiguous memory block.
If we could listen to it, we would know the compiler has allocated, on the stack a column of 24 bytes:
2 x 3 x sizeof(int) = 24 bytes
That is 6 x sizeof(int), aka 24 bytes. As 4 is size of int in bytes. Thus memory block of 24 bytes.
Memory block of 24 bytes to store 6 integers
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | 3 | . | . | . | 22 | 23 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
That is a memory allocated for int[2][3] aka int[2*3].
Fortunately we are not coding in assembler and we can stay on the higher level of abstraction than compiler can. We just need to know compiler has allocated an array of 6 integers as a result of that declaration.
Array of 6 integers aka int[2*3]
+-----+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+-----+
Compiler is mapping int[2*3] array to a memory block above. But, did we not required int[2][3] ?
The best way to level all that in your head is to code the above 2D array initialization in C in one line:
// two times array of 3 int's, aka 6 int's
// this takes 24 contiguous bytes in memory
// aka 6 * sizeof(int)
// aka 6 * 4
int arr[2][3] = { {1,2,3}, {4,5,6} } ;It is customary to say "two rows, three columns each". But. We need to make a slight but scary detour to try and explain why you should not think in "rows" and "columns".
Humans usually feel it "natural" to think of the above as "two rows of three int's", and thus to mentaly picture the above as:
1 2 3
4 5 6
Hence the terms "rows" and "columns". For 2D arrays this might be fine but for 3 or more "dimension" this is definitely not "fine". In C there is (almost) no limit to the number of array "dimensions".
// initialize this ?
int arr[2][2][2] ;That is 2 x 2 x 2 = 8 integers. Just start reading from the right. In human language above is : Array of two int's, repeated twice and then all of that repeated twice. In some form of pseudo code that might be:
// all read from right
// repeated twice twice array of two int's
2 * 2 * int[2] We can transform that into C declaration and initialization. It might be easier if you write this from "inside". Starting from array {1,2} and so on.
int arr3D[2][2][2] =
{
{ // once
{1,2}, // array of two int's
{3,4} // second array of two int's
} ,
{ // twice
{5,6}, // array of two int's
{7,8} // second array of two int's
}
} ; Some humans find it (much) easier to say: "two levels of int[2][2] matrices". As that is 3D array that is probably fine. But what about this completely legal C:
// what is your analogy for this structure?
int arr[2][2][2][2] ; 4 dimensions. Cartesian 3-dimensional space we live in breaks here. Don't worry we will stop here. The point was to try and explain why is it not a "good thing" just to think in term of "rows" and "columns". Try to think of matrices as compiler "thinks". Repetition of 1D arrays, reading from the right.
How do we use 2D array in C is not the same compiler thinks of it. How does that work. Recap:
// two times array of 3 int's
int arr[2][3] =
{
{1,2,3}, // "row" 0 is int[3]
{4,5,6} // "row" 1 is int[3]
} ;That is stored as 24 bytes in a single memory column of 6 integers. Your friend compiler allows you to use the matrix values in a "natural way", by addressing the cells with their indexes.
printf("\n%d", arr[1][1] ) // 5Compiler maps above human readable view, to the required value of the internal 1D array (memory column) representation.
Above print's the second value aka "element 1" from the second (of two) int[3] arrays. Yes, those humans again. They find it much easier to think of the above as the spreadsheet aka table
arr[2][3]
| rows / columns | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 2 | 3 |
| 1 | 4 | 5 | 6 |
Indexing goes from 0 as ever in C of course. Thus arr[1][1] is 5.
Please do remember. int[2][3] is mapped to the memory block of 24 bytes.
Memory block of 24 bytes keeps 6 int's to store int[2][3]
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 0 | 1 | 2 | 3 | . | . | . | 22 | 23 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Compiler does the "rewiring" and you do not have to worry (just a little), about a direct memory addressing. You simply think of it as a "table" with "rows" and "columns". Unless you need to deal wit more than 3 dimensions, as we have learned above.
That is orinteering course for C scouts done. But, on the more practical note, how do we allocate large 2D arrays? Stack allocation will fail rather quickly. You can try playing with MAX constants from stdint.h. Thast is not a problem. We would use the heap; malloc() and friends. Simple? Perhaps.
That is very important concept to understand and remember. In C, when made, memory block has no type info attached to it. It is just N bytes of RAM. But, upon memory allocation program can dictate what type will be effectively imposed onto the allocated memory. In C you do not need to, but you want to do that. Here is Why:
// just allocate a block of 24 bytes and give it no type
// void * block has no effective type
// malloc returns void pointer
void * block = malloc( 24 ) ;
// here is how , with difficulties
// you "put" int value 64 to that block
// starting from the "left" end of the block
// aka the left most location
*((int*)(block + 0)) = 64 ;Not very human readable one might admit. That is why we do:
// giving the effective type to the block allocated
// allocate block of 6 int's
int * int_block = malloc( 6 * sizeof(int) ) ;Above the compiler has silently re-writen into:
int (* int_block)[6] = malloc( 6 * sizeof(int) ) ;So that when you write:
int_block[0] = 64 ;We can re-writes that line to:
// compiler 'knows' int_block stores integers
*(int_block + 0) = 64 ;
// remember the compiler again rewrites any of the two above to:
*((int*)(block + 0)) = 64 ;Obviously in C we can code the above in different ways in regards what program needs to do.
Things are becoming interesting. Why would compiler do this silent re-writes?.
The following section is inspired with this. Caution, it is sharp and short. Just what you need :) This is what I do too, so being lazy I have done a paste in here and reworked it, with small changes.
In C never use a pointer-to-pointer to allocate multi-dimensional arrays. It is wide-spread but bad and incorrect practice. Doing so will not give you a true 2D array, and it will lead to slower code because of heap fragmentation. It also makes the code harder to write, read and maintain, which in turn increases the potential for memory leaks.
Instead, allocate the 2D array correctly in adjacent memory cells, like this:
// for example
int x = 0xFF ; int y = 0xF;
// carefully study the following line
int(*matrix)[y] = malloc (sizeof(int[x][y]));
if(matrix == NULL) { /* error handling here */ }
matrix[i][j] ; // notice how we can use the familliar notation here
free(matrix);If you insist on keeping this code in a function, then it would be: ( NOTE: I have changed this function slightly; in this form it is decoupled from type)
// I have changed it so the result is 'type less'
void* allocMatrix (int nRow, int nCol, size_t typesize )
{
// calloc zeroes the memory allocated
return calloc ( nRow * nCol, typesize);
// before, the type int was used
// int(*matrix)[y] = malloc (sizeof(int[x][y]));
}
// NOTE: you need to understand fully this line
// explanation is further bellow
// allocate array of x * y, integers
// caste the result to the pointer to the first row
// if need be jump qucikly to the diagram on the top of this article
int(*matrix)[y] = allocMatrix(x, y, sizeof(int) );This line has been taken out by me (the author of this paper) from allocMatrix; nevertheless we shall use it for the concept clarification:
int(*matrix)[y] = malloc (sizeof(int[x][y])); The detail: sizeof(int[x][y]) is pretty straight-forward, it is just the size of a Variably Modified Type (VMT) 2D array of integers with dimensions x*y. Compiler translates this into the number of cells of the memory block of x * y * 4 bytes, as 4 is size of int. x and y are runtime values. That is the concept of variably modified types (VMT) from the C99 standard, which allows array dimensions to be specified in runtime.
(I have replaced malloc() with the calloc() call, as explained in the code.)
Key concept: array pointers
An array pointer is a somewhat special compound type in C, it is 'able' to point to whole arrays, rather than just at the first item of the array, as a 'normal' decayed pointer will do, after a famous "array decay". The array pointer, is a regular pointer. It is not array decayed into pointer. Decayed array pointer is the same pointer as the first element of the array.
int a1d[] = { 1,2, 3,4 } ;
int * decayed_p = a1d ;
int * first_element_p = &a1d[0] ;
assert( decayed_p == first_element_p) ;An array pointer is written as type(*name)[size], so for example an array pointer to that array of 4 int's would be written as:
int(*arr_ptr)[4] = &a1d ;When accessing the contents pointed at, an array pointer behaves just as any pointer, you access the contents of it with * aka dereferencing operator. So *arr_ptr gives the array pointed at, and (*arr_ptr)[0] gives the first item of that array.
For multi-dimensional arrays, the same rules apply, but with the second dimension added. Given the array int arr[x][y], an array pointer to this type will be:
// two rows, thre columns each
int x = 2, y = 3 ;
int arr[x][y] = { { 1,2,3 } , { 4,5,6 } } ;
int(*arr_ptr)[x][y] = &arr;Accessing the contents *arr_ptr will give you a two-dimensional array, which is equivalent to an array of arrays.
// first column of the first row
int val = (*arr_ptr)[0][0] ; // 1(*arr_ptr)[0] will therefore give the pointer to the first array (aka row) in that array of arrays.
So, the rule for any standard array name when used in an expression, is that it "decays" into a pointer to the first element. Same does not apply here, so int(*arr_ptr)[0] will therefore also be the a pointer to the first array aka "row". And (*arr_ptr)[0][0] will give the first element content of the first "row". Don't worry there are diagrams coming. All will be clear.
That syntax (*arr_ptr)[0][0] looks a bit hard to read; to get the first item of a 2D array, we are used at writing just arr[0][0].
Let us repeat what we already know. Instead of declaring the complete and correct array pointer: int(*matrix)[x][y], an array pointer to a 2D array of dimensions x*y, we instead declare it as int(*matrix)[y], which is an array pointer to a first 1D array with dimension y. When we cast 2d array pointer to it, it will point at the first "row" in the 2D array, which is a 1D array of size y. And we know that the 2D array contains x such 1D arrays.
And because of this "trick", we are now able to use the array pointer with the same syntax as when accessing a 2D array, namely matrix[i][j], rather than the hard-to-read (*matrix)[i][j].
Phew! That was a short and hard kick directly from the deep foundation levels of C. And that is all correct. That is how you too, will code 2D arrays in C. Here is why and how with (yet another) repetitions of what we alreay know.
That is a key C programming concept here. Lets re-use our int[2][3] from above.
// array declaration and initialization
// this is two times int[3]
int arr[2][3] = { {1,2,3}, {4,5,6} } ;
// 2D array pointer declaration
int (*arp)[2][3]
// pointing to the whole int[2][3]
= &arr ;Visually:
+--- int arr[2][3] ---------------------+
| |
| | int[3] | int[3] | |
| +-----+-----+-----+-----+-----+-----+ |
| | 0 | 1 | 2 | 3 | 4 | 5 | |
| +-----+-----+-----+-----+-----+-----+ |
+---------------------------------------+
^
|
+ -- int (*arp)[2][3] // array pointer
Understand that diagram and you are done here. Almost. Just that "trick"to be explained. How do we index the above block allocated in the "natural" way? Aka matrix[x][y] ? With that arp above,as declared, we need to cast (*arp)[x][y] to "naturaly" reach any value x,y as that 2D array is a "table" we are used to. How? Let's build slowly up to the solution. Let's use another pointer to the same block from above.
// input from above: int (*arp)[2][3] aka the array pointer type
// but what is this??
int(*not_matrix_1)[3] = arp[0] ;For above we are getting the warning from the compiler: warning: incompatible pointer types initializing 'int (*)[3]' with an expression of type 'int [3]'; take the address with & [-Wincompatible-pointer-types]. Type of expression arp[0] is array, not a pointer to the array. And by now you know this is even worse:
int(*not_matrix_2)[3] = & arp[0] ;That is the pointer to the first element of the 1D array int[3], and nothing else, aka int *. Extremely not good, as we now know we can not reach the second "row" aka int[3] from int[2][3] by "simply" writing not_matrix_2[1][1]. Good old C compiler will let us write that without a warning, and it will address a memory which is not ours. A ticking time bomb.
This is a legal way to declare, define and use the array pointer to the first 1D array (aka "row")int[3] of the whole of int[2][3] 2D array:
// input from above: int (*arp)[2][3] aka the 2D array pointer type
// the casting is necessary
// this is the "trick"!
// after this we can write: matrix[1][1]
int(*matrix)[3] = (int(*)[3])arp ;is Instead of casting the whole 2D array pointer, you might be using the pointer to the first row, as an "effective" type, when the block allocated. Thus no casting will be necessary down the line.
// effective type here is not a pointer to the whole 2D array
// it is array pointer to the first "row" of the 2D array
// remember each row of the two, is 1D array int[3]
int(*matrix)[3] = malloc( sizeof(int[2][3]) ) ;To paraphrase: matrix will point at the first item in the 2D array, which is a 1D int array of size 3. And. We know that the 2D array contains 2 "rows", 0 and 1.
Importantly : matrix[0] and matrix[1] are 1D arrays.
That non-trivial situation is best understood when visualised. (note: 0 .. 5 are indices not values)
+ -- int (*arp)[2][3] // 2D array pointer
V
+------------- int arr[2][3] -----------+
| |
| | int[3] | int[3] | |
| +-----+-----+-----+-----+-----+-----+ | matrix[1] is array pointer to the second row
| | 0 | 1 | 2 | 3 | 4 | 5 | <--- matrix[1][2] is int value
| +-----+-----+-----+-----+-----+-----+ |
| | matrix[0] | matrix[1] | |
+------^--------------------------------+
|
+ int(*matrix)[3] // 1D array pointer
Let us repeat the key line once more:
// allocsate on the heap 24 bytes aka 2 * 3 * sizeof(int)
// give it efective type as 1D array pointer to the row 0
int(*matrix)[3] = malloc( sizeof(int[2][3]) ) ;Remember: In C the casting of the malloc result is not required. Thus we can do the above without compiler warnings. And we have given the "effective type" to the allocated block.
Since that matrix is the real pointer pointing to the above structure we can use the [][] indexing operators on it.
// we have initialized with
// { {1,2,3}, {4,5,6} }
// matrix[0] is the first 1D array: int[3]
// thus
matrix[0][1] ; // equals 2By far the best course of action is to employ your good IDE and debugger and follow slowly this little program: (hint:industry agrees, the best is Visual Studio)
// (c) 2021 by dbj at dbj dot org
// https://dbj.org/license_dbj
// https://godbolt.org/z/rzzaPMPah
#include <assert.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
// 2D array declaration and initialization, on stack
int arr[2][3] = { {1,2,3}, {4,5,6} } ;
// we can play with the underlying memory block
typedef unsigned char uchar ;
// pointer to the first byte of the underlying memory block
uchar * block = (uchar*)&arr ;
// pointer to the third int
uchar * int_no_3_ptr = block + (2 * sizeof(int)) ;
// the value is 3
int int_no_3 = (int)*int_no_3_ptr;
// or we can stay sane and deal with the real matrix of int's
// effective type we give is regular pointer to the whole of int[2][3]
int (*arp)[2][3] = malloc( sizeof(int[2][3]) ) ;
// row array pointer to the whole of the: int arr[2][3]
int(*matrix)[3] = (int(*)[3])arp ;
/*
using the above we can index "naturaly"
for example we can fill one by one
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[1][0] = 4;
matrix[1][1] = 5;
matrix[1][2] = 6;
*/
// or we can copy the array to array
// as mem block to mem block
// underlying data is int[2][3]
memcpy( arp, &arr, sizeof(int[2][3]) ) ;
assert( matrix[0][1] == 2 );
// release the whole
free( matrix ) ;
return 42;
}I think we are getting somewhere. Well done.
© 2021 APR by dbj at dbj dot org
Author of the inspiration for the middle section ("Allocating 2D Arrays") is "Lundin"