过去总以为vector和deque差不多，效率方面deque和vector接近，那干脆用效率高的vector好了。
但我忽略了另一方，一个事务存在就有它的理由，今天找到程序里面隐藏的bug给了我不得不用deque的理由，
deque和vector的结构很类似，但它是多段连续空间，如果vector空间不够的时候，要重新分配空间，并把所有的数据复制到新的空间中去，
deque不会这么做，它会去另外开辟一块连续空间去存放数据，所以存储效率方面deque高于vector,但deque又不同于链表，它可以说是顺序存储结构和链式存储结构的一个折中方案把，今天我写了段代码，是这样的结构
vector<SerializedEntity> archiveEntities; //也许你要问问什么不用vector<SerializedEntity*>，我这里比较特别，因为要读写磁盘的数据，序列化存储 //回避了指针的数据读写方式，所以用的vector<SerializedEntity>
那么：Entity * ent = &archive[0]; //看似没问题,其实里面暗藏杀机
这个archiveEntities 如果不改变是没有问题，但如果序列集又动态添加了数据，恰好没有预留空间，那么将导致整个集合重新分配连续空间了，所以那个引用也将“失效了”，这让我很头疼，这个时候让我想起了deque，它真的很棒，不会去重整空间，需要的时候再开辟其他连续的空间，虽然读的效率降低了，但
这点损失对于我的程序基本可以忽略不计的，IO数据本身就很少去遍历访问，却能给程序很好的去“引用”，不用担心引用失效的情况，这方面deque确实是个很好的选择
找到一篇文章与大家分享一下，也是应证我的观点的：
operator[]
operator[] 是指通过下标取数据。显然 list 的复杂度为O(N)，非常慢。而 vector、deque 均为 O(1)。让我们想象下 deque：：operator[] 的实现：
_E deque::operator[](int i)
{
return m_storage[i/BlockSize][i%BlockSize];
} |
可以看出，deque 只比 vector 多了一次内存访问。
空间性能分析
push_back
vector
很不幸，如果 vector 采用 N*2 的内存增长模型(通常如此)，那么在最差的情况下，空间复杂度就是 2*N ，最好的情况下为 N(所有的内存都用上了)。平均来讲，空间复杂度为 1.5*N .也就是说，通常差不多有一半的内存是被浪费的。
list
list 的空间浪费与 vector 相比不遑多让。它的空间复杂度为 (1 + sizeof(pointer)*2/sizeof(_E))*N.如果我们让 list 存储的元素为 pointer(即 _E = pointer)，那么空间复杂度为 3*N，比 vector 还浪费。
deque
deque 的最差情况下的空间复杂度为 N + sizeof(pointer)*2*N/(BlockSize*sizeof(_E))(这里假设vector也采用 2*N 增长模型，平均复杂度则将式中2改为1.5即可)。如果我们保存的元素为 pointer(即 _E = pointer)，并且BlockSize取512，那么空间复杂度为 N + N/256.也就是说最差情况下只浪费了 N/256 的内存。
deque的其他特性
元素地址不变
由于 deque 并不进行数据搬移，带来一个有意思的特性，就是 deque 的元素地址在只有 push_back/push_front，没有 insert/erase 时，可保持元素地址不变。
需要注意的是，vector 并不具备这样的特性。如下的代码是不合法的：
std::vector<int> vec;
...
int& elem = vec[i];
vec.push_back(100);
elem = 99; // error: can't access elem since vec was changed! |
由于取得 elem 之后存在 push_back 操作，所获得的元素地址(&elem)可能会由于内存搬移而失效。但是如果我们将容器换为 std：：deque，则这个代码不会有任何问题。
std::deque<int> dq;
...
int& elem = dq[i];
dq.push_back(100);
elem = 99; // ok! |
另外需要注意的是，元素地址不变，并不代表 iterator 不变，如下的代码 deque 并不支持：
std::deque<int> dq;
...
std::deque<int>::iterator it = dq.begin() + i;
dq.push_back(100);
*it = 99; // error: can't access iterator since deque was changed! |
结论
通过 vector， list， deque 的时间、空间性能对比，我们可以看出，应该提倡尽可能使用 deque 这个容器。特别是，如果要承受海量数据，deque 是最合适的人选了。