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

圖(a)是靜態(tài)環(huán)形雙端隊(duì)列的邏輯結(jié)構(gòu)圖，圖(b)是對(duì)應(yīng)的物理結(jié)構(gòu)圖。靜態(tài)環(huán)形雙端隊(duì)列有四個(gè)指針，指針start指向分配內(nèi)存塊的起始地址處，finish指向該快內(nèi)存的末尾，first和last是兩個(gè)自由指針，可以在[start, finish)區(qū)間自由移動(dòng)，在隊(duì)頭添加一個(gè)元素時(shí)，first就向左移動(dòng)一個(gè)元素的位置，在隊(duì)頭刪除一個(gè)元素時(shí)，first就向右移動(dòng)一個(gè)元素的位置，在隊(duì)尾添加一個(gè)元素時(shí)，last向右移動(dòng)一個(gè)元素的位置，在隊(duì)尾刪除一個(gè)元素時(shí)，last向左移動(dòng)一個(gè)元素的位置。
開始時(shí)，指針first和last都指向同一個(gè)位置(我們的設(shè)計(jì)是指向[start, finish)區(qū)間的正中間)，當(dāng)環(huán)形雙端隊(duì)列滿時(shí)last和first之間還剩一個(gè)元素的空位(如果不留空位怎么區(qū)分隊(duì)滿還是隊(duì)空？)。比較難處理的問(wèn)題是指針first和last移動(dòng)到隊(duì)頭和隊(duì)尾怎么辦，因?yàn)樵谖锢砩?在內(nèi)存中存放元素時(shí))一塊存儲(chǔ)空間的始末永遠(yuǎn)都不會(huì)構(gòu)成一個(gè)環(huán)，環(huán)行結(jié)構(gòu)只能在邏輯上出現(xiàn)。
解決此問(wèn)題的一種方法是取模，例如：first向左移動(dòng)一個(gè)元素的位置：first = (first - 1 + cap) % cap; last向右移動(dòng)一個(gè)元素的位置：last = (last + 1) % cap;其中first和last都是整形變量，cap是所開辟空間的大小，這就能很好的解決了環(huán)形移動(dòng)指針的問(wèn)題。這種傳統(tǒng)的算法形式上雖然比較簡(jiǎn)潔，但是速度慢，因?yàn)槿∧Ｐ枰龀ㄟ\(yùn)算，以現(xiàn)在的CPU架構(gòu)，做一次除法相當(dāng)于做多次加法。
另外一種解決方案更容易理解，例如：當(dāng)指針first移動(dòng)到最左端時(shí)就讓它指向右端，移動(dòng)到最右端時(shí)就讓它指向左端，當(dāng)指針last移動(dòng)到最右端時(shí)就讓它指向左端，移動(dòng)到最左端時(shí)就讓它指向右端，這種算法速度快，因?yàn)樽鲆淮闻袛嘈枰闹噶顢?shù)跟做一次加法需要的指令數(shù)相差不多。
為了能夠區(qū)分何時(shí)隊(duì)滿何時(shí)隊(duì)空，環(huán)形隊(duì)列應(yīng)該至少富裕一個(gè)元素的空間，也就是說(shuō)我們將用last + 1 == first表示隊(duì)滿，用last == first表示隊(duì)空。
為了看看環(huán)形緩沖區(qū)的性能怎樣，做了一個(gè)簡(jiǎn)單的測(cè)試，測(cè)試用系統(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)
測(cè)試用數(shù)據(jù): 32位的隨機(jī)數(shù)(由boost::mt19937產(chǎn)生)
測(cè)試數(shù)據(jù)量: 1千萬(wàn)，測(cè)試時(shí)間單位: 毫秒
測(cè)試方法: 生成Release版(-O3)，運(yùn)行5次取平均值，分別測(cè)試成員函數(shù)push_back+pop_front，push_back+pop_back，push_front+pop_back，push_front+pop_front耗費(fèi)的時(shí)間。
    測(cè)試結(jié)果見下圖。


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