二维数组和vector性能差别如何这么大
二维数组和vector<vector>性能差别怎么这么大？
int tmp[256][256];
int a[256][256];
std::vector <std::vector <int> > vtmp;
//设置vtmp元素个数为[256][256]，对tmp,vtmp中的元素进行赋值，使tmp[i][j] == vtmp[i][j]。
//...
time_t now;
now = time(NULL);
cout < < ctime(&now) < < endl;
for(int n = 0; n < 4096; n++)
for(int i = 0; i < 256; i++)
for(int j = 0; j < 256; j++)
{
a[i][j] = tmp[i][j];
a[i][j] += tmp[i][j];
a[i][j] /= tmp[i][j];
}
now = time(NULL);
cout < < ctime(&now) < < endl;
这段程序大约2次cout之间的时间差为10秒左右，但是把其中的tmp[i][j]改成vtmp[i][j]之后，程序运行了几分钟还没有结束。
不是说vector的性能基本相当于数组吗？怎么差别这么大？
------解决方案--------------------
刚才是我疏忽了，拿debug模式的数组和release模式的vector做了比较（汗！竟然结果正好是“几乎”“一样快”）。
但是数组不到1秒也不是正确的结果（其实是 < <1秒，既然循环次数*8仍然是不精确的1秒），这应该是优化的结果：未使用的变量不计算，这是一种常用的代码优化手段；而vector比内建类型的数组复杂，编译器不能够优化了。
于是做了实验，在循环之后（确切地说，在 cout < < ctime(&now) < < endl; 之后）加入一条语句：
cout < < a[0][0] < < endl;
这样在我的机子上，数组的性能是4秒（下降了N倍，之前是 < <1秒），vector则是7秒（和之前一样）。看来之前数组确实是优化了。（不过编译器确实比较“憨”，只是访问了一个元素，竟然所有都不优化了）
然后又实验了32768，数组是34秒，vector是64秒。因此大致可以确定，在VS2005的STL中，vector的性能是数组的一半。
------解决方案--------------------
在vector <vector <int> > 与 int[][]访问时计算偏移量的方法可能是不一样的.
------解决方案--------------------
刚才在VC6里面实验了一下，在Release模式下，使用数组仍然和使用vector差不多，大概要10秒左右，而在VC2005中，用时少于1秒，看来VC2005对这种情况的优化很到位啊，还是因为VC6里面有些什么需要特殊设置的地方才能打开这个优化开关？
------解决方案--------------------
我的实测数据（把time函数换成clock函数，得到的是CPU时间，毫秒计）：
VC 6，release：
array test: now start...
used 5469ms
vector test: now start...
used 5531ms
交换测试顺序后：
vector test: now start...
used 5531ms
array test: now start...
used 5469ms
可见VC Release下vector和内置数组几乎一样快。已经过反复测试，时间十分精确。
MinGW GCC 4.1.2，不使用任何优化：
array test: now start...
used 13453ms
vector test: now start...
used 105969ms
这个差异就十分明显，估计也是为了方便调试在vector中加入了许多冗余信息。
MinGW GCC 4.1.2，打开-O选项编译：
array test: now start...
used 0ms
vector test: now start...
used 0ms
竟然几乎不用时间。交换测试次序效果相同。
我猜测可能是GCC认为内循环没有做实质性的活动，直接把循环整个“优化”掉了。
为了防止GCC编译的过分优化，我把数组a设为volatile类型（可防止对a优化，但不影响vtmp和tmp）。然后打开-O2选项进行优化测试：
array test: now start...
used 6672ms
vector test: now start...
used 6656ms
交换测试次序后：
vector test: now start...
used 6656ms
array test: now start...
used 6672ms
这个结果时间上比较合理（在Windows下GCC一般没有VC优化得快，并不奇怪）。可以看出，用vector可能更快一些！
结论：在打开优化选项的情况下，用vector编译出的代码一点也不比用内置数组的逊色，在一些实现上甚至可能更快。
在不进行任何优化的情况下，vector和数组的性能差距比较大。但这点在实际中是可忽略的，因为实际的程序总是优化编译的。
附测试代码：
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int main()
{
int tmp[256][256];
int a[256][256];
// int volatile a[256][256];
vector < vector <int> > vtmp;
for (int i = 0; i < 256; ++i) {
vector <int> t;
vtmp.push_back(t);
for (int j = 0; j < 256; ++j) {
int tmp[256][256];
int a[256][256];
std::vector <std::vector <int> > vtmp;
//设置vtmp元素个数为[256][256]，对tmp,vtmp中的元素进行赋值，使tmp[i][j] == vtmp[i][j]。
//...
time_t now;
now = time(NULL);
cout < < ctime(&now) < < endl;
for(int n = 0; n < 4096; n++)
for(int i = 0; i < 256; i++)
for(int j = 0; j < 256; j++)
{
a[i][j] = tmp[i][j];
a[i][j] += tmp[i][j];
a[i][j] /= tmp[i][j];
}
now = time(NULL);
cout < < ctime(&now) < < endl;
这段程序大约2次cout之间的时间差为10秒左右，但是把其中的tmp[i][j]改成vtmp[i][j]之后，程序运行了几分钟还没有结束。
不是说vector的性能基本相当于数组吗？怎么差别这么大？
------解决方案--------------------
刚才是我疏忽了，拿debug模式的数组和release模式的vector做了比较（汗！竟然结果正好是“几乎”“一样快”）。
但是数组不到1秒也不是正确的结果（其实是 < <1秒，既然循环次数*8仍然是不精确的1秒），这应该是优化的结果：未使用的变量不计算，这是一种常用的代码优化手段；而vector比内建类型的数组复杂，编译器不能够优化了。
于是做了实验，在循环之后（确切地说，在 cout < < ctime(&now) < < endl; 之后）加入一条语句：
cout < < a[0][0] < < endl;
这样在我的机子上，数组的性能是4秒（下降了N倍，之前是 < <1秒），vector则是7秒（和之前一样）。看来之前数组确实是优化了。（不过编译器确实比较“憨”，只是访问了一个元素，竟然所有都不优化了）
然后又实验了32768，数组是34秒，vector是64秒。因此大致可以确定，在VS2005的STL中，vector的性能是数组的一半。
------解决方案--------------------
在vector <vector <int> > 与 int[][]访问时计算偏移量的方法可能是不一样的.
------解决方案--------------------
刚才在VC6里面实验了一下，在Release模式下，使用数组仍然和使用vector差不多，大概要10秒左右，而在VC2005中，用时少于1秒，看来VC2005对这种情况的优化很到位啊，还是因为VC6里面有些什么需要特殊设置的地方才能打开这个优化开关？
------解决方案--------------------
我的实测数据（把time函数换成clock函数，得到的是CPU时间，毫秒计）：
VC 6，release：
array test: now start...
used 5469ms
vector test: now start...
used 5531ms
交换测试顺序后：
vector test: now start...
used 5531ms
array test: now start...
used 5469ms
可见VC Release下vector和内置数组几乎一样快。已经过反复测试，时间十分精确。
MinGW GCC 4.1.2，不使用任何优化：
array test: now start...
used 13453ms
vector test: now start...
used 105969ms
这个差异就十分明显，估计也是为了方便调试在vector中加入了许多冗余信息。
MinGW GCC 4.1.2，打开-O选项编译：
array test: now start...
used 0ms
vector test: now start...
used 0ms
竟然几乎不用时间。交换测试次序效果相同。
我猜测可能是GCC认为内循环没有做实质性的活动，直接把循环整个“优化”掉了。
为了防止GCC编译的过分优化，我把数组a设为volatile类型（可防止对a优化，但不影响vtmp和tmp）。然后打开-O2选项进行优化测试：
array test: now start...
used 6672ms
vector test: now start...
used 6656ms
交换测试次序后：
vector test: now start...
used 6656ms
array test: now start...
used 6672ms
这个结果时间上比较合理（在Windows下GCC一般没有VC优化得快，并不奇怪）。可以看出，用vector可能更快一些！
结论：在打开优化选项的情况下，用vector编译出的代码一点也不比用内置数组的逊色，在一些实现上甚至可能更快。
在不进行任何优化的情况下，vector和数组的性能差距比较大。但这点在实际中是可忽略的，因为实际的程序总是优化编译的。
附测试代码：
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int main()
{
int tmp[256][256];
int a[256][256];
// int volatile a[256][256];
vector < vector <int> > vtmp;
for (int i = 0; i < 256; ++i) {
vector <int> t;
vtmp.push_back(t);
for (int j = 0; j < 256; ++j) {