boost::circular_buffer is on the way…
很多時候我們會用到緩沖區(qū)或者類似緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)，如果能事先估計出數(shù)據(jù)量多大，并盡可能的節(jié)約內(nèi)存，可以使用環(huán)形(邏輯上)結(jié)構(gòu)的緩沖區(qū)。boost已經(jīng)有了一個這樣的緩沖區(qū),circular_buffer，由Jan Gaspar設(shè)計實現(xiàn)，它的數(shù)據(jù)結(jié)構(gòu)跟傳統(tǒng)的靜態(tài)環(huán)形雙端隊列(很多數(shù)據(jù)結(jié)構(gòu)書上有相關(guān)介紹)一樣，速度比傳統(tǒng)的靜態(tài)環(huán)形雙端隊列快得多。只不過我對它的表現(xiàn)還是不太滿意，覺得它還不夠快。為此，我設(shè)計了一個簡單的靜態(tài)環(huán)形雙端隊列，它的數(shù)據(jù)結(jié)構(gòu)與circular_buffer沒什么兩樣，沒有編寫迭代器，也沒有給出太多公有成員函數(shù)，只不過它的速度要快一些。下面先來看看它的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)圖。

圖(a)是靜態(tài)環(huán)形雙端隊列的邏輯結(jié)構(gòu)圖，圖(b)是對應(yīng)的物理結(jié)構(gòu)圖。靜態(tài)環(huán)形雙端隊列有四個指針，指針start指向分配內(nèi)存塊的起始地址處，finish指向該快內(nèi)存的末尾，first和last是兩個自由指針，可以在[start, finish)區(qū)間自由移動，在隊頭添加一個元素時，first就向左移動一個元素的位置，在隊頭刪除一個元素時，first就向右移動一個元素的位置，在隊尾添加一個元素時，last向右移動一個元素的位置，在隊尾刪除一個元素時，last向左移動一個元素的位置。
開始時，指針first和last都指向同一個位置(我們的設(shè)計是指向[start, finish)區(qū)間的正中間)，當(dāng)環(huán)形雙端隊列滿時last和first之間還剩一個元素的空位(如果不留空位怎么區(qū)分隊滿還是隊空？)。比較難處理的問題是指針first和last移動到隊頭和隊尾怎么辦，因為在物理上(在內(nèi)存中存放元素時)一塊存儲空間的始末永遠都不會構(gòu)成一個環(huán)，環(huán)行結(jié)構(gòu)只能在邏輯上出現(xiàn)。
解決此問題的一種方法是取模，例如：first向左移動一個元素的位置：first = (first - 1 + cap) % cap; last向右移動一個元素的位置：last = (last + 1) % cap;其中first和last都是整形變量，cap是所開辟空間的大小，這就能很好的解決了環(huán)形移動指針的問題。這種傳統(tǒng)的算法形式上雖然比較簡潔，但是速度慢，因為取模需要做除法運算，以現(xiàn)在的CPU架構(gòu)，做一次除法相當(dāng)于做多次加法。
另外一種解決方案更容易理解，例如：當(dāng)指針first移動到最左端時就讓它指向右端，移動到最右端時就讓它指向左端，當(dāng)指針last移動到最右端時就讓它指向左端，移動到最左端時就讓它指向右端，這種算法速度快，因為做一次判斷需要的指令數(shù)跟做一次加法需要的指令數(shù)相差不多。
為了能夠區(qū)分何時隊滿何時隊空，環(huán)形隊列應(yīng)該至少富裕一個元素的空間，也就是說我們將用last + 1 == first表示隊滿，用last == first表示隊空。
為了看看環(huán)形緩沖區(qū)的性能怎樣，做了一個簡單的測試，測試用系統(tǒng)配置如下。
操作系統(tǒng): Windows XP Professional(內(nèi)核版本5.1.2600), 英文版
CPU: Intel(R) PIII 1.13MHz, Moblie
編譯器: Code::Blocks(svn5616) + MinGW(g++4.4.0)
測試用數(shù)據(jù): 32位的隨機數(shù)(由boost::mt19937產(chǎn)生)
測試數(shù)據(jù)量: 1千萬，測試時間單位: 毫秒
測試方法: 生成Release版(-O3)，運行5次取平均值，分別測試成員函數(shù)push_back+pop_front，push_back+pop_back，push_front+pop_back，push_front+pop_front耗費的時間。
    測試結(jié)果見下圖。


    由上圖(a)、(b)、(c)、(d)容易看出，boost::circular_buffer比普通的靜態(tài)雙端環(huán)形隊列快得多，但比靜態(tài)雙端環(huán)形隊列circular_deque慢很多。
傳統(tǒng)的環(huán)形隊列速度慢的主要原因是移動指針時需要取模，這很糟糕，因為取模需要做除法，計算機做一次乘法或除法運算比做一次加法耗費的CPU周期多很多，由于每移動一次指針都需要做一次取模運算，從而導(dǎo)致整體運行速度大大下降。
boost 1.42中的circular_buffer中成員函數(shù)push_front, push_back, pop_front, pop_back不夠快的主要原因是有太多的瑣碎操作，這些瑣碎的操作會消耗很多CPU周期，作者Jan Gaspar為何要這樣實現(xiàn)，本人不理解，我覺得沒有必要那樣做(請參考boost::circular_buffer的源代碼)。
如果您想看看各自的實現(xiàn)，circular_deque和circular_deque_traditional的源代碼可以從下面地址下載
http://www.shnenglu.com/Files/Chipset/circular_deque.zip