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://www.cppblog.com/Files/Chipset/circular_deque.zip