在结构中需要一个二维“可变”大小的数组

I am attempting to implement a grid of cells, analogous to that of Conway's game of life.

我正在尝试实现一个单元格网格，类似于康威的生命游戏。

While each individual grid should have fixed size in both dimensions, I would like a Grid struct that allows for any size in both dimensions.

虽然每个单独的网格在两个维度上都应该有固定的大小，但是我希望有一个网格结构，允许在两个维度上有任何大小。

This is in analogy to how arrays can be of any size, but an array once initialized has a fixed size.

这与数组的大小类似，但是初始化的数组有固定的大小。

This is what I have so far:

这是我目前所拥有的:

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[][];
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell)*width*height );
    return g;
}

However I get the following compile-time error:

但是我得到以下编译时错误:

main.c|12|note: declaration of `‘cell’ as multidimensional array must have bounds for all dimensions except the first|

How can I define a Grid data type with flexible size?

如何定义具有灵活大小的网格数据类型?

Post scriptum: as a C newbie, I thought the following would work:

编剧:作为一名C新手，我认为下面的方法会奏效:

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell cell[width][height];
} Grid;

Post post scriptum: I am always uneasy whenever I use malloc. Am I doing (or trying to do) anything horribly wrong here?

贴帖脚本:每当我使用malloc的时候，我总是感到不安。我在做(或试图做)任何可怕的错误吗?

4 个解决方案

#1

You can't do it with double indexing (cell[x][y]) in C, there's no way to express that the number of bytes to jump for each row is dynamic.

在C语言中，不能使用双索引(cell[x][y])，无法表示每一行要跳转的字节数是动态的。

So, the best (in my opinion) way to do is it to just do the indexing manually, using a one-dimensional array.

所以，最好的方法就是用一维数组来手动进行索引。

Put a plain:

把一个普通的:

Cell *cell;

in the struct (keeping width and height) and then index like so:

在结构(保持宽度和高度)中，索引如下:

set_cell(Grid *g, unsigned int x, unsigned int y, Cell value)
{
  g->cell[y * g->width + x] = value;
}

it's not unlikely that the compiler will inline this, and it's going to be pretty tight. Probably faster than the jagged array" approach which uses much more memory and another layer of indirection.

编译器不太可能内联这个，而且会非常紧密。可能比锯齿状数组“方法更快，它使用更多的内存和另一层间接。

Allocation is simple:

配置很简单:

Grid initGrid(unsigned int width, unsigned int height)
{
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc(width * height * sizeof *g.cell);
    // add assert or error here, can't return NULL for value type
    return g;
}

if you wanted to heap-allocate Grid too, you could co-allocate it with its elements.

如果您也想堆分配网格，您可以将它与它的元素一起分配。

And yes, you need to free() the allocation when you're done with it, in order to not leak memory. Strictly speaking on modern systems the OS will free all resources when the program ends anyway, but it's good form to free anyway:

是的，您需要在处理完分配之后释放()这个分配，以避免内存泄漏。严格地说，在现代系统中，当程序结束时，操作系统将会释放所有的资源，但是无论如何它都是免费的:

void destroyGrid(Grid g)
{
  free(g.cell);
}

#2

You are pretty much out of luck here, as there is no way in C to use variable array lengths within a struct definition. What you can do is this:

您在这里非常不走运，因为在C语言中，在struct定义中不可能使用可变数组长度。你能做的是:

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

#define cell(myGrid) ((Cell(*)[(myGrid).height])(myGrid).cell_internal)

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
cell(*newGrid) = malloc(newGrid->width*sizeof(*cell(*newGrid)));
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cell(*newGrid)[x][y] = ...;
    }
}

This is a dirty little hack, but it should work fine. The cool part is, that you can simply address your grid cells with cell(aGrid)[x][y]. The downside is, that it does obscure what is actually going on quite thoroughly. And there are not many people who can actually read what the cell() macro does. (Hint: It simply casts the void* to a pointer to a column array Cell(*)[myGrid.height], whatever myGrid.height may be at that point in time.)

这是一个肮脏的小技巧，但应该可以用得很好。很酷的一点是，你可以简单地用cell(aGrid)[x][y]来定位你的网格单元格。缺点是，它确实掩盖了真正正在发生的事情。并且没有多少人能够真正读懂cell()宏的功能。(提示:它只是将void*转换为指向列数组单元格(*)的指针[myGrid]。高度),无论myGrid。高度可能在那个时间点。

---

Of course, you can go more explicit like this:

当然，你可以这样说:

typedef struct Grid {
    unsigned width, height;
    void* cell_internal;    //Type: Cell(*)[height]
} Grid;

//in the constructor of Grid
newGrid->width = ...;
newGrid->height = ...;
Cell (*cells)[newGrid->height] = malloc(newGrid->width*sizeof(*cells));
newGrid->cell_internal = cells;
for(unsigned x = 0; x < newGrid->width; x++) {
    for(unsigned y = 0; y < newGrid->height; y++) {
        cells[x][y] = ...;
    }
}

The downside of this approach is, that you will need to explicitly create an alias pointer for the cell_internal pointer in each function that works on the cell data with

这种方法的缺点是，您需要显式地为每个处理单元数据的函数中的cell_internal指针创建一个别名指针

Cell (*cells)[myGrid->height] = myGrid->cell_internal;

Probably, this is the better approach, as it would seem to be readable to more people.

也许，这是更好的方法，因为它对更多的人来说似乎是可读的。

#3

Use a flexible array. It's trivial to do with two malloc() calls, and possible to do with just one if you care to push the limits of alignment restrictions or strict aliasing or want to write the code to coerce the alignment of the portion of malloc()'d used to store Cell structures.

使用一个灵活的数组。使用两个malloc()调用非常简单，如果您希望突破对齐限制或严格的别名限制，或者希望编写代码强制用于存储单元结构的malloc() d部分的对齐，那么只需使用一个malloc()调用即可。

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // get all the data needed with one malloc call
    g->cell[ 0 ] = malloc( width * height * sizeof( Cell ) );

    // fill in the pointers
    for ( unsigned ii = 1; ii < height; ii++ )
    {
        g->cell[ ii ] = g->cell[ 0 ] + ii * width;
    }

    return g;
}

void freeGrid( Grid *g )
{
    free( g->cell[ 0 ] );
    free( g );
}

If you don't mind pushing the limits of strict aliasing, you can do it with a flexible array and a single call to malloc() (it's left as an exercise for the reader to coerce the alignment of the data portion so that there's no potential alignment problems - that definitely is possible to do):

如果你不介意把限制严格的混叠,你可以灵活的数组和一个调用malloc()(它留给读者作为练习强制对齐的数据部分,这样没有潜在的对齐问题-这绝对是有可能的):

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell[];
} Grid;

Grid *initGrid(unsigned width, unsigned height )
{
    // the Grid structure itself
    size_t bytesNeeded = sizeof( Grid );

    // space for pointers
    bytesNeeded += height * sizeof( Cell * );

    // space for data
    bytesNeeded += width * height * sizeof( Cell );

    Grid *g = malloc( bytesNeeded );
    g->width = width;
    g->height = height;

    // fill in the pointers
    // (technically a strict-aliasing/alignment violation as it assumes
    // that &(g->cell[ height ]) is suitable to store a Cell...)
    for ( unsigned ii = 0; ii < height; ii++ )
    {
        g->cell[ ii ] = ( Cell * ) &(g->cell[ height ]) +
            ii * width;
    }

    return g;
}

#4

following this excelent post: How do I work with dynamic multi-dimensional arrays in C? read @JensGustedt post and follow his link variable length arrays (VLAs)

下面这篇精辟的文章:如何使用C中的动态多维数组?阅读@JensGustedt文章并跟随他的链接变量长度数组(VLAs)

there is actually a way - I followed his post and written a small test program to verify:

实际上有一种方法——我跟随他的帖子，写了一个小测试程序来验证:

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

int main(int argc, char ** argv)
{
    unsigned int height = 100;
    unsigned int width = 10;

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

    array[90][2] = 1231;
    printf("%d", array[90][2]);
}

---

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

int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    int (*array)[width] = malloc (sizeof(int[height][width]));

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j] = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j]);
        printf("\n");
    }
}

---

and the console:

控制台:

enter width: 10
enter height: 6
0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 

---

I'll admit it suprising - I was not aware this exists...

我得承认这让人吃惊——我不知道这是真的……

---

EDIT - using structs:

编辑-使用结构体:

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

typedef struct Cell {
    int data;
    // stuff to be added later
} Cell;

typedef struct Grid {
    unsigned width;
    unsigned height;
    Cell *cell;
} Grid;

Grid initGrid(unsigned width, unsigned height) {
    Grid g;
    g.width = width;
    g.height = height;
    g.cell = malloc( sizeof(Cell[height][width]) );
    return g;
}
int main(int argc, char ** argv)
{
    unsigned int height;
    unsigned int width;
    int i,j;
    Grid test;

    printf("enter width: ");
    scanf("%d", &width);
    printf("enter height: ");
    scanf("%d", &height);
    test = initGrid (width, height);
    Cell (*array)[width] = test.cell;

    for (i = 0; i < height; i++ )
        for (j = 0; j < width; j++ )
            array[i][j].data = i;

    for (i = 0; i < height; i++ ) {
        for (j = 0; j < width; j++ )
            printf("%d ", array[i][j].data);
        printf("\n");
    }
}

console output:

控制台输出:

enter width: 20
enter height: 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 

there is a casting warning which i did not have time to resolve, but one can implement the idea - just do it cleanly... again it's a POC not an actual program

有一个我没有时间去解决的铸造警告，但是一个人可以实现这个想法——只是干净的做它……这是一个POC，不是实际的程序