先看三段代码:

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int main()
{
	vector<int> a;
	for(int i=0;i<N;i++)
		a.push_back(i);
	return 0;
}//0.0234s

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int main()
{
	vector<int> a;
	for(int i=0;i<N;i++)
		a.insert(a.begin(),i);
	return 0;
}//0.5903s

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N+5];

int main()
{
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
			a[j+1]=a[j];
		a[0]=i;
	}
	return 0;
}//23.03s

网上(?)说vector的内存是连续的，所以按理说非尾部插入比较慢(实际上确实是的(1&2)),但是为什么比普通数组插入快这么多?