How to access 1D arrays with multiple brackets for readability?

Question

I have a huge code using a 3D array managed with pointers. Something like:

int *** tab;
tab = malloc(m*sizeof(int**));
for(i= 1..n) tab[i] = malloc(n*sizeof(int*));  
... etc...

and later the elements are accessed with:

tab[i][j][k] = ...

But because of specific issues with this structure, I would like to declare tab as a contiguous array instead but still use the syntax with 3 brackets in the code. The compiler will internally replace them like this:

tab[i][j][k] = ...  =>  tab[i*m*n+j*m+k] = ...

So the array is accessed with only one pointer dereference. I'd like not to change the source code (no sed).

For example I could do this by declaring tab in stack:

int tab[n][m][l];

but unfortunately this doesn't work if m and n are runtime variables.

Answer 1

A C++ way is to enclose the 3D array in a class to have a natural accessor:

struct Arr3D
{
    int *arr;
    const int n, m, p; //size of the tab in 3 dimensions

public:
    Arr3D(int n, int m, int l): n(n), m(m), p(l) {
        arr = new int[n * m * p];
    }

    ~Arr3D() {
        delete[] arr;
    }

    int& operator()(int i, int j, int k) {   // read-write accessor
        // optionaly test for 0<=i<n...
        return arr[k + p * (j + i * m)];
    }
};

You create and use an array simply with:

Arr3D * parr = new Arr3D(3,4,5); // dynamic allocation
Arr3D arr(3, 4, 5);              // automatic allocation
...
arr(1,2,3) = 5;
int i = arr(2,0,1);

---

Alternatively, if you want to keep the syntax tab[i][j][k] you can if you use an auxilliary Arr2D class able to provide a view on a 2D array:

struct Arr2D
{
    int *arr;
    const int n, m; //size of the tab in 2 dimensions
    const bool is_view;

public:
    Arr2D(int n, int m): n(n), m(m), is_view(false) {
        arr = new int[n * m];
    }
    Arr2D(int *arr, int n, int m): arr(arr), n(n), m(m), is_view(true) {}

    ~Arr2D() {
        if (! is_view) delete[] arr;
    }

    int * operator[] (int i) {
        return arr + i * m;
    }
};

struct Arr3D
{
    int *arr;
    const int n, m, p; //size of the tab in 3 dimensions

public:
    Arr3D(int n, int m, int l): n(n), m(m), p(l) {
        arr = new int[n * m * p];
    }

    ~Arr3D() {
        delete[] arr;
    }

    Arr2D operator[](int i) {
        return Arr2D(arr + i * p * m, m, p);
    }
};

You can now simply use arr[i][j][k] ...

Answer 2

#define SUB(x,y,z) ((x)*m + (y))*n + (z)

         . . . . .

tab[SUB(i,j,k)] = ....

Answer 3

In C (C99 or C11), the tab array with variable dimensions can be passed as a function parameter as long as its dimensions are also passed in the preceding parameters. Here is an example to show what I mean:

#include <stdio.h>
#include <stdlib.h>

int sum3d(unsigned int dim_n, unsigned int dim_m, unsigned int dim_l,
          int tab[dim_n][dim_m][dim_l])
{
    int total = 0;
    int n, m, l;

    for (n = 0; n < dim_n; n++)
    {
        for (m = 0; m < dim_m; m++)
        {
            for (l = 0; l < dim_l; l++)
            {
                total += tab[n][m][l];
            }
        }
    }
    return total;
}

int main(void)
{
    unsigned int dim_n, dim_m, dim_l;
    unsigned int n, m, l;
    int tot;

    dim_n = 10;
    dim_m = 5;
    dim_l = 4;

    int (*tab)[dim_m][dim_l] = calloc(dim_n, sizeof(*tab));
    if (!tab)
    {
        fprintf(stderr, "Memory allocation failure!\n");
        exit(1);
    }
    for (n = 0; n < dim_n; n++)
    {
        for (m = 0; m < dim_m; m++)
        {
            for (l = 0; l < dim_l; l++)
            {
                tab[n][m][l] = 1;
            }
        }
    }

    printf("total = %d\n", sum3d(dim_n, dim_m, dim_l, tab));
    return 0;
}

In function sum3d, tab could have been declared as int tab[][dim_m][dim_l], or as int (*tab)[dim_m][dim_l], omitting the leftmost dimension in both cases.

Answer 4

You have tagged this as both C and C++, so different solutions are possible.

A C solution would be of the form

#include <stdlib.h>    /*  assumed */

int* tab = malloc(sizeof(int)*n*m*l);

tab[i*m*n+j*m+k] = 42;

free(tab);   /* when done */

This C solution can technically be used in C++ (albeit with an (int *) type conversion to the result of malloc()). However, in C++ this is discouraged in favour of

int* tab = new int[n*m*l];

tab[i*m*n+j*m+k] = 42;

delete [] tab;    // when done

An even better C++ approach is to use the standard library

#include <vector>

std::vector<int> tab(n*m*l);

tab[i*m*n+j*m+k] = 42;

//  tab will be automatically released when it passes from scope.

Of course, all of these will access elements with a single deference. But computing the indices involves a number of multiplications which are not particularly inexpensive operations either. It would be necessary to test to determine which is more efficient/effective.

Answer 5

To achieve this you can first allocate the full "tab"

int* tab = malloc(sizeof(int)* i * j * k);

Which will give you your data. This pointer will serve as the owner of the array.

After that you can create your "3d" array by building up your array of access pointer to the tab variable. Which will result in you having a int*** access; that has all of its internal pointers pointing to the correct portions of tab allowing you to access the tab via access.

this assumes you are sticking to C style code.

If You are looking to do this using a C++ style:

See: What is the most efficient way to initialize a 3D vector?

This post provides a good starting point to doing the same thing using std::vector

Answer 6

For a two-dimensional int array with dimensions n x m, you can do this (in C):

size_t n;
size_t m;
...
// base all sizeof() calls directly on array so it's
// trivial to change the type from int to something else
int **array = malloc( n * sizeof( *array ) );
array[ 0 ] = malloc( n * m * sizeof( **array ) );
size_t rowSize = m * sizeof( **array );
for ( size_t i = 1; ii < m; ii++ )
{
    array[ i ] = array[ i - 1 ] + rowSize;
}

Expanding that to three dimensions is fairly easy (as is adding error checking...)

The real trick is doing everything with a single call to malloc().