引子
std::TextPool 基於 std::deque 實現。所以盡管本文討論 std::deque，但是所有的結論對 std::TextPool 同 樣有效。
實現概要
顧名思義，這是一個“雙向隊列（double-ended queue）”。這意味著從隊列開始 和結束處插入（刪除）數據的性能很好。為了達到這個目的，std::deque 基於一種分段連續的、介於數組和鏈表之間的數據結 構，示意如下：
template <class _E>
class deque
{
enum { BlockSize = 512 };
typedef _E Block[BlockSize];
std::vector<Block*> m_storage;
iterator m_first, m_last;
};
其中，iterator是deque::iterator類。其具體實現我們這裡不展開 討論，只是提示一點：這裡m_first, m_last就是容器的begin(), end()。之所以需要它們，是因為m_storage的第一個Block和 最後一個Block的數據可能沒有填滿，需要有指針去指出邊界。設想一下如果 我們只是要實現一個單向的隊列，那麼可以去掉這 裡的m_first成員（因為第一個Block如果它不同時是最後一個Block，則不會不滿）。
為什麼需要采用這種分段連續的數 據結構呢？答案是：性能。deque 平常很少為C++程序員所使用，但從容器的各方面的性能指標來看，實在不應該如此。可以說 ，deque 是 STL 中基於值的容器（它們包括：list/slist, vector, deque, basic_string等）中綜合性能最優的類。
下面我們仔細分析一下。
時間性能分析
push_back/push_front
這兩個操作對 deque 來說並無區別。而 vector 則不支持 push_front（因為性能很差而不提供）。我們對比各容器 push_back 性能。如下：
vector
vector::push_back 的性能具體要看 vector 的實現，主要關乎vector的內存增長模型。目前所見典型的 做法是N*2模型，也就是說在申請的內存填滿後，申請N*2字節的內存，這裡N為當前 vector占用的空間。在此情況下，元素搬移 的時間為 (1/N * N) = 1 為常數（其中1/N為平均搬移的次數，N為每次搬移的數據量），故此 push_back 的復雜度為 O(1)。 但這種做法時間性能是有了，空間存在巨大的浪費。但是如果增長模型為N+Delta模型（這裡Delta為一個常增長系數），那麼元 素搬移的時 間為 (1/Delta * N) = O(N)。空間是節約了，但時間性能極差。Erlang語言引入了一個很有意思的增長模型，是基 於 Fibonacci 序列，空間浪費要好於N*2模型，兼顧了空間性能和時間性能。
list
list::push_back 的性能為O (1)。主要的時間開銷為new Node時間。如果我們使用GC Allocator，list::push_back的速度非常快。
deque
deque::push_back 的性能接近O(1)。之所以不是O(1)，是因為 m_storage 滿了之後，會導致和 vector 一樣的內存搬移問題。假設 vector<Block*> 采用了 2*N 增長模型，那麼 deque::push_back 性能顯然是 O(1)。如果采 用 N+Delta 模型，那麼元素搬移時間為 (1/(BlockSize*Delta) * N/BlockSize) = O(N)。雖然也是 O(N)，但是一個是 N/Delta，一個是 N/(Delta*BlockSize*BlockSize)，還是差別很大。由於 m_storage.size() 通常很小，所以實際情況下哪怕 在海量數據情形下 deque::push_back 仍然表現良好。
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<Block*>也采用 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<int>，則這個代碼不會有任何問題。
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 是最合適 的人選了。
相關參考
std::vector：
http://cpp.winxgui.com/cn:std-vector
std::list：
http://cpp.winxgui.com/cn:std-list
std::TextPool：
http://cpp.winxgui.com/cn:textpool
