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

写在前面

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

方法1——动态分配（new）一维数组，再强制类型转换为二维（个人使用，推荐指数：⭐⭐⭐⭐）

直接看例子

/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size(); 
const int sz2 = str2.size(); 

/** 动态分配内存 */
auto f = new int[sz1 * sz2];
auto dp = (int (*)[sz2])f;

/** 这里放置自己制造bug的操作*/
// abaabaaba， 直接dp[i][j]使用即可

/** 制造完了别忘记释放栈空间 */
delete[] f;
f = nullptr;
dp = nullptr;

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

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

这个方法优点和缺点都很明显，灵活且完全和使用全局二维数组方法一样，且释放内存简单，但是使用存在危险性。如果觉得自己把握不住，建议先考虑其他方法。

另外，请读者考虑一下，可以使用如下的二重指针代替一维数组的指针进行类型转换吗？

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

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

我们思考后也不难理解，为什么声明二维数组的形参类型或者是强制类型转换时，一定要正确指定最低维的大小。

方法2——分配一维数组，以二维数组的方式使用（推荐指数：⭐⭐⭐）

其实如果不是非要追求“传统”的使用二维数组的方式，也可以不用强制类型转换的方法。

只需要把握一点：二维数组的所有元素，在内存中是连续排列的。

那么我们可以按照如下的方式使用分配的二维数组：

/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size(); 
const int sz2 = str2.size(); 

/** 动态分配内存 */
auto f = new int[sz1 * sz2];

/** 给每个元素赋值 */
for (int i = 0, idx = 1; i < sz1; ++i)
    for (int j = 0; j < sz2; ++j, ++idx)
        f[i * sz2 + j] = idx; /** 相当于 arr[i][j] = idx; */

/** 别忘记释放栈空间 */
delete[] f;
f = nullptr;

与方法一大同小异，因此注意事项也一样，注意f[i * sz2 + j]中sz2是最低维的大小。

方法3——多次动态分配（也需要多次释放）（推荐指数：⭐⭐）

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

/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size(); 
const int sz2 = str2.size(); 

/** 分配一个数组元素为一维数组的数组 */
auto dp = new int *[sz1];

/** 给数组每个元素赋值 */
for (int i = 0; i < sz1; ++i)
  dp[i] = new int[sz2];

/** 这里放置自己制造bug的操作*/
// abaabaaba

/** 制造完了别忘记释放栈空间 */
for (int i = 0; i < sz1; ++i)
  delete[] dp[i];

delete[] dp;

注意最后要先释放元素的内存。

（小声说，应该很少有人用这种方法？）

方法4——使用vector(推荐指数：⭐⭐⭐⭐⭐)

前面的几种方法多少是不太 idiomatic C++，最后当然要请出我们的STL。

没什么说的，直接看代码：

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

优点是不用再担心内存释放的问题，并且vector有很多方便的成员函数可以使用。

另外，在刷题的时候如果要判断二维vector是否为空，可以使用如下语句：

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

热门相关：超武穿梭   寂静王冠   第一神算：纨绔大小姐   刺客之王   网游之逆天飞扬