Three dimensional arrays of integers in C++

Question

I would like to find out safe ways of implementing three dimensional arrays of integers in C++, using pointer arithmetic / dynamic memory allocation, or, alternatively using STL techniques such as vectors.

Essentially I want my integer array dimensions to look like:

[ x ][ y ][ z ]

x and y are in the range 20-6000 z is known and equals 4.

Solution 1

Have a look at the Boost multi-dimensional array library. Here's an example (adapted from the Boost documentation):

#include "boost/multi_array.hpp"

int main() {
  // Create a 3D array that is 20 x 30 x 4
  int x = 20;
  int y = 30;
  int z = 4;

  typedef boost::multi_array<int, 3> array_type;
  typedef array_type::index index;
  array_type my_array(boost::extents[x][y][z]);

  // Assign values to the elements
  int values = 0;
  for (index i = 0; i != x; ++i) {
    for (index j = 0; j != y; ++j) {
      for (index k = 0; k != z; ++k) {
        my_array[i][j][k] = values++;
      }
    }
  }
}

Solution 2

Each pair of square brackets is a dereferencing operation (when applied to a pointer). As an example, the following pairs of lines of code are equivalent:

x = myArray[4];
x = *(myArray+4);

 

x = myArray[2][7];
x = *((*(myArray+2))+7);

To use your suggested syntax you are simply dereferencing the value returned from the first dereference.

int*** myArray = (some allocation method, keep reading);
//
// All in one line:
int   value = myArray[x][y][z];
//
// Separated to multiple steps:
int** deref1 = myArray[x];
int*  deref2 = deref1[y];
int   value = deref2[z];

To go about allocating this array, you simply need to recognise that you don't actually have a three-dimensional array of integers. You have an array of arrays of arrays of integers.

// Start by allocating an array for array of arrays
int*** myArray = new int**[X_MAXIMUM];

// Allocate an array for each element of the first array
for(int x = 0; x < X_MAXIMUM; ++x)
{
    myArray[x] = new int*[Y_MAXIMUM];

    // Allocate an array of integers for each element of this array
    for(int y = 0; y < Y_MAXIMUM; ++y)
    {
        myArray[x][y] = new int[Z_MAXIMUM];

        // Specify an initial value (if desired)
        for(int z = 0; z < Z_MAXIMUM; ++z)
        {
            myArray[x][y][z] = -1;
        }
    }
}

Deallocating this array follows a similar process to allocating it:

for(int x = 0; x < X_MAXIMUM; ++x)
{
    for(int y = 0; y < Y_MAXIMUM; ++y)
    {
        delete[] myArray[x][y];
    }

    delete[] myArray[x];
}

delete[] myArray;

Solution 3

Below is a straightforward way to create 3D arrays using C or C++ in one chunk of memory for each array. No need to use BOOST (even if it's nice), or to split allocation between lines with multiple indirection (this is quite bad as it usually gives big performance penalty when accessing data and it fragments memory).

The only thing to understand is that there is no such thing as multidimensional arrays, just arrays of arrays (of arrays). The innermost index being the farthest in memory.

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

int main(){

    {
        // C Style Static 3D Arrays
        int a[10][20][30];
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
    }

    {
        // C Style dynamic 3D Arrays
        int (*a)[20][30];
        a = (int (*)[20][30])malloc(10*20*30*sizeof(int));
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
        free(a);
    }

    {
        // C++ Style dynamic 3D Arrays
        int (*a)[20][30];
        a = new int[10][20][30];
        a[9][19][29] = 10;
        printf("a[9][19][29]=%d\n", a[9][19][29]);
        delete [] a;
    }

}

For your actual problem, as there potentially is two unknown dimensions, there is a problem with my proposal at it allow only one unknown dimension. There is several ways to manage that.

The good news is that using variables now works with C, it is called variable length arrays. You look here for details.

    int x = 100;
    int y = 200;
    int z = 30;

    {
        // C Style Static 3D Arrays 
        int a[x][y][z];
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
    }

    {
        // C Style dynamic 3D Arrays
        int (*a)[y][z];
        a = (int (*)[y][z])malloc(x*y*z*sizeof(int));
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
        free(a);
    }

If using C++ the simplest way is probably to use operator overloading to stick with array syntax:

    {
        class ThreeDArray {
            class InnerTwoDArray {
                int * data;
                size_t y;
                size_t z;
                public:
                InnerTwoDArray(int * data, size_t y, size_t z)
                    : data(data), y(y), z(z) {}

                public:
                int * operator [](size_t y){ return data + y*z; }
            };

            int * data;
            size_t x;
            size_t y;
            size_t z;
            public:
            ThreeDArray(size_t x, size_t y, size_t z) : x(x), y(y), z(z) {
                data = (int*)malloc(x*y*z*sizeof data);
            }

            ~ThreeDArray(){ free(data); }

            InnerTwoDArray operator [](size_t x){
                return InnerTwoDArray(data + x*y*z, y, z);
            }
        };

        ThreeDArray a(x, y, z);
        a[99][199][29] = 10;
        printf("a[99][199][29]=%d\n", a[99][199][29]);
    }

The above code has some indirection cost for accessing InnerTwoDArray (but a good compiler can probably optimize it away) but uses only one memory chunk for array allocated on heap. Which is usually the most efficient choice.

Obviously even if the above code is still simple and straightforward, STL or BOOST does it well, hence no need to reinvent the wheel. I still believe it is interesting to know it can be easily done.

Solution 4

With vectors:

std::vector< std::vector< std::vector< int > > > array3d;

Every element is accessible wit array3d[x][y][z] if the element was already added. (e.g. via push_back)

Solution 5

It should be noted that, for all intents and purposes, you are dealing with only a 2D array, because the third (and least significant) dimension is known.

Using the STL or Boost are quite good approaches if you don't know beforehand how many entries you will have in each dimension of the array, because they will give you dynamic memory allocation, and I recommend either of these approaches if your data set is to remain largely static, or if it to mostly only receive new entries and not many deletions.

However, if you know something about your dataset beforehand, such as roughly how many items in total will be stored, or if the arrays are to be sparsely populated, you might be better off using some kind of hash/bucket function, and use the XYZ indices as your key. In this case, assuming no more than 8192 (13 bits) entries per dimension, you could get by with a 40-bit (5-byte) key. Or, assuming there are always 4 x Z entries, you would simply use a 26-bit XY key. This is one of the more efficient trade-offs between speed, memory usage, and dynamic allocation.

View more solutions

Comments

[kriss]

yes, you can do that, but you can also do it in one memory chunk and only one allocation. It's also usually much faster to use one memory chunk that many small ones, memory indirection has a price. The method you show is mostly usefull for sparse matrixes when full inner arrays are not used and you can completely avoid to allocate them.

[jcopenha]

@kriss I agree completely, and I personally tend to use single arrays (allocated by page for big stuff). The reason I set it up this way here is for the syntax requested (as I noted). The performance difference for access is trivial, though for a big enough array and known cache behaviour I can certainly create degenerate use cases (for both), and the performance for initialisation is irrelevant (if it matters, you're initialising it in the wrong place - do it earlier).

[kriss]

you also can easily do it with the syntax asked for poster in one memory chunk. I posted an answer showing (one way, there is many) how to do just that using C++, and variable length arrays are now a feature of C99 (too bad it didn't got his way to C++). I will +1 your answer anyway as it works fine.