为 C 中的 3 维数组分配 space

Question

这个问题已经得到回答 here 但对我来说，有些事情仍然悬而未决，讨论太老了，任何人都无法回复评论，此外我想问一下我的实施有什么问题。

不管怎样，问题设置。我想为维度 3, h, w 的 3D 数组分配 space。我在做什么：

int ***a = (int***)malloc(3 * sizeof(int*));
for (int i = 0; i < 3; i++)
{
   a[i] = (int **) malloc(height * sizeof(int*)); 
}

我理解为先创建space三个3int**然后分配高度int**；然后：

for (int i = 0; i < 3; i++)
{
  a[i][0] = (int *) malloc(height * width * sizeof(int *));
  for (int j = 1; j < height; j++)
   {
     a[i][j] = a[i][j-1] + width;
   }
}

所以现在我认为每个 a[i][0] 基本上是 space 用于大小为高度和宽度的二维数组；此外 j != 0 的 a[i][j] 的其余部分被初始化为 a[i][0] 的 j th 行；

然后我通过以下方式初始化值：

for (int c = 0; c < 3; c++){
  for (int i = 0; i < height; i++){
    for (int j = 0; j < width; j++){
      a[c][i][j] = i+j+c;

然而，这是不正确的。我想通过以下方式将此作为扩展练习来分配二维数组：

int *a[height]; 
a[0] = (int*)malloc(height * width * sizeof(int));
for (int i = 1; i < height; i++){
  a[i] = a[i-1] + widht;
}

这样 a 是一个长度为高度的指针数组，a[0] 分配给整个二维数组，随后的指针指向它们各自的行，我可以通过调用 [=24 简单地写入它们=]

我想做的是将这个2D的想法扩展到3D的案例中，可惜我失败了。

Answer 1

int ***a = (int***)malloc(3 * sizeof(int*));

这没有分配任何有意义的东西。特别是，它不分配 3D 数组，甚至不分配 3D 数组的一部分。它为 3 个整数指针分配 space，这没有任何意义。 int*** 也没有任何意义。

而是分配一个 3D 数组：

int (*a)[y][z] = malloc( sizeof(int[x][y][z]) );

for(int i=0; i<x; i++)
  for(int j=0; j<y; j++)
    for(int k=0; k<z; k++)
      a[i][j][k] = something;

free(a);

编辑（以下文字中的任何讽刺语气都是故意的）

为了拒绝接受任何少于三层间接寻址的解决方案的 three-star 程序员的利益，这里有一个如何正确进行 three-star 编程的示例。

不幸的是，它还不包含 non-conditional 向上分支、内存泄漏或复杂的指针算法。但是对于一个three-star的程序员来说，这种开心的事情当然是后面再补充的小事了。但是，它确实保证数据缓存未命中，因此该程序将运行具有与没有任何数据缓存的系统相同的性能。

也可以考虑将分配的pointer-to-pointer-to-pointer作为参数传递，从而达到4星！！！

[如 pointer-to-pointer 方法是非常糟糕的做法，但如果您出于未知原因坚持使用它，您不妨正确使用它。]

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


void free_int_3d (int*** ppp, size_t X, size_t Y, size_t Z)
{
  (void)Z;

  if(ppp == NULL)
  {
    return ;
  }

  for(size_t x=0; x < X; x++)
  {
    if(ppp[x] != NULL)
    {
      for(size_t y=0; y < Y; y++)
      {
        if(ppp[x][y] != NULL)
        {
          free(ppp[x][y]);
        }
      }
      free(ppp[x]);
    }
  }
  free(ppp);
}


#define malloc_with_cleanup(ptr, size)     \
ptr = malloc(size);                        \
if(ptr == NULL)                            \
{                                          \
  free_int_3d(result, X, Y, Z);            \
  return NULL;                             \
}

int*** int_alloc_3d (size_t X, size_t Y, size_t Z)
{
  int*** result = NULL;

  malloc_with_cleanup(result, sizeof(int**[X]));
  for(size_t x=0; x<X; x++)
  {
    malloc_with_cleanup(result[x], sizeof(int*[Y]));
    for(size_t y=0; y<Y; y++)
    {
      malloc_with_cleanup(result[x][y], sizeof(int[Z]));
    }
  }
  return result;
}


int main (void)
{
  const size_t X = 5;
  const size_t Y = 3;
  const size_t Z = 4;

  int*** ppp = int_alloc_3d(X, Y, Z);

  for(size_t i=0; i<X; i++)
  {
    for(size_t j=0; j<Y; j++)
    {
      for(size_t k=0; k<Z; k++)
      {
        ppp[i][j][k] = (int)k;
        printf("%d ", ppp[i][j][k]);
      }
      printf("\n");
    }
    printf("\n");
  }

  free_int_3d(ppp, X, Y, Z);

  return 0;
}

输出：

Answer 2

为了解决 OP 的更高目标，我怀疑指向二维数组的指针就足够了

int (*a)[height][width] = malloc(sizeof *a * 3);

 a[c][i][j] = i + j + c;

但根据 OP 的要求....

... to allocate space for a 3D array ...

代码通常如何创建 3D 数组？
下面的代码使用 C99 中可用的 可变长度数组 来实现。
（C11 可选支持 VLA）

int a1[3][height][width];
// and assign it accordingly
for (int c = 0; c < 3; c++) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      a1[c][i][j] = i + j + c;

然而 OP 想要 allocate space 这样的数组。

malloc()returns一个指针。指向已分配内存的指针。所以我们需要创建一个指向这样一个数组的指针。一旦我们这样做了，分配和元素分配就很容易了。

int (*a2)[3][height][width] = malloc(sizeof *a2);

// 3 nested for loop as above
    (*a2)[c][i][j] = i + j + c;

示例代码

void VT_3_dimensional_array(int height, int width) {
  assert(height > 0 && width > 0);

  int (*a2)[3][height][width] = malloc(sizeof *a2);
  printf("%p %zu\n", (void*) a2, sizeof *a2);
  if (a2 == NULL) {
    perror("Out of memory");
    exit(EXIT_FAILURE);
  }
  for (int c = 0; c < 3; c++) {
    for (int i = 0; i < height; i++) {
      for (int j = 0; j < width; j++) {
        (*a2)[c][i][j] = i + j + c;
      }
    }
  }

  // use a;
  for (int c = 0; c < 3; c++) {
    for (int i = 0; i < height; i++) {
      putchar('(');
      for (int j = 0; j < width; j++) {
        printf(" %X", (*a2)[c][i][j]);
      }
      putchar(')');
    }
    puts("");
  }

  free(a2);
}

int main() {
  VT_3_dimensional_array(5, 7);
  return 0;
}

输出

0x80071980 420
( 0 1 2 3 4 5 6)( 1 2 3 4 5 6 7)( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)
( 1 2 3 4 5 6 7)( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)( 5 6 7 8 9 A B)
( 2 3 4 5 6 7 8)( 3 4 5 6 7 8 9)( 4 5 6 7 8 9 A)( 5 6 7 8 9 A B)( 6 7 8 9 A B C)

请注意，从技术上讲，OP 的代码使用了错误的尺寸。通常 sizeof(int*) 将与 sizeof(int**) 相同，所以没有什么大不了的。然而，它确实表明对分配的混淆。

// wrong type  -----------------------v  should be int**
int ***a = (int***)malloc(3 * sizeof(int*));

Answer 3

让我们先想象一下您要尝试做什么，然后我将展示实现目标的代码：

  int ***         int **                int *                  int 

  +---+           +---+                 +---+                  +---+
a |   | ---> a[0] |   | ------> a[0][0] |   | ----> a[0][0][0] |   |
  +---+           +---+                 +---+                  +---+
             a[1] |   | ----+   a[0][1] |   | -+    a[0][0][1] |   |
                  +---+     |           +---+  |               +---+
             a[2] |   |     |            ...   |                ...
                  +---+     |           +---+  |               +---+
                            | a[0][h-1] |   |  |  a[0][0][w-1] |   | 
                            |           +---+  |               +---+
                            |                  |
                            |           +---+  |               +---+
                            +-> a[1][0] |   |  +--> a[0][1][0] |   |
                                        +---+                  +---+
                                a[1][1] |   |       a[0][1][1] |   |
                                        +---+                  +---+
                                         ...                    ...
                                        +---+                  +---+
                              a[1][h-1] |   |     a[0][1][w-1] |   |
                                        +---+                  +---+

类型：

每个 a[i][j][k] 都有类型 int;
每个 a[i][j] 指向 int 个对象序列的第一个元素，因此它的类型必须是 int *;
每个 a[i] 指向 int * 对象序列的第一个元素，因此它的类型必须是 int **;
a 指向 int ** 个对象序列的第一个元素，因此它的类型必须是 int ***.

因为你正在做一个零碎的嵌套分配，你需要检查每个 malloc 调用的结果，如果有错误，你会想要在退出之前清理所有以前分配的内存，否则你有内存泄漏的风险。不幸的是，没有真正干净或优雅的方法来做到这一点——你要么随身携带一个标志并做一堆额外的测试，要么你扔几个 gotos。我将展示两种不同的方法，但都不是那么漂亮。

第一种方法 - 当我们分配每个 a[i] 时，我们也分配每个 a[i][j]（一种 "depth-first" 方法）并初始化每个 a[i][j][k]。如果 a[i][j] 上的分配失败，我们必须解除分配所有 a[i][0] 到 a[i][j-1]，然后解除分配 a[i]，然后对 a[0] 到 a[i-1]:

/**
 * Depth-first approach: allocate each a[i][j] with each a[i]
 */
int ***alloc1( size_t pages, size_t height, size_t width )
{
  size_t i, j, k;

  int ***a = malloc( sizeof *a * pages ); // allocate space for N int **
                                          // objects, where N == pages

  if ( !a )
    return NULL;

  for ( i = 0; i < pages; i++ )
  {
    a[i] = malloc( sizeof *a[i] * height );  // for each a[i], allocate space for
    if ( !a[i] )                             // N int * objects, where N == height
      goto cleanup_1;

    for ( j = 0; j < height; j++ )
    {
      a[i][j] = malloc( sizeof *a[i][j] * width ); // for each a[i][j], allocate      
      if ( !a[i][j] )                              // space for N int objects,
        goto cleanup_2;                            // where N == w

      for ( k = 0; k < width; k++ )
        a[i][j][k] = initial_value( i, j, k );
    }
  }
  goto done;

/**
 * Free all of a[i][0] through a[i][j-1], then free a[i]
 */
cleanup_2:
  while ( j-- )
    free( a[i][j] );
  free( a[i] );

/**
 * Free all of a[0] through a[i-1], then free a
 */
cleanup_1:
  while ( i-- )
  {
    j = height;
    goto cleanup_2;
  }
  free( a );
  a = NULL;

done:
  return a;  // at this point, a is either a valid pointer or NULL.
}

是的，这段代码包含 goto，它违反了我的一条规则（永远不要向后分支）。但是，分配代码和清理代码之间有相当清晰的分离，我们不会在清理部分重复。 cleanup_2 释放页面中的所有行，以及页面本身； cleanup_1 释放所有页面。 cleanup_2 "falls through" 变成 cleanup_1。

这是第二种方法 - 首先我们在分配任何 a[i][j] 之前分配 all a[i]，然后我们确保所有 a[i][j] 都成功在初始化数组内容之前分配。

/**
 * Breadth-first approach; allocate all a[i], then all a[i][j], then initialize
 */
int ***alloc2( size_t pages, size_t height, size_t width )
{
  size_t i, j, k;

  /**
   * Allocate space for N int ** objects, where N == pages
   */
  int ***a = malloc( sizeof *a * pages );

  if ( !a )
    return NULL;                        // allocation failed for initial sequence, return NULL

  for ( i = 0; i < pages; i++ )  // For each a[i], allocate N objects of type
  {                              // int *, where N == height
    a[i] = malloc( sizeof *a[i] * height );
    if ( !a[i] )
      break;
  }

  if ( i < pages )
  {
    while ( i-- )                       // allocation of a[i] failed, free up a[0] through a[i-1]
      free( a[i] );
    free( a );                          // free a
    return NULL;
  }

  for ( i = 0; i < pages; i++ )    
  {
    for ( j = 0; j < height; j++ )
    {
      a[i][j] = malloc( sizeof *a[i][j] * width ); // for each a[i][j], allocate    
      if ( !a[i][j] )                             // space for N int objects, 
        break;                                    // where N == width
    }
  }

  if ( j < h )
  {
    do
    {
      while ( j-- )                     // allocation of a[i][j] failed, free up a[i][0] through a[i][j-1]
        free( a[i][j] );                // repeat for all of a[0] through a[i-1].
      free( a[i] );
      j = h;
    } while ( i-- );
    free( a );                          // free a
    return NULL;
  }

  /**
   * All allocations were successful, initialize array contents
   */    
  for ( i = 0; i < pages; i++ )
    for ( j = 0; j < height; j++ )
      for ( k = 0; k < width; k++ )
        a[i][j][k] = initial_value( i, j, k );

  return a;
}

没有gotos！但是代码并没有 "flow" 以及 IMO。分配和清理代码之间没有那么清晰的分离，并且清理部分之间有一点重复。

请注意，对于这两种方法，内存不是连续的 - 紧跟在 a[0][0][h-1] 之后的元素不会是 a[0][1][0]。如果您需要所有数组元素在内存中相邻，您将需要使用其他人显示的方法：

int (*a)[h][w] = malloc( sizeof *a * 3 );

需要注意的是，如果 h 和 w 很大，您可能没有足够的连续分配内存来满足请求。

为 C 中的 3 维数组分配 space

Allocate space for a 3 dimensional array in C

c

arrays

pointers

dynamic-memory-allocation