Declaring a pointer to multidimensional array and allocating the array
I just found this ancient answer still gets read, which is a shame since it's wrong. Look at the answer below with all the votes instead.
Read up on pointer syntax, you need an array of arrays. Which is the same thing as a pointer to a pointer.
int width = 5;
int height = 5;
int** arr = new int*[width];
for(int i = 0; i < width; ++i)
arr[i] = new int[height];
Correctly allocating multi-dimensional arrays
In order to answer the question, we should first clear up some concepts. What is an array and how can it be used? And what is the code in the question, if not an array?
What is an array?
The formal definition of an array is found in the C standard, ISO 9899:2011 6.2.5/20 Types.
An array type describes a contiguously allocated non-empty set of
objects with a particular member object type, called the element type.
In plain English, an array is a collection of items of the same type allocated contiguously, in adjacent memory cells.
For example an array of 3 integers int arr[3] = {1,2,3}; would be allocated in memory like this:
+-------+-------+-------+
| | | |
| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
So what about the formal definition of a multi-dimensional array? Actually, it is the very same definition as cited above. It applies recursively.
If we would allocate a 2D array, int arr[2][3] = { {1,2,3}, {1,2,3} }; it would get allocated in memory like this:
+-------+-------+-------+-------+-------+-------+
| | | | | | |
| 1 | 2 | 3 | 1 | 2 | 3 |
| | | | | | |
+-------+-------+-------+-------+-------+-------+
What we have in this example is actually an array of arrays. An array which has 2 items, each of them an array of 3 integers.
An array is a type like any other
Arrays in C often follow the same type system as regular variables. As shown above, you can have an array of arrays, like you can have an array of any other type.
You can also apply the same kind of pointer arithmetic on n-dimensional arrays as on plain one-dimensional arrays. With a regular one-dimensional arrays, applying pointer arithmetic should be trivial:
int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.
for(size_t i=0; i<3; i++)
{
printf("%d ", *ptr); // print contents.
ptr++; // set pointer to point at the next element.
}
This was made possible through "array decay". When arr was used inside an expression, it "decayed" into a pointer to the first element.
Similarly, we can use the very same kind of pointer arithmetic to iterate through an array of arrays, by using an array pointer:
int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.
for(size_t i=0; i<2; i++)
{
printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
ptr++; // set pointer to point at the next element
}
Again there was array decay. The variable arr which was of type int [2][3] decayed into a pointer to the first element. The first element was an int [3] and a pointer to such an element is declared as int(*)[3] - an array pointer.
Understanding array pointers and array decay is necessary in order to work with multi-dimensional arrays.
There are more cases where arrays behave just like regular variables. The sizeof operator works just the same for (non-VLA) arrays as for regular variables. Examples for a 32 bit system:
int x; printf("%zu", sizeof(x)); prints 4.int arr[3] = {1,2,3}; printf("%zu", sizeof(arr)); prints 12 (3*4=12)int arr[2][3] = { {1,2,3}, {1,2,3} }; printf("%zu", sizeof(arr)); prints 24 (2*3*4=24)
Like any other type, arrays can be used with library functions and generic APIs. Since arrays fulfil the requirement of being allocated contiguously, we can for example safely copy them with memcpy:
int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));
Contiguous allocation is also the reason why other similar standard library functions like memset, strcpy, bsearch and qsort work. They are designed to work on arrays allocated contiguously. So if you have a multi-dimensional array, you can efficiently search it and sort it with bsearch and qsort, saving you the fuss of implementing binary search and quick sort yourself and thereby re-inventing the wheel for every project.
All of the above consistencies between arrays and other types is a very good thing that we want to take advantage of, particularly when doing generic programming.
What is the pointer-to-pointer thing, if not an array?
Now to get back to the code in the question, which used a different syntax with a pointer-to-pointer. There is nothing mysterious about it. It is a pointer to pointer to type, no more no less. It is not an array. It is not a 2D array. Strictly speaking, it cannot be used to point at an array, nor can it be used to point at a 2D array.
A pointer-to-pointer can however be used to point at the first element of an array of pointers, instead of pointing at the array as whole. And that is how it is used in the question - as a way to "emulate" an array pointer. In the question, it is used to point at an array of 2 pointers. And then each of the 2 pointers is used to point at an array of 3 integers.
This is known as a look-up table, which is a kind of abstract data type (ADT), which is something different from the lower level concept of plain arrays. The main difference is how the look-up table is allocated:
+------------+
| |
| 0x12340000 |
| |
+------------+
|
|
v
+------------+ +-------+-------+-------+
| | | | | |
| 0x22223333 |---->| 1 | 2 | 3 |
| | | | | |
+------------+ +-------+-------+-------+
| |
| 0xAAAABBBB |--+
| | |
+------------+ |
|
| +-------+-------+-------+
| | | | |
+->| 1 | 2 | 3 |
| | | |
+-------+-------+-------+
The 32 bit addresses in this example are made-up. The 0x12340000 box represents the pointer-to-pointer. It contains an address 0x12340000 to the first item in an array of pointers. Each pointer in that array in turn, contains an address pointing at the first item in an array of integers.
And here is where the problems start.
Problems with the look-up table version
The look-up table is scattered all over the heap memory. It is not contiguously allocated memory in adjacent cells, because each call to malloc() gives a new memory area, not necessarily located adjacently to the others. This in turn gives us lots of problems:
We can't use pointer arithmetic as expected. While we can use a form of pointer arithmetic to index and access the items in the look-up table, we can't do so using array pointers.
We can't use the sizeof operator. Used on the pointer-to-pointer, it would give us the size of a pointer-to-pointer. Used to the first item pointed at, it would give us the size of a pointer. Neither of them is the size of an array.
We can't use standard library functions that excepts an array type (
memcpy,memset,strcpy,bsearch,qsortand so on). All such functions assume to get arrays as input, with data allocated contiguously. Calling them with our look-up table as parameter would result in undefined behavior bugs, such as program crashes.Repeated calls of
mallocto allocate several segments leads to heap fragmentation, which in turn results in poor use of RAM memory.Since the memory is scattered, the CPU cannot utilize cache memory when iterating through the look-up table. Efficient use of the data cache requires a contiguous chunk of memory which is iterated through from top to bottom. This means that the look-up table, by design, has significantly slower access time than a real multi-dimensional array.
For each call to
malloc(), the library code managing the heap has to calculate where there is free space. Similarly for each call tofree(), there is overhead code which has to be executed. Therefore, as few calls to these functions as possible is often preferable, for the sake of performance.
Are look-up tables all bad?
As we can see, there are a lot of problems with pointer-based look-up tables. But they aren't all bad, it is a tool like any other. It just has to be used for the right purpose. If you are looking for a multi-dimensional array, which should be used as an array, look-up tables are clearly the wrong tool. But they can be used for other purposes.
A look-up table is the right choice when you need all dimensions to have completely variable sizes, individually. Such a container can be handy when for example creating a list of C strings. It is then often justified to take the above mentioned execution speed performance loss in order to save memory.
Also, the look-up table has the advantage that you can re-alloce parts of the table in run-time without the need to re-allocate a whole multi-dimensional array. If this is something that needs to be done frequently, the look-up table might even outperform the multi-dimensional array in terms of execution speed. For example, similar look-up tables can be used when implementing a chained hash table.
How to properly allocate a multi-dimensional array dynamically then?
The easiest form in modern C is to simply use a variable-length array (VLA). int array[x][y]; where x and y are variables given values in run-time, prior array declaration. However, VLAs have local scope and do not persist throughout the duration of the program - they have automatic storage duration. So while VLAs may be convenient and fast to use for temporary arrays, it is not an universal replacement to the look-up table in the question.
To truly allocate a multi-dimensional array dynamically, so that it gets allocated storage duration, we have to use malloc()/calloc()/realloc(). I'll give one example below.
In modern C, you would use array pointers to a VLA. You can use such pointers even when no actual VLA is present in the program. The benefit of using them over a plain type* or a void* is increased type-safety. Using a pointer to a VLA also allows you to pass the array dimensions as parameters to the function using the array, making it both variable and type safe at once.
Unfortunately, in order to use the benefits of having a pointer to VLA, we can't return that pointer as a function result. So if we need to return a pointer to the array to the caller, it must be passed as a parameter (for the reasons described in Dynamic memory access only works inside function). This is fine practice in C, but makes the code a bit hard to read. It would look something like this:
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
While this syntax with a pointer to an array pointer might look a bit strange and intimidating, it doesn't get more complex than this even if we add more dimensions:
void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
*aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
assert(*aptr != NULL);
}
Now compare that code with the code for adding one more dimension to the look-up table version:
/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
int*** ppp = malloc(sizeof(*ppp) * x);
assert(ppp != NULL);
for(size_t i=0; i<x; i++)
{
ppp[i] = malloc(sizeof(**ppp) * y);
assert(ppp[i] != NULL);
for(size_t j=0; j<y; j++)
{
ppp[i][j] = malloc(sizeof(***ppp) * z);
assert(ppp[i][j] != NULL);
}
}
return ppp;
}
Now that is one unreadble mess of "three-star programming". And lets not even consider 4 dimensions...
The full code of a version using true 2D arrays
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
assert(*aptr != NULL);
}
void arr_fill (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
array[i][j] = (int)j + 1;
}
}
}
void arr_print (size_t x, size_t y, int array[x][y])
{
for(size_t i=0; i<x; i++)
{
for(size_t j=0; j<y; j++)
{
printf("%d ", array[i][j]);
}
printf("\n");
}
}
int main (void)
{
size_t x = 2;
size_t y = 3;
int (*aptr)[x][y];
arr_alloc(x, y, &aptr);
arr_fill(x, y, *aptr);
arr_print(x, y, *aptr);
free(aptr); // free the whole 2D array
return 0;
}
Pointer to a 2D dynamic Array Pointer
Further down the answer, you find more possible solutions.
First, I want to present a solution to you, where you manage a dynamic 2d array with a 1d pointer, in case of same-length columns.
#include <stdlib.h>
#include <stdio.h>
struct XYZ
{
int someValue;
};
struct XYZ* GetArrayItem(struct XYZ* itemArray, int numCols, int row, int col)
{
return &itemArray[row * numCols + col];
}
int main()
{
int A = 5;
int B = 4;
struct XYZ* arr = (struct XYZ*)calloc(A*B, sizeof(struct XYZ));
for (int i = 0; i < A; i++)
{
for (int j = 0; j < B; j++)
{
GetArrayItem(arr, B, i, j)->someValue = 1;
}
}
free(arr);
return 0;
}
With columns of different length, a double pointer might be a viable solution.
struct XYZ
{
int someValue;
};
int main()
{
int i;
int j;
// row count
int A = 5;
// column count per row
int B[] = { 3, 4, 3, 2, 4 };
struct XYZ** arr = (struct XYZ**)calloc(A, sizeof(struct XYZ*));
for (i = 0; i < A; i++)
{
// initialize column for each row
arr[i] = (struct XYZ*)calloc(B[i], sizeof(struct XYZ));
}
for (i = 0; i < A; i++)
{
for (j = 0; j < B[i]; j++)
{
// access items
arr[i][j].someValue = 1;
}
}
for (i = 0; i < A; i++)
{
free(arr[i]);
}
free(arr);
return 0;
}
However, I would advise you to create a more explicit object structure in case where you need 2d data. This makes the design more explicit and the column count per row more transparent.
struct XYZ
{
int someValue;
};
struct MyDomainSpecificRow
{
int numColumns;
struct XYZ* myRowData;
};
int main()
{
int i;
int j;
// row count
int A = 5;
// column count per row
int B[] = { 3, 4, 3, 2, 4 };
// 1d array of rows, each containing 1d array of cells
struct MyDomainSpecificRow* arr = (struct MyDomainSpecificRow*)calloc(A, sizeof(struct MyDomainSpecificRow));
for (i = 0; i < A; i++)
{
// initialize column for each row
arr[i].numColumns = B[i];
arr[i].myRowData = (struct XYZ*)calloc(B[i], sizeof(struct XYZ));
}
for (i = 0; i < A; i++)
{
for (j = 0; j < arr[i].numColumns; j++)
{
// access items
arr[i].myRowData[j].someValue = 1;
}
}
for (i = 0; i < A; i++)
{
free(arr[i].myRowData);
}
free(arr);
return 0;
}
Freaky way of allocating two-dimensional array?
The variable e is a pointer to an array of n + 1 elements of type double.
Using the dereference operator on e gives you the base-type of e which is " array of n + 1 elements of type double".
The malloc call simply takes the base-type of e (explained above) and gets its size, multiplies it by n + 1, and passing that size to the malloc function. Essentially allocating an array of n + 1 arrays of n + 1 elements of double.
C++ How to declare pointer to 2D array
Combining @MadScienceDreams' answer and @Grijesh Chauhan comment, the following seems to work:
double A[1000][1000];
double (*B)[1000][1000] = &A;
And then to access a value:
double a = (*B)[i][j];
How to dynamically allocate the memory for multi dimensional arrays
You have not SegFaulted only by happy accident, and due to the fact that the size of a pointer doesn't change. So where you allocate for int* where you should be allocating for int**, the size of your allocation isn't affected (by happy accident...)
You generally want to avoid becoming a 3-Star Programmer, but sometimes, as in this case, it is what is required. In allocating for any pointer, or pointer-to-pointer, or in this case a pointer-to-pointer-to-pointer, understand there is no "array" involved whatsoever.
When you declare int ***array; you declare a single pointer. The pointer then points to (holds the address of) a block of pointers (type int**) that you allocate. You allocate storage for matricies number of int** pointers as input by the user.
Each matrix is type int**, so you must allocate a block of memory containing rows number of pointer for each matrix.
Finally you allocate cols number of int (type int*) for each and every row in each and every matrix.
So your collection of matricies is an allocated block of pointers with one pointer for each matrix. Then each matrix is an allocate block of pointers with one pointer for every row in that matrix. Finally you allocate a columns worth of int for each an every row pointer for each and every matrix.
Visually your allocation and assignment would resemble the following:
array (int***)
|
+ allocate matricies number of [Pointers]
|
+----------+
| array[0] | allocate rows number of [Pointers] for each matrix
+----------+ assign to each pointer in array block
| array[1] |
+----------+ array[2] (int**)
| array[2] | <======= +-------------+
+----------+ | array[2][0] |
| .... | +-------------+ allocate cols no. of [int]
| array[2][1] | for each allocated row pointer
+-------------+
| array[2][2] | <=== array[2][2] (int*)
+-------------+ +----------------+
| ... | | array[2][2][0] |
+----------------+
| array[2][2][1] |
+----------------+
| array[2][2][2] |
+----------------+
| ... |
In order to always keep the type-size of each allocation correct, simply use the dereferenced pointer to set the type-size. For example when allocating for array (int***) you would use:
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
When allocating for each array[i], you would use:
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
Finally when allocating for each block of int for each row, every array[i][j], you would use:
array[i][row] = malloc (cols * sizeof *array[i][row]);
If you always use the dereference pointer to set type-size, you will never get it wrong.
Following the diagram above through and just taking each allocation in turn (and validating EVERY allocation), you could write your allocation and free routines similar to:
/* use dereferenced pointer for type-size */
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
if (!array) { /* validate EVERY allocation */
perror ("malloc-array");
return 1;
}
for (int i = 0; i < matrix; i++) {
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
if (!array[i]) { /* validate */
perror ("malloc-array[i]");
return 1;
}
for (int row = 0; row < rows; row++) {
/* allocate cols int per-row in each matrix */
array[i][row] = malloc (cols * sizeof *array[i][row]);
if (!array[i][row]) {
perror ("malloc-array[i][row]");
return 1;
}
}
}
The complete example that allocates for the number of matricies with the number of rows and columns entered by the user would be:
#include <stdio.h>
#include <stdlib.h>
int main (void) {
int ***array = NULL,
matrix,
rows,
cols;
fputs ("no. of matricies: ", stdout);
if (scanf ("%d", &matrix) != 1) /* validate EVERY input */
return 1;
fputs ("no. of rows : ", stdout);
if (scanf ("%d", &rows) != 1) /* ditto */
return 1;
fputs ("no. of cols : ", stdout);
if (scanf ("%d", &cols) != 1) /* ditto */
return 1;
/* use dereferenced pointer for type-size */
array = malloc (matrix * sizeof *array); /* allocate matrix int** */
if (!array) { /* validate EVERY allocation */
perror ("malloc-array");
return 1;
}
for (int i = 0; i < matrix; i++) {
array[i] = malloc (rows * sizeof *array[i]); /* array[i] int** pointers */
if (!array[i]) { /* validate */
perror ("malloc-array[i]");
return 1;
}
for (int row = 0; row < rows; row++) {
/* allocate cols int per-row in each matrix */
array[i][row] = malloc (cols * sizeof *array[i][row]);
if (!array[i][row]) {
perror ("malloc-array[i][row]");
return 1;
}
}
}
/* fill matricies with any values */
for (int i = 0; i < matrix; i++)
for (int j = 0; j < rows; j++)
for (int k = 0; k < cols; k++)
array[i][j][k] = j * cols + k + 1;
/* display each matrix and free all memory */
for (int i = 0; i < matrix; i++) {
printf ("\nmatrix[%2d]:\n\n", i);
for (int j = 0; j < rows; j++) {
for (int k = 0; k < cols; k++)
printf (" %2d", array[i][j][k]);
putchar ('\n');
free (array[i][j]); /* free row of int (int*) */
}
free (array[i]); /* free matrix[i] pointers (int**) */
}
free (array); /* free matricies pointers (int***) */
}
(note: you free the memory for each block of int before freeing the memory for the block of row pointers in each matrix before freeing the block of pointers to each matrix)
Example Use/Output
$ ./bin/allocate_p2p2p
no. of matricies: 4
no. of rows : 4
no. of cols : 5
matrix[ 0]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 1]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 2]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 3]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
Memory Use/Error Check
In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.
It is imperative that you use a memory error checking program to ensure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.
For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.
$ valgrind ./bin/allocate_p2p2p
==9367== Memcheck, a memory error detector
==9367== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==9367== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==9367== Command: ./bin/allocate_p2p2p
==9367==
no. of matricies: 4
no. of rows : 4
no. of cols : 5
matrix[ 0]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 1]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 2]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
matrix[ 3]:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
==9367==
==9367== HEAP SUMMARY:
==9367== in use at exit: 0 bytes in 0 blocks
==9367== total heap usage: 23 allocs, 23 frees, 2,528 bytes allocated
==9367==
==9367== All heap blocks were freed -- no leaks are possible
==9367==
==9367== For counts of detected and suppressed errors, rerun with: -v
==9367== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Always confirm that you have freed all memory you have allocated and that there are no memory errors.
Look things over and let me know if you have further questions.
Accessing multi-dimensional arrays in C using pointer notation
here i am thinking of 2D array b as array of 1D arrays
That's the correct way to approach this, because that's indeed what it is. The C standard does not actually specify multi-dimensional arrays as some special case, but they are rather possible because an array is a type like any other. So we can have an array of arrays.
- How is the expression b[i] evaluated in case when b is 2D array?
...
- What does b evaluate to if b is a 2D array?
As for any array, b when used in an expression, decays into a pointer to the first element. b[i] is therefore equivalent to *(b+i), as for any other array expression.
In this case b decays into an array pointer of type int(*)[3].
- How is the expression b[i][j] evaluated in case when b is 2D array?
bis used in an expression, so in this expression it decays into a pointer to the first element, which is an array pointer to the first array.b[i]causes pointer arithmetic to get applied to the array pointer, equivalent to*(b+i). This gives array numberi.- At this position we have a 1D array of type
int[3]. Since this array is part of another array, it has no identifier by itself. But for the sake of illustration, lets pretend it gets a temporary name "tmp". We would then have the expressiontmp[j], which as always decays into*(tmp+j), resulting in anint.
Essentially the whole expression can be treated as *(*(b+i) + j).
- How to access elements of a Multi-dimensional Array in C using pointers.Here i would like to know about how compiler treats a Multi-dimensional Array internally ?
As explained above, it treats it as an array of arrays. For example, you can iterate over a 2D array by using array pointers:
#include <stdio.h>
void print_array (int array[3])
{
printf("%d %d %d\n", array[0], array[1], array[2]);
}
int main (void)
{
int b[2][3]={ {1,2,3},{4,5,6} };
const size_t b_size = sizeof b / sizeof *b;
for(int(*ptr)[3] = b; ptr < b+b_size; ptr++)
{
print_array(*ptr);
}
}
Related Topics
Serial Port (Rs -232) Connection in C++
Class Template for Numeric Types
C++11 Type Trait to Differentiate Between Enum Class and Regular Enum
What's the Difference Between Span and Array_View in the Gsl Library
Check If a Type Is from a Particular Namespace
Why "Universal References" Have the Same Syntax as Rvalue References
Should C++ Programmer Avoid Memset
Generating One Class Member Per Variadic Template Argument
Manual for Cross-Compiling a C++ Application from Linux to Windows
How to Enable /Std:C++17 in VS2017 with Cmake
Deterministic Builds Under Windows