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