C++ 2D数组内存分配

Question

我之前并没有真正关注这个问题，但是让我感到非常惊讶的是，为 2D 数组分配内存的最直接方法是首先创建指针数组，然后为每个指针分配一个单独的 block 实际数组内容的内存。然后，数组可以分布在整个内存中，访问多行元素(例如 A[i][N-1] -> A[i+1][0])可能会导致性能损失。

stackoverflow 上的某个地方我找到了一种完美的类似 C 的解决方案，可以在一次 malloc 调用中分配空间。 但是使用 malloc 和不安全的指针转换并不是一个好的 C++ 实践，所以我决定研究一下我可以通过 google/code 来重新创建这个 C 方法并构造普通的 2D 数组 (A[m][n]) 并将其存储在一个单独的数组中。内存块(rowise)。

我想知道这样的解决方案是否存在任何问题。我在这里展示了一个在 VS 2015 中的 Windows 10 下编译的工作代码片段，其中/Wall 没有给出有关我的代码的警告。两个函数分配内存，类似于 C 和 C++。我还针对 x86 和 x64 编译了它，示例日志可以在代码部分之后找到。

来源:

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


void allocate(int m, int n, int** & arr)
{
// Allocates memory that is sufficient for storing m pointers to rows plus m*n continuos array
arr = (int**)malloc(m * sizeof(int*) + m*n * sizeof(int));

// First block of memory (m*sizeof(int*)) should be assigned with pointers to rows from second block of memory
for (int i = 0; i < m; i++)
{
    // arr is int**, arr + 1 shift pointer for sizeof(int*) bytes
    // arr + m points to the beginning of second (array) memory block, but it is of int** type;
    // consider it as a pointer to a single block of (int*), thus cast
    *(arr + i) = (int*)(arr + m) + n*i;

    //(int*)(arr + m) is the beginning of array, + n*i shifts to i-th row, j - iterates along that row
    // finally, * allows to zero memory at that address
    for (int j = 0; j < n; j++)
        *((int*)(arr + m) + n*i + j) = 0;
}

}

void allocatecpp(int m, int n, int** & p)
{
// Uses reinterpret_cast<T> as it performs casts from int** to int*, which are not allowed with normal casts
// Allocates memory that is sufficient for storing m pointers to rows plus m*n continuos array; function ::operator new(size)
p = reinterpret_cast<int**> (::operator new(m*n * sizeof(int) + m*sizeof(int*)));

// Iterates through first block of memory, assigning addresses of respective rows
for (int i = 0; i < m; i++)
{
    // Logic is the same as in C-style, but with some C++ stuff
    *(p + i) = reinterpret_cast<int*>(p + m) + n*i;
    for (int j = 0; j < n; j++)
        // Zeros memory
        *(reinterpret_cast<int*>(p + m) + n*i + j) = 0;
}

}

int main()
{
// Define size of an array; array of m rows x n columns
int m = 5, n = 4;

// array pointer, not sure how to use smart pointer here

int** arr;

// Allocates memory
allocatecpp(m, n, arr);

// Normally iterates through a 2D array, assigning values that correspond to the element position; e.g. element [3][2] gets value 43
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        arr[i][j] = 10 * (i+1) + (j+1);

// Address of the beginning; value of arr treated as a pointer
printf("Address of the beginning: 0x%p\r\n", arr);

// Moves along row address space and asks for addresses of a specific row
for (int i = 0; i < m; i++)
    printf("Row %i at address 0x%p pointing to 0x%p\r\n", i, arr+i, *(arr + i));

printf("\r\n");

// A pointer to an actual block of memory that represents array as continuous memory piece; casted to int*
int* p = (int*)(arr + m);

// Iterates through the whole array and prints addresses of elements and values (which correspond to position in matrix)
for (int i = 0; i < m * n; i++)
    printf("0x%p\t%02i\r\n", p + i, *(p + i));

delete (arr);

return 0;
}

x86 输出:

Address of the beginning: 0x00DADD18

Row 0 at address 0x00DADD18 pointing to 0x00DADD2C

Row 1 at address 0x00DADD1C pointing to 0x00DADD3C

Row 2 at address 0x00DADD20 pointing to 0x00DADD4C

Row 3 at address 0x00DADD24 pointing to 0x00DADD5C

Row 4 at address 0x00DADD28 pointing to 0x00DADD6C



0x00DADD2C  11

0x00DADD30  12

0x00DADD34  13

0x00DADD38  14

0x00DADD3C  21

0x00DADD40  22

0x00DADD44  23

0x00DADD48  24

0x00DADD4C  31

0x00DADD50  32

0x00DADD54  33

0x00DADD58  34

0x00DADD5C  41

0x00DADD60  42

0x00DADD64  43

0x00DADD68  44

0x00DADD6C  51

0x00DADD70  52

0x00DADD74  53

0x00DADD78  54

x64 输出

Address of the beginning: 0x000001D9E0FB4DE0

Row 0 at address 0x000001D9E0FB4DE0 pointing to 0x000001D9E0FB4E08

Row 1 at address 0x000001D9E0FB4DE8 pointing to 0x000001D9E0FB4E18

Row 2 at address 0x000001D9E0FB4DF0 pointing to 0x000001D9E0FB4E28

Row 3 at address 0x000001D9E0FB4DF8 pointing to 0x000001D9E0FB4E38

Row 4 at address 0x000001D9E0FB4E00 pointing to 0x000001D9E0FB4E48



0x000001D9E0FB4E08  11

0x000001D9E0FB4E0C  12

0x000001D9E0FB4E10  13

0x000001D9E0FB4E14  14

0x000001D9E0FB4E18  21

0x000001D9E0FB4E1C  22

0x000001D9E0FB4E20  23

0x000001D9E0FB4E24  24

0x000001D9E0FB4E28  31

0x000001D9E0FB4E2C  32

0x000001D9E0FB4E30  33

0x000001D9E0FB4E34  34

0x000001D9E0FB4E38  41

0x000001D9E0FB4E3C  42

0x000001D9E0FB4E40  43

0x000001D9E0FB4E44  44

0x000001D9E0FB4E48  51

0x000001D9E0FB4E4C  52

0x000001D9E0FB4E50  53

0x000001D9E0FB4E54  54

Answer 1

你做了很多工作却毫无结果。您从错误的陈述开始:

the most straightforward way to allocate memory for a 2D array [is] first creating array of pointers and then for each pointer assign a separate block of memory for actual array contents.

这在两种情况下是正确的:

1. 如果数组的不同行的大小不同(你的则不是)；
2. 如果您的堆非常碎片化，那么尝试分配一个(比如)1MB block 的成功率就低于(比如)1,000 个 1kB block 。

但是您正在 malloc() 分配一 block 内存，因此上面的 1. 和 2. 都不适用。

有些人认为您需要这样做的第三个原因是:

传递二维数组需要在编译时知道列数:

void Legal(int a[][1000]);
void Illegal(int a[][]);
void PointerVersion(int *a[], int numCols);

通过以上内容:

• Legal() 之所以有效，是因为编译器可以计算出如何访问 a[1][0];
• Illegal() 不起作用，因为编译器无法弄清楚如何访问 a[1][0];
• PointerVersion() 很明显 - 列数在运行时传入。

您没有收到警告的原因是您在各处进行类型转换 - 尤其是使用 int **&(颤抖!)。肯定有需要引用指针到指针的时候 - 这不是其中之一!

查看解决方案的另一种方法是:

typedef int Array1D[1000];      // 1,000 ints in a 1-D array
typedef Array1D *Array2D[1000]; // 1,000 pointers to 1-D arrays - a 2-D array!(?)

上面显示“二维数组”实际上是指向一维 int 数组的指针的一维数组。这些需要作为 int **(指向 int 的指针)传递。

不要。只是……不要。如果在知道高度和宽度的情况下需要一个二维整数数组，那么就硬着头皮分配内存块并将其分配给单个 int *:

int *array = (int *)malloc(m*n * sizeof(int));

array 现在是指向整数的指针。但是，它也是指向数组开头的指针；或二维数组；或 3-D 数组；或者...这就是为什么上面#3也是不必要的。将 int * 传递到各处(如有必要，作为 int *&)，并传递列数。

• 您不会浪费执行双重取消引用所需的时间；
• 您不会对自己正在做的事情失去任何清晰度。

或者，正如其他人提到的，将整个内容放在一个类中并隐藏所有内容。