boost::circular_buffer is on the way…
很多時候我們會用到緩沖區或者類似緩沖區的數據結構，如果能事先估計出數據量多大，并盡可能的節約內存，可以使用環形(邏輯上)結構的緩沖區。boost已經有了一個這樣的緩沖區,circular_buffer，由Jan Gaspar設計實現，它的數據結構跟傳統的靜態環形雙端隊列(很多數據結構書上有相關介紹)一樣，速度比傳統的靜態環形雙端隊列快得多。只不過我對它的表現還是不太滿意，覺得它還不夠快。為此，我設計了一個簡單的靜態環形雙端隊列，它的數據結構與circular_buffer沒什么兩樣，沒有編寫迭代器，也沒有給出太多公有成員函數，只不過它的速度要快一些。下面先來看看它的邏輯結構和物理結構圖。
圖(a)是靜態環形雙端隊列的邏輯結構圖，圖(b)是對應的物理結構圖。靜態環形雙端隊列有四個指針，指針start指向分配內存塊的起始地址處，finish指向該快內存的末尾，first和last是兩個自由指針，可以在[start, finish)區間自由移動，在隊頭添加一個元素時，first就向左移動一個元素的位置，在隊頭刪除一個元素時，first就向右移動一個元素的位置，在隊尾添加一個元素時，last向右移動一個元素的位置，在隊尾刪除一個元素時，last向左移動一個元素的位置。
開始時，指針first和last都指向同一個位置(我們的設計是指向[start, finish)區間的正中間)，當環形雙端隊列滿時last和first之間還剩一個元素的空位(如果不留空位怎么區分隊滿還是隊空？)。比較難處理的問題是指針first和last移動到隊頭和隊尾怎么辦，因為在物理上(在內存中存放元素時)一塊存儲空間的始末永遠都不會構成一個環，環行結構只能在邏輯上出現。
解決此問題的一種方法是取模，例如：first向左移動一個元素的位置：first = (first - 1 + cap) % cap; last向右移動一個元素的位置：last = (last + 1) % cap;其中first和last都是整形變量，cap是所開辟空間的大小，這就能很好的解決了環形移動指針的問題。這種傳統的算法形式上雖然比較簡潔，但是速度慢，因為取模需要做除法運算，以現在的CPU架構，做一次除法相當于做多次加法。
另外一種解決方案更容易理解，例如：當指針first移動到最左端時就讓它指向右端，移動到最右端時就讓它指向左端，當指針last移動到最右端時就讓它指向左端，移動到最左端時就讓它指向右端，這種算法速度快，因為做一次判斷需要的指令數跟做一次加法需要的指令數相差不多。
為了能夠區分何時隊滿何時隊空，環形隊列應該至少富裕一個元素的空間，也就是說我們將用last + 1 == first表示隊滿，用last == first表示隊空。
為了看看環形緩沖區的性能怎樣，做了一個簡單的測試，測試用系統配置如下。
操作系統: Windows XP Professional(內核版本5.1.2600), 英文版
CPU: Intel(R) PIII 1.13MHz, Moblie
編譯器: Code::Blocks(svn5616) + MinGW(g++4.4.0)
測試用數據: 32位的隨機數(由boost::mt19937產生)
測試數據量: 1千萬，測試時間單位: 毫秒
測試方法: 生成Release版(-O3)，運行5次取平均值，分別測試成員函數push_back+pop_front，push_back+pop_back，push_front+pop_back，push_front+pop_front耗費的時間。
測試結果見下圖。
由上圖(a)、(b)、(c)、(d)容易看出，boost::circular_buffer比普通的靜態雙端環形隊列快得多，但比靜態雙端環形隊列circular_deque慢很多。
傳統的環形隊列速度慢的主要原因是移動指針時需要取模，這很糟糕，因為取模需要做除法，計算機做一次乘法或除法運算比做一次加法耗費的CPU周期多很多，由于每移動一次指針都需要做一次取模運算，從而導致整體運行速度大大下降。
boost 1.42中的circular_buffer中成員函數push_front, push_back, pop_front, pop_back不夠快的主要原因是有太多的瑣碎操作，這些瑣碎的操作會消耗很多CPU周期，作者Jan Gaspar為何要這樣實現，本人不理解，我覺得沒有必要那樣做(請參考boost::circular_buffer的源代碼)。
如果您想看看各自的實現，circular_deque和circular_deque_traditional的源代碼可以從下面地址下載
http://m.shnenglu.com/Files/Chipset/circular_deque.zip