我如何与动态分配的任意维数组工作？ [英] How can I work with dynamically-allocated arbitrary-dimensional arrays?
问题描述
典型的1-D阵列可以在声明静态或自动分配。
The typical 1-D array can be statically or automatically allocated in a declaration.
enum { n=100 };
int arr1[n];
或动态分配和访问通过一个指针。
Or dynamically-allocated and accessed via a pointer.
int *arr1m=malloc(n*sizeof*arr1m);
int *arr1c=calloc(n, sizeof*arr1c);
这两种方式访问一个元素具有相同的语法。
Both of these styles access an element with the same syntax.
int i = n/2;
arr1[i] = arr1c[i] = arr1m[i] = 42;
但是，当你添加第二个维度，它需要一些努力来实现相同的语法。
But when you add a second dimension, it takes some effort to achieve the same syntax.
int arr2[n][n];
int *arr2c=calloc(n*n,sizeof*arr2c);
arr2[5][5] = arr2c[5*n+5] = 23;
如果相反，你构建它作为一个的 Iliffe载体只能获得成倍组括号的。
You can only get the doubled set of brackets if instead you construct it as an Iliffe-vector.
int **arr2l=calloc(n,sizeof*arr2l);
for (int j=0; j<n; j++)
arr2l[j]=calloc(n,sizeof**arr2l);
arr2[6][6] = arr2l[6][6] = 72;
但是，这变得越来越笨重作为尺寸增加
But this becomes more and more cumbersome as the dimensions increase.
另一个困难是访问一个元素（让你不动它没有被正确分配的内存）之前检查动态数组的边界。该的真正的阵列可以使用的sizeof 运营商确定的范围，但这些动态数组随身携带的大小和他们在一起。
Another difficulty is checking the bounds of a dynamic array before accessing an element (so that you're not touching memory that was not properly allocated). The real arrays can use the sizeof operator to determine the bounds, but none of these dynamic arrays carry their size with them.
如何可以定义具有快速，连续的布局类似的阵列，但与用于访问单元与该工程的2D阵列，作为一个三维阵列相同指数列表一致的语法结构;和所有动态，以使他们能够传递到并返回从函数？动态可用大小
How can I define a structure that has fast, contiguous layout like an array, but with a consistent syntax for accessing elements with a list of indices that works the same for a 2D array as for a 3D array; and all dynamically, with sizes available dynamically so they can be passed to and returned from functions?
推荐答案
有在容纳动态分配的任意维数组歼语言（APL的一种方言）的实现使用的数据结构。它使用了结构 A混合动力和它的数据结构的动态数组，俗称的结构黑客的一招。 （在J实施这里和的这里）
There is a data structure used in the implementation of the J language (a dialect of APL) which accommodates dynamically-allocated arbitrary-dimensional arrays. It uses a hybrid of a struct and a dynamic array for its data structure, a trick commonly known as the struct hack. (More info on the J implementation here and here.)
要看到一个简单的环境的想法，考虑1D情况：我们想要一个动态一维数组与它一贯奉行的大小。所以：
To see the idea in a simple context, consider the 1D case: we want a dynamic 1D array which carries its size along with it. So:
struct vec { int n; int p[]; };
由于 P 成员是最后一个，和C没有内置的边界检查，它可以被用来访问更多的内存的关结束在<$ C $的C>结构。当然，如果分配，我们需要提供这种额外的内存，而不是简单地分配结构的大小。在结构只是数组的头的。 C90需要用于p []数组的长度的号码（例如，1），但C99允许省略的数目所以首部的尺寸是更简单的计算
Since the p member is last, and C has no built-in bounds checking, it can be used to access additional memory off the end of the struct. Of course, when allocating, we'll need to provide this extra memory and not simply allocate the size of the struct. The struct is just the header of the array. C90 requires a number (say, 1) for the length of the p[] array, but C99 allows the number to be omitted so the size of the header is more straightforward to calculate.
因此，随着更多维度的阵列将需要更多的值，以保持每个维度的尺寸。和我们的结构，以适应不同的维数的阵列，这维矢量的将需要可变长度以及
So, an array with more dimensions will need more values to hold the sizes of each dimension. And for our structure to accommodate arrays of different dimensionality, this dimension vector will need to be variable-length as well.
我们可以做些什么来实现这一切的是结构黑客的两倍，递归在自身申请。这给了我们一个内存布局就是这样，其中研究是我们将调用的级别的阵列中，<$的维数C $ C> D 值是每个维度的长度，而 V 值是实际的阵列数据：
What we can do to achieve all of this is to apply the struct hack twice, recursively upon itself. This gives us a memory layout like this, where R is the number of dimensions which we'll call the rank of the array, the D values are the lengths of each dimension, and the V values are the actual array data:
1 R Product(D)
--- -------------------- -----------------------------
R D[0] D[1] ... D[R-1] V[0] V[1] ... V[Product(D)-1]
和来形容这在C，
typedef struct arr { int r; int d[]; } *arr;
数组的元素 A 紧跟DIMS矢量研究元素 ð。因此， V 元素可以在 A-＆GT访问; D [R + 0]，A-＆GT; D [R + 1]。 .. A- D 1和D [R + I] （减少的索引向量之后的向下的扁平重新presentation一个索引）。元素是最简单的行优先的顺序来对待。实际元件的数目是所有尺寸的产品，所有尺寸相乘。的编辑：的这位前$ P $这里pssion可能更好的写法：（A-＆GT; D + A-＆GT; R）[0]，（A-＆GT; d + A-＆GT; r）的[1]，...（A-D 1和D + A-方式＆gt; r）的[I]
The elements of an array a immediately follow the R elements of the dims vector D. So the V elements can be accessed at a->d[r+0], a->d[r+1], ... a->d[r+i] (after reducing the index vector down to a single index on the flattened representation). The elements are easiest to treat in row-major order. The number of actual elements is the product of all the dimensions, all the dimensions multiplied together. The expression here might be better written: (a->d+a->r)[0], (a->d+a->r)[1], ... (a->d+a->r)[i].
为了分配这些东西，我们需要一个函数来计算本产品为大小计算的一部分。
In order to allocate one of these things, we'll need a function to compute this product as part of the size calculation.
int productdims(int rank, int *dims){
int z=1;
for(int i=0; i<rank; i++)
z *= dims[i];
return z;
}
和初始化，我们只需要填写相应的成员。
And to initialize, we just need to fill-in the members.
arr makearr(int rank, int *dims){
arr z = calloc( (sizeof(struct arr)/sizeof(int)) +
rank + productdims(rank,dims), sizeof(int));
z->r = rank;
memmove(z->d,dims,rank*sizeof(int));
return z;
}
记住用于访问二维数据式（发言权[米] [n]的元件的阵列）与单一索引（它是一种典型的动态数组像的问题）。元素[I] [J]是的 I＆倍; N＆加;Ĵ的。随着3D阵列[M] [N] [O]，元素[I] [J] [K]是的 I＆倍;（N次; O）及加; J＆次; O＆加; k 的。
Remembering the formula for accessing 2D data (say an array of [m][n] elements) with a single index (it's a typical dynamic array like in the question). Element [i][j] is at i×n+j. With a 3D array [m][n][o], element [i][j][k] is at i×(n×o)+j×o+k.
因此，我们可以从索引的阵列和尺寸的阵列计算我们的直线布置的数据的单个索引
So we can calculate a single index for our linearly-laid-out data from an array of indices and the array of dimensions.
int *elem(arr a, ...){
va_list ap;
int idx = 0;
va_start(ap,a);
if (a->r){
idx = va_arg(ap,int);
for(int i=1; i<a->r; i++){
idx *= a->d[i];
idx += va_arg(ap,int);
}
}
va_end(ap);
return &a->d[a->r + idx];
}
不要忘了标题：
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
瞧：
int main() {
{
int i,n=6;
arr m = makearr(1, (int[]){n});
for (i=0;i<n;i++)
*elem(m,i) = i;
for (i=0;i<n;i++,printf(" "))
printf("%d",*elem(m,i));
}
puts("\n");
{
int i,j,n=4;
arr m = makearr(2, (int[]){n,n});
for (i=0;i<n;i++)
for (j=0;j<n;j++)
*elem(m,i,j) = i*n+j;
for (i=0;i<n;i++,printf("\n"))
for (j=0;j<n;j++,printf(" "))
printf("%d",*elem(m,i,j));
}
puts("\n");
{
int i,j,k,n=3;
arr m = makearr(3, (int[]){n,n,n});
for (i=0;i<n;i++)
for (j=0;j<n;j++)
for (k=0;k<n;k++)
*elem(m,i,j,k) = (i*n+j)*n+k;
for (i=0;i<n;i++,printf("\n"))
for (j=0;j<n;j++,printf("\n"))
for (k=0;k<n;k++,printf(" "))
printf("%d",*elem(m,i,j,k));
}
return 0;
}
输出：
0 1 2 3 4 5
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
0 1 2
3 4 5
6 7 8
9 10 11
12 13 14
15 16 17
18 19 20
21 22 23
24 25 26
这code的进一步制定支持2D矩阵乘法和列片已发布到的 comp.lang.c 中的此线程。
Further elaboration of this code to support 2D matrix multiplication and column slices has been posted to comp.lang.c in this thread.
<一个href=\"http://stackoverflow.com/questions/30409991/use-a-dope-vector-to-access-arbitrary-axial-slices-of-a-multidimensional-array\">Better-motivated问题/更强大的数据结构。
这篇关于我如何与动态分配的任意维数组工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
