C++动态分配（new）二维数组的若干方法

写在前面

之前刷动态规划的题目，多需要用到二维数组（也许后面再优化成一维）。如果每次都按照给定数的范围直接声明为全局二维数组变量，又总觉得的不够优雅。查阅了一些网上的资料后，总结了一些使用方法，就写下这篇博文用以记录。
方法1——动态分配（new）一维数组，再强制类型转换为二维（个人使用，推荐指数：⭐⭐⭐⭐）

直接看例子

1. /** 假设需要根据两个string的长度建立二维数组 */
2. const int sz1 = str1.size();
3. const int sz2 = str2.size();
5. /** 动态分配内存 */
6. auto f = new int[sz1 * sz2];
7. auto dp = (int (*)[sz2])f;
9. /** 这里放置自己制造bug的操作*/
10. // abaabaaba， 直接dp[i][j]使用即可
12. /** 制造完了别忘记释放栈空间 */
13. delete[] f;
14. f = nullptr;
15. dp = nullptr;

复制代码

注意，auto dp = (int (*)[sz2]f这条语句，sz2的大小一定要是后面使用二维数组时最低维的大小。
如果按照上面的类型转换方式，下面这样写会出现bug（注意sz1和sz2的顺序）：

1. for (int i = 0; i < sz2; ++i)
2.   for (int j = 0; j < sz1; ++j)
3.     // do something;
4.     /** 其实大概率你啥也do不了，程序跑飞了 */

复制代码

这个方法优点和缺点都很明显，灵活且完全和使用全局二维数组方法一样，且释放内存简单，但是使用存在危险性。如果觉得自己把握不住，建议先考虑其他方法。
另外，请读者考虑一下，可以使用如下的二重指针代替一维数组的指针进行类型转换吗？

1. auto f = new int[sz1 * sz2];
2. auto dp = (int **)f; /** 二重指针真的可以吗？*/

复制代码

若觉得可行的话，可能对二维数组和二重指针的理解出现了偏差。试想，我们按照dp存储的地址值a去寻址，得到地址a中存储的值b，再按照值b去寻址的话会发生什么？（本例中，b的值的根本不是地址，而是数组的值！）

我们思考后也不难理解，为什么声明二维数组的形参类型或者是强制类型转换时，一定要正确指定最低维的大小。
方法2——分配一维数组，以二维数组的方式使用（推荐指数：⭐⭐⭐）

其实如果不是非要追求“传统”的使用二维数组的方式，也可以不用强制类型转换的方法。
只需要把握一点：二维数组的所有元素，在内存中是连续排列的。
那么我们可以按照如下的方式使用分配的二维数组：

1. /** 假设需要根据两个string的长度建立二维数组 */
2. const int sz1 = str1.size();
3. const int sz2 = str2.size();
5. /** 动态分配内存 */
6. auto f = new int[sz1 * sz2];
8. /** 给每个元素赋值 */
9. for (int i = 0, idx = 1; i < sz1; ++i)
10.     for (int j = 0; j < sz2; ++j, ++idx)
11.         f[i * sz2 + j] = idx; /** 相当于 arr[i][j] = idx; */
13. /** 别忘记释放栈空间 */
14. delete[] f;
15. f = nullptr;

复制代码

与方法一大同小异，因此注意事项也一样，注意f[i * sz2 + j]中sz2是最低维的大小。
方法3——多次动态分配（也需要多次释放）（推荐指数：⭐⭐）

简单说，就是动态分配一维数组，然后把这些数组的指针存储到一个数组元素为一维数组的数组中。
代码如下：

1. /** 假设需要根据两个string的长度建立二维数组 */
2. const int sz1 = str1.size();
3. const int sz2 = str2.size();
5. /** 分配一个数组元素为一维数组的数组 */
6. auto dp = new int *[sz1];
8. /** 给数组每个元素赋值 */
9. for (int i = 0; i < sz1; ++i)
10.   dp[i] = new int[sz2];
12. /** 这里放置自己制造bug的操作*/
13. // abaabaaba
15. /** 制造完了别忘记释放栈空间 */
16. for (int i = 0; i < sz1; ++i)
17.   delete[] dp[i];
19. delete[] dp;

复制代码

注意最后要先释放元素的内存。
（小声说，应该很少有人用这种方法？）
方法4——使用vector(推荐指数：⭐⭐⭐⭐⭐)

前面的几种方法多少是不太 idiomatic C++，最后当然要请出我们的STL。
没什么说的，直接看代码：

1. vector<vector<int> > dp(str1.length(), vector<int>(str2.length(), 0));

复制代码

优点是不用再担心内存释放的问题，并且vector有很多方便的成员函数可以使用。
另外，在刷题的时候如果要判断二维vector是否为空，可以使用如下语句：

1. if (dp.empty() || dp[0].empty())
2.   return ;

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！