[C++]二维数组还是一维数组？(2)

除了直接使用一维和二维数组，也可以对一维数组进行二维索引，方法是把一维数组中所有对应第一列的元素的地址单独作为一个指针数组，这样本质上还是一维数组，但是实现了形式上的二维数组调用，这种办法空间申请的代码如下：

 

1 // Create 2 int **m = new int*[n_row]; 3 int *block = new int[n_row * n_col]; 4 for ( int i = 0; i < n_row; ++i ) 5 m[i] = &block[i * n_col]; 6 return m;

释放的代码和二维数组相同。

用一维数组模拟二维调用的优点是既保证了内存空间的连续性，又保持了二维调用的代码易维护的优点。不过需要注意的是，由于是二维索引，汇编代码和二维数组还是一样的。

测试结果

执行上面的代码，在不同行数和列数下，循环执行取平均值，结果如下：

内存的申请和释放：

逐行访问

逐列访问

按间隔访问

分析

内存的连续性：一维数组显然有着比二维数组更好的连续性，我忘了以前是在哪看到的一个形象的字符画说明一维数组和二维数组的区别，大概是下面这样子：

一维数组：

┌--┬--┬--┬--┬- | | | | | ... └--┴--┴--┴--┴-

二维数组：

 

┌--┬--┬--┬--┬- | | | | | ... └--┴--┴--┴--┴- | | | | | V | | ┌--┬--┬--┬- | | | | | | ... | | └--┴--┴--┴- | V | ┌--┬--┬--┬--┬- | | | | | | ... | └--┴--┴--┴--┴- V ┌--┬--┬--┬--┬--┬- | | | | | | ... └--┴--┴--┴--┴--┴-

 

缓存命中率：缓存是SRAM，内存是DRAM，效率差很多，所以如果能提高缓存中的命中率，效率能提高很多。其实这和上一条其实也有关联，显然连续的内存命中率会高，不过如果申请的内存空间非常大那具体问题得具体分析了。

指令执行速度：由于早年体系没学好，所以我也不知道这条有多大影响，另外现在的电脑都是多核的，作为不搞多核算法的人，不太懂会有多大影响。

对照结果可以看到基本上而言一维数组的效率完爆二维数组，尤其是内存申请和小内存访问的情况，总体而言效率上一维数组>一维数组的二维引用>二维数组。不过也有比较有意思的发现：1) 逐行访问的时候，在开辟内存空间小的时候一维数组二维索引效率高于二维数组，而大内存情况下却变慢了。2) 逐列访问基本符合预期，一维数组和一维数组二维索引效率接近，二维索引效率略低，但是都优于二维数组。3) 按间隔访问的时候一维数组大幅快于逐行访问，不太懂这是为什么，是否我电脑是多核的影响？还是说VS的O2编译的作用？

纯属蛋疼的测试，也相当不严谨，希望有体系知识比较丰富的大拿指点一二。

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

Linux-C成长之路（一）：Linux下C编程概要

Linux-C成长之路（二）：基本数据类型

Linux-C成长之路（三）：基本IO函数操作

Linux-C成长之路（四）：运算符

Linux-C成长之路（五）：控制流

Linux-C成长之路（六）：函数要义

Linux-C成长之路（七）：数组与指针

Linux-C成长之路（八）：存储类，动态内存

Linux-C成长之路（九）：复合数据类型

Linux-C成长之路（十）：其他高级议题