但我忽略了另一方,，一個(gè)事務(wù)存在就有它的理由，今天找到程序里面隱藏的bug給了我不得不用deque的理由,，

deque和vector的結(jié)構(gòu)很類似,，但它是多段連續(xù)空間，如果vector空間不夠的時(shí)候,，要重新分配空間,，并把所有的數(shù)據(jù)復(fù)制到新的空間中去，

deque不會(huì)這么做,，它會(huì)去另外開辟一塊連續(xù)空間去存放數(shù)據(jù),，所以存儲(chǔ)效率方面deque高于vector,但deque又不同于鏈表，它可以說是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的一個(gè)折中方案把，今天我寫了段代碼,，是這樣的結(jié)構(gòu)

vector<SerializedEntity> archiveEntities; //也許你要問問什么不用vector<SerializedEntity*>,，我這里比較特別，因?yàn)橐x寫磁盤的數(shù)據(jù),，序列化存儲(chǔ)                                            //回避了指針的數(shù)據(jù)讀寫方式,，所以用的vector<SerializedEntity>
那么：Entity * ent = &archive[0];          //看似沒問題,其實(shí)里面暗藏殺機(jī)
這個(gè)archiveEntities 如果不改變是沒有問題，但如果序列集又動(dòng)態(tài)添加了數(shù)據(jù),，恰好沒有預(yù)留空間,，那么將導(dǎo)致整個(gè)集合重新分配連續(xù)空間了，所以那個(gè)引用也將“失效了”,，這讓我很頭疼,，這個(gè)時(shí)候讓我想起了deque，它真的很棒,，不會(huì)去重整空間,，需要的時(shí)候再開辟其他連續(xù)的空間，雖然讀的效率降低了,，但
這點(diǎn)損失對(duì)于我的程序基本可以忽略不計(jì)的,，IO數(shù)據(jù)本身就很少去遍歷訪問，卻能給程序很好的去“引用”,，不用擔(dān)心引用失效的情況,，這方面deque確實(shí)是個(gè)很好的選擇

找到一篇文章與大家分享一下，也是應(yīng)證我的觀點(diǎn)的：

operator[]

　　operator[] 是指通過下標(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)存訪問,。

　　空間性能分析

　　push_back

　　vector

　　很不幸,，如果 vector 采用 N*2 的內(nèi)存增長(zhǎng)模型(通常如此)，那么在最差的情況下,，空間復(fù)雜度就是 2*N ,，最好的情況下為 N(所有的內(nèi)存都用上了)。平均來講,，空間復(fù)雜度為 1.5*N .也就是說,，通常差不多有一半的內(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.也就是說最差情況下只浪費(fèi)了 N/256 的內(nèi)存,。

　　deque的其他特性

　　元素地址不變

　　由于 deque 并不進(jìn)行數(shù)據(jù)搬移，帶來一個(gè)有意思的特性,，就是 deque 的元素地址在只有 push_back/push_front,，沒有 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ì)有任何問題,。

 

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 的時(shí)間,、空間性能對(duì)比，我們可以看出,，應(yīng)該提倡盡可能使用 deque 這個(gè)容器,。特別是，如果要承受海量數(shù)據(jù),，deque 是最合適的人選了,。