介绍

像许多其他编程语言一样，C支持多维阵列（矩阵）。但是，它对它使用了非常规的语法：

int a2d[3][3];  // not: a2d[3,3]

也就是说，我们将每个维度放在其自己的[]对中。从概念上讲，将2D矩阵视为数组数组。在引擎盖下，记忆是（总是）一维的。为了实现二维阵列的syntactic sugar，编译器实际上是这样做的：

int *const a1d = &a2d[0][0];

a2d[i][j] = 0;  // really: a1d[ i * 3 + j ]

是在C中，所有元素都是连续分配的，以使a2d[i][0]和a2d[i][1]在给定的行 i 的内存中相邻：：

（这被称为row-major order。）鉴于，编译器可以通过将 i 乘以行的长度来计算a2d[i][j]的地址（在这种情况下为3），然后添加 j 所有由sizeof(T)缩放为t是元素类型。

这一切都可以很好地适用于静态分配的2D矩阵，其中尺寸在编译时已知，但是如果我们不知道编译时的尺寸怎么办？然后，我们必须动态分配它。但是C所拥有的只是malloc()，它只是分配给定的字节数。我们如何分配正确数量的字节和使[][]语法仍然有效？

C中的数组和指针

在阵列和指针方面，C有几个古怪的特征：

1. 表达式中的数组的名称衰减到指向其第一个元素的指针中。例如：
   

   int a1d[3];
   int *p = a1d;  // as if: p = &a1d[0]
   

   也就是说，a1d的名称是&a1d[0]的速记。

2. 数组的a1d[i]语法只是*(a1d+i)的句法糖。也就是说，以a1d（这是其第一个元素的地址），将sizeof i 元素添加到该地址，然后返回 element。 >

3. 对于任何指针p等效地，*p也可以写为p[0]。这种等效性允许动态分配一个维数数组和具有[]语法仍然有效：
   

   int *p3 = malloc( 3 * sizeof(int) );
   // ...
   p3[i] = 42;    // as if: *(p3 + i) = 42;
   

   这种等价是对新B（C的前体）如何指定指针的残余。参见The Development of the C Language，Dennis M. Ritchie，1993年4月。

这些古怪的功能允许通过动态分配的多维数组和具有[][]语法仍然可行。但是如何？

初始实现

窍门不是直接分配元素矩阵，而是分配一个 i pointers的数组（每行一个），其中每个指针指向 j 该行的元素：

void** matrix2_new( size_t esize, size_t idim, size_t jdim ) {
  size_t const ptrs_size = sizeof(void*) * idim;
  size_t const row_size = esize * jdim;
  void **const rows = malloc( ptrs_size );
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = malloc( row_size );
  return rows;
}

int **m2d = matrix2_new( sizeof(int), 3, 3 );
// ...
m2d[i][j] = 42;    // as if: *(*(m2d + i) + j) = 42

也就是说，m2d[i]产生了一个指向 ith int的行阵列，然后我们通过 j 。。。

但是，虽然此实现很简单，但此实现的问题是它需要 i + 1呼叫malloc()，我们需要编写一个相应的matrix2_free()函数，该函数将free()均等称为次数。

更好的实施

如果您查看第一个插图，您可能会意识到，没有理由将行阵列融为一部分记忆。行指针只需要指向每行的[i][0]元素：

执行此操作的代码是：

void** matrix2_new( size_t esize, size_t idim, size_t jdim ) {
  size_t const ptrs_size = sizeof(void*) * idim;
  size_t const row_size = esize * jdim;
  void **const rows = malloc( ptrs_size );
  char *const elements = malloc( idim * row_size );
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = &elements[ i * row_size ];
  return rows;
}

将elements宣布为char*而不是void*是必要的，因为我们可以使用void*进行指针算术。我们需要char*，特别是因为我们根据字节来工作。

这是更好的，因为我们现在只需要对malloc()的两个调用，但是我们仍然需要编写一个相应的matrix2_free()函数。

最佳实施

如果您查看第二个插图，您最终可能会怀疑是否可以将ROW POINTERS 和元素合并为一个记忆的一个。是的，他们可以，但是有一个陷阱：

size_t round_up_to( size_t n, size_t multiple ) {
  size_t const remainder = n % multiple;
  return remainder == 0 ? n : n + multiple - remainder;
}

void** matrix2_new( size_t esize, size_t ealign, size_t idim,
                    size_t jdim ) {
  // ensure &elements[0][0] is suitably aligned
  size_t const ptrs_size = round_up_to( sizeof(void*) * idim, ealign );
  size_t const row_size = esize * jdim;
  // allocate the row pointers followed by the elements
  void **const rows = malloc( char, ptrs_size + idim * row_size );
  char *const elements = (char*)rows + ptrs_size;
  for ( size_t i = 0; i < idim; ++i )
    rows[i] = &elements[ i * row_size ];
  return rows;
}

int **m2d = matrix2_new( sizeof(int), alignof(int), 3, 3 );