Three dimensional arrays of integers in C++

Question

Hi,

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.

Any feedback or suggestions greatly appreciated.

Thanks in anticipation.

Andy

Answer 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++;
      }
    }
  }
}

Answer 2

If z is "known and equals 4" then just use a 2D array instead. Additionally, if you have a sparse matrix, there are techniques for significantly reducing storage size at a minor expense of speed. As far as allocation, if you hope to use the bracket shorthand [x][y][z] you will need to allocate it in one contiguous memory section with something like malloc();

Answer 3

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;

Answer 4

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.

Answer 5

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)

Answer 6

Many thanks for the quick replies. Zoobas/Pieters suggestions work just fine.

ChrisN the boost libraries look interesting and I will definitely probe further.

Best regards

Andy

Answer 7

There are many advantages to using the STL to manage your memory over using new/delete. The choice of how to represent your data depends on how you plan to use it. One suggestion would be a class that hides the implementation decision and provides three dimensional get/set methods to a one dimensional STL vector.

If you really believe you need to create a custom 3d vector type, investigate Boost first.

// a class that does something in 3 dimensions

class MySimpleClass
{
public:

  MySimpleClass(const size_t inWidth, const size_t inHeight, const size_t inDepth) :
   mWidth(inWidth), mHeight(inHeight), mDepth(inDepth)
   {
       mArray.resize(mWidth * mHeight * mDepth);
   }


  // inline for speed
  int Get(const size_t inX, const size_t inY, const size_t inZ) {
     return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX];
  }

  void Set(const size_t inX, const size_t inY, const size_t inZ, const int inVal) {
     return mArray[(inZ * mWidth * mHeight) + (mY * mWidth) + mX];
  }

  // doing something uniform with the data is easier if it's not a vector of vectors
  void DoSomething()
  {
     std::transform(mArray.begin(), mArray.end(), mArray.begin(), MyUnaryFunc);
  }

private:

  // dimensions of data
  size_t mWidth;
  size_t mHeight;
  size_t mDepth;

  // data buffer
  std::vector< int > mArray;
};

Answer 8

Pieter's suggestion is good of course, but one thing you've to bear in mind is that in case of big arrays building it may be quite slow. Every time vector capacity changes, all the data has to be copied around ('n' vectors of vectors).