過去總以為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 是最合適的人選了。