How do I work with dynamic multi-dimensional arrays in C?
With dynamic allocation, using malloc:
int** x;
x = malloc(dimension1_max * sizeof(*x));
for (int i = 0; i < dimension1_max; i++) {
x[i] = malloc(dimension2_max * sizeof(x[0]));
}
//Writing values
x[0..(dimension1_max-1)][0..(dimension2_max-1)] = Value;
[...]
for (int i = 0; i < dimension1_max; i++) {
free(x[i]);
}
free(x);
This allocates an 2D array of size dimension1_max * dimension2_max. So, for example, if you want a 640*480 array (f.e. pixels of an image), use dimension1_max = 640, dimension2_max = 480. You can then access the array using x[d1][d2] where d1 = 0..639, d2 = 0..479.
But a search on SO or Google also reveals other possibilities, for example in this SO question
Note that your array won't allocate a contiguous region of memory (640*480 bytes) in that case which could give problems with functions that assume this. So to get the array satisfy the condition, replace the malloc block above with this:
int** x;
int* temp;
x = malloc(dimension1_max * sizeof(*x));
temp = malloc(dimension1_max * dimension2_max * sizeof(x[0]));
for (int i = 0; i < dimension1_max; i++) {
x[i] = temp + (i * dimension2_max);
}
[...]
free(temp);
free(x);
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;
}
Create a multidimensional array dynamically in C++
In general, nesting std::vector is not a great idea. It's usually a better plan to allocate memory which will hold the entirety of your multidimensonal array as a contiguous block, and then index into it as if it were multidimensional. This memory block could be allocated via new, but unless you need some precise control over how it's allocated (custom allocator), I'd recommend sticking with a single std::vector.
It's not difficult to create a class to manage such a resource in which the number of dimensions can be set dynamically. A good way to organize such a class is to keep track of the allocated memory, the sizes of each dimension, and the stride pattern for each dimension. The strides describe how many elements must be incremented over in order to reach the next element along a given dimension.
This allows efficient indexing (just pointer arithmetic), as well as very efficient reshaping: as long as the number of elements doesn't change, this just requires changing the shape and stride arrays.
Example:
Here's a very basic class which will store such a dynamical multidimensional array of doubles. It stores data in row-major order, meaning that the last index varies the fastest. So for a 2D array, the first row is stored contiguously, followed by the second row, and so on.
You can reshape the array, changing the number of dimensions, if you want. A basic element access operator[] is shown, too. There's nothing else fancy about the class, but you can extend it to provide whatever functionality you want, e.g., iterators, mathematical operations on the data, I/O operators, etc.
/*! \file dynamic_array.h
* Basic dynamic multi-dimensional array of doubles.
*/
#ifndef DYNAMIC_ARRAY_H
#define DYNAMIC_ARRAY_H
#include <vector>
#include <numeric>
#include <functional>
class
dynamic_array
{
public:
dynamic_array(const std::vector<int>& shape)
: m_nelem(std::accumulate(shape.begin(), shape.end(),
1, std::multiplies<int>()))
, m_ndim(shape.size())
, m_shape(shape)
{
compute_strides();
m_data.resize(m_nelem, 0.0);
}
~dynamic_array()
{
}
const double& operator[](int i) const
{
return m_data.at(i);
}
double& operator[](int i)
{
return m_data.at(i);
}
const double& operator[](const std::vector<int>& indices) const
{
auto flat_index = std::inner_product(
indices.begin(), indices.end(),
m_strides.begin(), 0);
return m_data.at(flat_index);
}
double& operator[](const std::vector<int>& indices)
{
auto flat_index = std::inner_product(
indices.begin(), indices.end(),
m_strides.begin(), 0);
return m_data.at(flat_index);
}
void reshape(const std::vector<int>& new_shape)
{
auto new_nelem = std::accumulate(
new_shape.begin(), new_shape.end(),
1, std::multiplies<int>());
if (new_nelem != m_nelem) {
throw std::invalid_argument("dynamic_array::reshape(): "
"number of elements must not change.");
}
m_nelem = new_nelem;
m_ndim = new_shape.size();
m_shape = new_shape;
compute_strides();
}
const std::vector<int>& shape() const
{
return m_shape;
}
const std::vector<int>& strides() const
{
return m_strides;
}
int ndim() const
{
return m_ndim;
}
int nelem() const
{
return m_nelem;
}
private:
int m_ndim;
int m_nelem;
std::vector<int> m_shape;
std::vector<int> m_strides;
std::vector<double> m_data;
void compute_strides()
{
m_strides.resize(m_ndim);
m_strides.at(m_ndim - 1) = 1;
std::partial_sum(m_shape.rbegin(),
m_shape.rend() - 1,
m_strides.rbegin() + 1,
std::multiplies<int>());
}
};
#endif // include guard
Here's a basic demo of the functionality.
/*! \file test.cc
* Basic test of the dynamic_array class.
*/
#include "dynamic_array.h"
#include <iostream>
int main(int /* argc */, const char * /* argv */[])
{
dynamic_array arr({2, 3});
std::cout << "Shape: { ";
for (auto& each : arr.shape())
std::cout << each << " ";
std::cout << "}" << std::endl;
std::cout << "Strides: { ";
for (auto& each : arr.strides())
std::cout << each << " ";
std::cout << "}" << std::endl;
// Reshape array, changing number of dimensions, but
// keeping number of elements constant.
arr.reshape({6});
std::cout << "Shape: { ";
for (auto& each : arr.shape())
std::cout << each << " ";
std::cout << "}" << std::endl;
// Verify that the stride pattern has now also changed.
std::cout << "Strides: { ";
for (auto& each : arr.strides())
std::cout << each << " ";
std::cout << "}" << std::endl;
return 0;
}
You can compile the test program with g++ -std=c++14 -o test test.cc, assuming the file defining the class is in the same directory as test.cc.
How do I declare a 2d array in C++ using new?
If your row length is a compile time constant, C++11 allows
auto arr2d = new int [nrows][CONSTANT];
See this answer. Compilers like gcc that allow variable-length arrays as an extension to C++ can use new as shown here to get fully runtime-variable array dimension functionality like C99 allows, but portable ISO C++ is limited to only the first dimension being variable.
Another efficient option is to do the 2d indexing manually into a big 1d array, as another answer shows, allowing the same compiler optimizations as a real 2D array (e.g. proving or checking that arrays don't alias each other / overlap).
Otherwise, you can use an array of pointers to arrays to allow 2D syntax like contiguous 2D arrays, even though it's not an efficient single large allocation. You can initialize it using a loop, like this:
int** a = new int*[rowCount];
for(int i = 0; i < rowCount; ++i)
a[i] = new int[colCount];
The above, for colCount= 5 and rowCount = 4, would produce the following:
Don't forget to delete each row separately with a loop, before deleting the array of pointers. Example in another answer.
How are multi-dimensional arrays formatted in memory?
A static two-dimensional array looks like an array of arrays - it's just laid out contiguously in memory. Arrays are not the same thing as pointers, but because you can often use them pretty much interchangeably it can get confusing sometimes. The compiler keeps track properly, though, which makes everything line up nicely. You do have to be careful with static 2D arrays like you mention, since if you try to pass one to a function taking an int ** parameter, bad things are going to happen. Here's a quick example:
int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};
In memory looks like this:
0 1 2 3 4 5
exactly the same as:
int array2[6] = { 0, 1, 2, 3, 4, 5 };
But if you try to pass array1 to this function:
void function1(int **a);
you'll get a warning (and the app will fail to access the array correctly):
warning: passing argument 1 of ‘function1’ from incompatible pointer type
Because a 2D array is not the same as int **. The automatic decaying of an array into a pointer only goes "one level deep" so to speak. You need to declare the function as:
void function2(int a[][2]);
or
void function2(int a[3][2]);
To make everything happy.
This same concept extends to n-dimensional arrays. Taking advantage of this kind of funny business in your application generally only makes it harder to understand, though. So be careful out there.
Do multi-dimensional arrays cause any problems in C and/or C++?
You cannot answer this question for C and C++ at once, because there is a fundamental difference between these two languages and their handling of multidimensional arrays. So this answer contains two parts:
C++
Multidimensional arrays are pretty useless in C++ because you cannot allocate them with dynamic sizes. The sizes of all dimensions except the outermost one must be compile time constants. In virtually all the usecases for multidimensional arrays I have encountered, the size parameters are simply not known at compile time. Because they come from the dimensions of an image file, or some simulation parameter, etc.
There might be some special cases where the dimensions are actually known at compile time, and in these cases, there is no issue with using multidimensional arrays in C++. In all the other cases, you'll need to either use pointer arrays (tedious to set up), nested std::vector<std::vector<std::vector<...>>>, or a 1D array with manual index computation (error prone).
C
C allows for true multidimensional arrays with dynamic sizes since C99. This is called VLA, and it allows you to create fully dynamically sized multidimensional arrays both on the stack and the heap.
However, there are two catches:
You can pass a multidimensional VLA to a function, but you can't return it. If you want to pass multidimensional data out of a function, you must return it by reference.
void foo(int width, int height, int (*data)[width]); //works
//int (*bar(int width, int height))[width]; //does not workYou can have pointers to multidimensional arrays in variables, and you can pass them to functions, but you cannot store them in structs.
struct foo {
int width, height;
//int (*data)[width]; //does not work
};
Both problems can be worked around (pass by reference to return a multidimensional array, and storing the pointer as a void* in the struct), but it's not trivial. And since its not a heavily used feature, only very few people know how to do it right.
Compile time array sizes
Both C and C++ allow you to use multidimensional arrays with dimensions known at compile time. These do not have the drawbacks listed above.
But their usefulness is reduced greatly: There are just so many cases where you would want to use a multidimensional array, and where you do not have the ghost of a chance to know the involved sizes at compile time. An example is image processing: You don't know the dimensions of the image before you have opened the image file. Likewise with any physics simulation: You do not know how large your working domain is until your program has loaded its configuration files. Etc.
So, in order to be useful, multidimensional arrays must support dynamic sizes imho.
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:
Related Topics
C and C++ Programming on Ubuntu 11.10
Do Class/Struct Members Always Get Created in Memory in the Order They Were Declared
Vector of Const Objects Giving Compile Error
How to Detect/Avoid Memory Leaks in Your (Unmanaged) Code
How to Properly Link Libraries with Cmake
Declare Abstract Signal in Interface Class
Why/When Is _Declspec( Dllimport ) Not Needed
Properly Print Utf8 Characters in Windows Console
"The System Cannot Find the File Specified" When Running C++ Program
Why Doesn't Narrowing Conversion Used with Curly-Brace-Delimited Initializer Cause an Error
Std::String::C_Str() and Temporaries
Which Headers in the C++ Standard Library Are Guaranteed to Include Another Header
What Does the Operation C=A+++B Mean
What Is the Point of a Private Pure Virtual Function
Initialize Parent's Protected Members with Initialization List (C++)
Why Is It Undefined Behavior to Delete[] an Array of Derived Objects via a Base Pointer
Difference in Performance Between Msvc and Gcc for Highly Optimized Matrix Multplication Code
Sendinput() Not Equal to Pressing Key Manually on Keyboard in C++