過去總以為vector和deque差不多，效率方面deque和vector接近，那干脆用效率高的vector好了。
但我忽略了另一方，一個事務(wù)存在就有它的理由，今天找到程序里面隱藏的bug給了我不得不用deque的理由，
deque和vector的結(jié)構(gòu)很類似，但它是多段連續(xù)空間，如果vector空間不夠的時候，要重新分配空間，并把所有的數(shù)據(jù)復(fù)制到新的空間中去，
deque不會這么做，它會去另外開辟一塊連續(xù)空間去存放數(shù)據(jù)，所以存儲效率方面deque高于vector,但deque又不同于鏈表，它可以說是順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的一個折中方案把，今天我寫了段代碼，是這樣的結(jié)構(gòu)
vector<SerializedEntity> archiveEntities; //也許你要問問什么不用vector<SerializedEntity*>，我這里比較特別，因為要讀寫磁盤的數(shù)據(jù)，序列化存儲 //回避了指針的數(shù)據(jù)讀寫方式，所以用的vector<SerializedEntity>
那么：Entity * ent = &archive[0]; //看似沒問題,其實里面暗藏殺機
這個archiveEntities 如果不改變是沒有問題，但如果序列集又動態(tài)添加了數(shù)據(jù)，恰好沒有預(yù)留空間，那么將導(dǎo)致整個集合重新分配連續(xù)空間了，所以那個引用也將“失效了”，這讓我很頭疼，這個時候讓我想起了deque，它真的很棒，不會去重整空間，需要的時候再開辟其他連續(xù)的空間，雖然讀的效率降低了，但
這點損失對于我的程序基本可以忽略不計的，IO數(shù)據(jù)本身就很少去遍歷訪問，卻能給程序很好的去“引用”，不用擔(dān)心引用失效的情況，這方面deque確實是個很好的選擇
找到一篇文章與大家分享一下，也是應(yīng)證我的觀點的：
operator[]
operator[] 是指通過下標(biāo)取數(shù)據(jù)。顯然 list 的復(fù)雜度為O(N)，非常慢。而 vector、deque 均為 O(1)。讓我們想象下 deque：：operator[] 的實現(xiàn)：
_E deque::operator[](int i)
{
return m_storage[i/BlockSize][i%BlockSize];
} |
可以看出，deque 只比 vector 多了一次內(nèi)存訪問。
空間性能分析
push_back
vector
很不幸，如果 vector 采用 N*2 的內(nèi)存增長模型(通常如此)，那么在最差的情況下，空間復(fù)雜度就是 2*N ，最好的情況下為 N(所有的內(nèi)存都用上了)。平均來講，空間復(fù)雜度為 1.5*N .也就是說，通常差不多有一半的內(nèi)存是被浪費的。
list
list 的空間浪費與 vector 相比不遑多讓。它的空間復(fù)雜度為 (1 + sizeof(pointer)*2/sizeof(_E))*N.如果我們讓 list 存儲的元素為 pointer(即 _E = pointer)，那么空間復(fù)雜度為 3*N，比 vector 還浪費。
deque
deque 的最差情況下的空間復(fù)雜度為 N + sizeof(pointer)*2*N/(BlockSize*sizeof(_E))(這里假設(shè)vector也采用 2*N 增長模型，平均復(fù)雜度則將式中2改為1.5即可)。如果我們保存的元素為 pointer(即 _E = pointer)，并且BlockSize取512，那么空間復(fù)雜度為 N + N/256.也就是說最差情況下只浪費了 N/256 的內(nèi)存。
deque的其他特性
元素地址不變
由于 deque 并不進行數(shù)據(jù)搬移，帶來一個有意思的特性，就是 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)可能會由于內(nèi)存搬移而失效。但是如果我們將容器換為 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! |
結(jié)論
通過 vector， list， deque 的時間、空間性能對比，我們可以看出，應(yīng)該提倡盡可能使用 deque 這個容器。特別是，如果要承受海量數(shù)據(jù)，deque 是最合適的人選了。