C++ 中的三维整数数组

Three dimensional arrays of integers in C++

提问by AndyUK

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 STLtechniques such as vectors.

我想找出在 C++ 中实现三维整数数组的安全方法，使用指针算术/动态内存分配，或者使用STL向量等技术。

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.

x 和 y 在 20-6000 范围内 z 已知且等于 4。

回答by ChrisN

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

看看 Boost多维数组库。这是一个示例（改编自 Boost 文档）：

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

回答by kriss

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).

下面是在每个数组的一块内存中使用 C 或 C++ 创建 3D 数组的直接方法。不需要使用 BOOST（即使它很好），也不需要在具有多个间接的行之间分割分配（这很糟糕，因为它通常在访问数据时会带来很大的性能损失，并且会碎片化内存）。

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 herefor details.

好消息是现在可以在 C 中使用变量，它被称为可变长度数组。你看这里了解详情。

    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:

如果使用 C++，最简单的方法可能是使用运算符重载来坚持数组语法：

    {
        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.

上面的代码有一些访问 InnerTwoDArray 的间接成本（但一个好的编译器可能会优化它）但只使用一个内存块来分配在堆上的数组。这通常是最有效的选择。

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.

显然，即使上面的代码仍然简单明了，STL 或 BOOST 做得很好，因此无需重新发明轮子。我仍然相信知道它可以轻松完成很有趣。

回答by Zooba

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.

要分配这个数组，您只需要认识到您实际上并没有一个由整数组成的 3 维数组。你有一个由整数数组组成的数组。

// 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;

回答by Pieter

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)

如果元素已经添加，每个元素都可以通过 array3d[x][y][z] 访问。（例如通过 push_back）

回答by Paul Troon

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.

与使用 new/delete 相比，使用 STL 管理内存有很多优点。选择如何表示您的数据取决于您计划如何使用它。一个建议是一个隐藏实现决策的类，并为一维 STL 向量提供三维获取/设置方法。

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

如果您确实认为需要创建自定义 3d 矢量类型，请先研究 Boost。

// 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;
};

回答by Mark Webster

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.

应该注意的是，出于所有意图和目的，您只处理一个 2D 数组，因为第三个（也是最不重要的）维度是已知的。

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.

如果您事先不知道数组的每个维度中将有多少条目，使用 STL 或 Boost 是非常好的方法，因为它们将为您提供动态内存分配，如果您的数据集是，我推荐这两种方法中的任何一种保持基本静态，或者如果它主要只接收新条目而不是很多删除。

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.

但是，如果您事先对数据集有所了解，例如总共将存储多少项，或者如果数组要稀疏填充，则最好使用某种散列/存储桶函数，并使用XYZ 指数作为您的关键。在这种情况下，假设每个维度不超过 8192（13 位）条目，您可以使用 40 位（5 字节）密钥。或者，假设总是有 4 x Z 条目，您只需使用 26 位 XY 密钥。这是速度、内存使用和动态分配之间更有效的权衡之一。

回答by yrp

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).

Pieter 的建议当然很好，但您必须记住的一件事是，在构建大型阵列的情况下，它可能会很慢。每次向量容量发生变化时，都必须复制所有数据（'n' 个向量的向量）。