循环缓冲区与Vector、Deque和List的性能比较
4.85/5 (18投票s)
报告C++容器类在各种操作上的性能
本文回顾了C++标准库序列容器在频繁操作上的性能，并考察了另一种容器类——环形或循环缓冲区——的性能，它有望在未来的C++版本中被纳入标准。
背景
在PC和手机中，内存访问主导了执行成本。内存访问源于获取执行指令，尤其是数据读写到内存。调用C++内存管理器分配和释放动态变量会执行许多指令，并对内存进行分散访问，这使得这些调用代价高昂。由于C++标准库容器类分配动态变量，因此在调优性能时了解它们的行为非常重要。
测量序列容器的性能
我的书《优化的C++》第10章讨论了C++标准库容器类的有效使用并比较了它们的性能。在书中，我报告了测量序列容器std::vector、std::deque和std::list（以及性能与std::list无法区分的std::forward_list）性能方面的实验结果。书中包含了该实验的许多细节。简而言之，我测量了在包含100,000个项的容器上，插入和删除、遍历、搜索和排序的时间成本。每个项都包含一个随机的空终止char[]键和一个int值。
当然，没有简单的测试能够捕捉性能的所有方面。绝对性能数字显然取决于测试结构、编译器版本、处理器和其他因素。然而，我发现，在相同测试条件下，一个容器相对于另一个容器的性能在不同处理器、编译器版本和操作系统上是一致的。因此，可以得出结论，一个容器执行任务的效率比另一个容器更高，甚至可以说高出多少。
对于本文，我在Microsoft的Visual Studio 2017上重新运行了这些实验。我还进行了新的实验，以测量序列容器在实现类队列行为时的性能。可作为队列使用的标准容器std::deque和std::list的性能受限于它们对动态分配变量的广泛使用。我使用另一个容器类boost::circular_buffer进行了额外实验，我期望它在实现队列时具有良好的性能。正如所料，circular_buffer在许多操作上的性能远远优于list或deque，并且通常与std::vector相当。C++标准委员会sg14小组委员会正在积极讨论将循环缓冲区容器添加到C++标准下一版本的提案。这使得循环缓冲区成为一种值得了解的数据结构。
本文报告的所有测试均在运行Windows 10的i7-4650平板电脑上进行，并在Visual Studio 2017中编译为32位发布版本，尽管我从Visual Studio 2010版本开始就有了经验。
队列作为标准数据结构的应用
队列是重要且经常使用的数据结构。队列是数据容器。它有两端，分别标记为前端和后端。数据从队列的后端插入，在队列中按顺序维护，并以与插入时相同的顺序从队列的前端移除。除了许多其他用途外，当数据的生产者和消费者异步操作时，队列会缓冲面向记录的数据。当树或图数据结构进行广度优先遍历时，队列会进行搜索排序。
适合实现队列的容器类必须保持插入项的顺序。（它必须是C++术语中的“序列容器”）。它必须具有高效的、最好是常数时间的函数，以便在一端插入项并从另一端移除项。标准C++容器类std::deque、std::list和std::forward_list具有这些属性。然而，令人惊讶的是，考虑到队列在代码中出现的频率，它们都不适合高效地执行此角色。另一种容器类型，即环形或循环缓冲区，目前不在C++标准库中，但提供了更高效的队列实现。
std::deque（deque是双端队列的缩写），顾名思义，似乎是实现队列的明显选择。Deque满足上述实现队列的要求。Deque是一个序列容器。在两端的插入和删除都是常数时间操作。Deque还具有一个有用的附加属性，即可以使用下标运算符以常数时间访问任何项，例如q[i]。Deque迭代器是随机访问迭代器，这使得deque可以使用std::sort()高效排序，并且排序后的deque可以使用C++标准库中的算法高效地进行二分查找。
不幸的是，std::deque的大部分行为依赖于隐藏的实现魔术。尽管下标是常数时间的，但此属性不足以暗示连续的deque项位于相邻的内存位置。Deque被实现为固定长度数组的变长数组；下标运算符会进行一些算术运算，以找到这些数组中下标的deque项的偏移量。C++标准在23.3.3.4节中包含关于迭代器失效的非常精确的语言，它将数组的数组实现写入标准，而没有实际描述它。因此，每次将一个项插入到deque的末尾时，可能会有零次、一次甚至两次调用内存管理器来分配内存。当一个项被移除时，可能会调用内存管理器来释放一个节点数组。
更糟糕的是，一些实现限制了固定长度项目数组的大小。对于足够大的项目，项目数组可能只包含一个项目。如果发生这种情况，每次项目插入都会调用内存管理器，使得deque在实现队列时与列表一样慢。最后，更改容量的deque成员函数会影响deque的后端。因此，deque并非真正的双端；在后端插入更有效率。
std::list（以及C++11之后的std::forward_list）满足实现队列的最低要求。它们是序列容器，在两端都具有常数时间的插入和删除操作。除了最低要求之外，list可以高效地排序，但是不能高效地搜索，并且list项不能使用下标符号进行访问。
std::list和std::forward_list有一个显著的弱点。它们被实现为动态分配节点的链表。每次插入一个项时，list都会从内存管理器获取一块内存，在此内存中构建一个包含插入项的新动态列表节点变量，并将其链接到列表中。每当移除一个项时，list都会销毁被移除的动态节点变量，并将该变量的存储返回给内存管理器。基于list和forward_list的队列之所以慢，是因为每次插入和删除都会调用内存管理器。
C++ 还提供了序列容器 `std::vector`，Bjarne Stroustrup 等著名专家将其誉为最有效的 C++ 容器类。vector 中的项存储在连续的内存位置，在遍历 vector 或插入项时提高了缓存局部性。与 `std::deque` 一样，vector 中的任何项都可以通过索引在常数时间内访问。vector 可以高效排序，排序后的 vector 可以高效搜索。尽管 vector 随着增长必须重新分配，但这种情况在均摊常数时间内发生。遗憾的是，vector 不适合实现队列，因为插入或删除项的时间成本仅在后端是常数。在前端是 O(n)；对于高效实现许多项的队列来说太慢了，尽管有一些部分解决方案。
还有另一种可以实现队列的数据结构。它被称为环形或循环缓冲区。C++17 中没有循环缓冲区，但 C++ 标准委员会 sg14 小组委员会正在积极开发一项提案。目前在 boost 中有一个实验版本。循环缓冲区的性能与 std::vector 具有竞争力，并且远优于 std::deque 或 std::list。
循环缓冲区 C++ 容器类
像 boost::circular_buffer 这样的循环缓冲区容器类的“规格表”可能如下所示：
-
序列容器
-
插入或删除：从前端或后端 O(1)，从其他位置 O(n)
-
索引时间：按位置，O(1)
-
排序：O(n log2 n)
-
搜索：如果已排序，O(log2 n)，否则 O(n)
-
当项被移除时，迭代器和对项的引用会失效。当项被插入到循环缓冲区的另一端且循环缓冲区已满时，迭代器和对循环缓冲区一端的项的引用会失效。当容量增加时，所有迭代器和引用都会失效。
-
迭代器是随机访问迭代器。
-
迭代器按从前到后或从后到前的顺序生成项。
-
固定容量数据结构
循环缓冲区类的接口看起来很像std::deque。它是一个序列容器，保留了项添加到或从循环缓冲区中移除的顺序。它有一个前端和一个后端，就像deque和std::list一样。项可以在两端以常数时间插入或移除。像deque或std::vector一样，项可以通过位置引用，使用下标符号如q[i]，在常数时间内，除了从一端到另一端迭代。像vector、list或deque一样，循环缓冲区有一个大小，即它当前包含的项数。像vector一样，它的容量是它可以在不调用内存管理器增加容量的情况下可以包含的最大项数。
当循环缓冲区的容量达到上限时，它的行为与 `std::deque`、`std::list` 或 `std::vector` 不同。当一个新项插入到循环缓冲区的一端，并且 `size = capacity` 时，循环缓冲区会首先移除另一端的项，然后插入新项，从而使循环缓冲区的 `size` 和 `capacity` 保持不变。相反，list、deque 和 vector 在插入元素时总是增加其 `size`，如果需要，还会对内存管理器进行代价高昂的调用以分配存储空间来增加容器的 `capacity`。
这种行为差异解释了循环缓冲区的性能优势。一旦最初构建完成，循环缓冲区从不重新分配其存储或复制元素。当一个项插入到任一端时，新元素会在循环缓冲区已拥有的存储中构建，并且一些指针会更新。当一个项从任一端移除时，该项被销毁，并且一些指针会更新。boost 提供的循环缓冲区确实允许用户明确命令更改其容量，这可能导致调用内存管理器、复制项以及引用和迭代器失效。
boost::circular_buffer 的实现类似于 std::vector，由一个动态元素数组组成。但与 vector 不同的是，循环缓冲区的前端与动态数组的基址不同。前端和后端可以指向数组中的任何位置。
循环缓冲区得名于其前端和后端指针以及有效迭代器的行为。当前端或后端指针，或循环缓冲区中的有效迭代器递增时，如果它已经指向动态数组的最后一个条目，它会重置为指向动态数组的基址，就像动态数组的末尾与基址相邻一样。当前端或后端指针，或有效迭代器递减时，如果它指向动态数组的基址，它会重置为指向动态数组中的最后一个项。
可以将循环缓冲区的实现想象成一个存储位置的环，其中前端和后端指针指向环中的任何位置，循环缓冲区中当前的项从前端顺时针延伸到后端。循环缓冲区中的项从前端到后端编号为索引 0, 1, 2, ... n-1，对于大小为 n 的循环缓冲区。如果 size ≤ capacity，则存在未使用的存储位置。
循环缓冲区的迭代器是随机访问迭代器，就像std::deque和std::vector的迭代器一样。这意味着缓冲区中的任何有效项都可以通过索引在常数时间内访问，并且两个迭代器之间的距离（即项数）可以在常数时间内计算。此属性足以允许循环缓冲区在O(n log2 n)时间内排序，并允许排序后的循环缓冲区在O(log2 n)时间内进行二分查找。虽然vector中两个迭代器之间的所有项都位于连续的存储位置，但循环缓冲区中两个迭代器之间的项仅是几乎连续的，最多只有一个间隙。当循环缓冲区的末尾递增超过循环缓冲区内部动态数组的末尾，并被重置为数组的基址时，就会发生这种情况。
在 boost::circular_buffer 中插入和移除
将项目插入容器的时间复杂度取决于在插入项目之前是否必须在容器中腾出空间。因此，例如，在 std::vector 的末尾插入项目可以在 O(1)（即常数时间）内完成。然而，要在中间插入项目，则需要复制所有后续条目以腾出空间供插入项目使用，因此是 O(n)。
boost::circular_buffer 的赋值
数据可以有多种方式插入容器。最简单的方法，通常也是最快的方法，是将一个容器实例赋值给另一个。下面的简单代码片段演示了赋值。
size_t size = ...
boost::circular_buffer<kvstruct> random_container(size),
test_container(size);
...
test_container = random_container;
一项重复将一个包含 100,000 个条目的循环缓冲区赋值给另一个循环缓冲区的实验耗时 1,525 毫秒。该时间分为 1,383 毫秒用于重复执行赋值操作，以及 151 毫秒用于在执行下一次迭代之前重复清除被赋值的循环缓冲区。
下表总结了循环缓冲区（标记为“ring”）与std::vector、std::deque和std::list在赋值操作上的性能。
| 环 | 向量 | 双端队列 | 列表 | |
| 赋值 | 1534 | 1162 | 10237 | 9389 |
| 赋值部分 | 1383 | 1050 | 7312 | 6724 |
| 删除部分 | 151 | 112 | 2925 | 2665 |
在赋值测试中，boost::circular_buffer比std::vector慢40%，但如接下来所示，这些时间很接近。circular_buffer比std::deque快5.3倍，比std::list快4.9倍。查看删除时间很有启发性。circular_buffer删除其100,000个条目比deque快19.4倍，比list快17.7倍。这意味着deque和list释放的内存块比circular_buffer多得多。
向 boost::circular_buffer 插入一系列条目
所有序列容器都定义了 `insert()` 成员函数的重载，该重载将由两个迭代器分隔的序列中的数据复制到由一个迭代器给出的容器中的位置。将数据插入到循环缓冲区末尾的代码如下所示：
std::vector<kvstruct> random_vector;
...
auto size = random_vector.size();
boost::circular_buffer<kvstruct> test_container(size);
...
test_container.insert(test_container.end(), random_vector.begin(), random_vector.end());
我进行了一项实验，反复将一个包含 100,000 个条目的向量插入到一个空的 boost::circular_buffer 的后端。该测试运行了 1,155 毫秒。如果减去之前测量到的清除循环缓冲区的时间，那么插入到后端所花费的时间是 1,004 毫秒。
下表总结了循环缓冲区（标记为“ring”）与std::vector、std::deque和std::list在将元素插入容器末尾时的性能。
| 环 | 向量 | 双端队列 | 列表 | |
.insert(end()) 来自向量迭代器对 | 1004 | 1074 | 7234 | 6493 |
相同，但带 reserve() | 1032 |
在此测试中，boost::circular_buffer 比 std::vector 快 7%，但考虑到测试设置，这已处于显著性的边缘。我会说两者的耗时非常接近。circular_buffer 比 std::deque 快 7 倍，比 std::list 快 6.5 倍。
将一系列项目插入到 `boost::circular_buffer` 的末尾是 O(n) 的，因为不需要移动其他项目来为插入的项目腾出空间。容器运行时间的差异可以清晰地归因于动态变量的分配。`circular_buffer` 从不分配。`std::vector` 在需要增长时会分配当前长度的倍数（通常在 1.5 到 2 之间）。`std::deque` 和 `std::list` 会分配与插入项目总数成比例的节点数量。
在任何其他位置插入可能更昂贵。容器boost::circular_buffer、std::vector和std::deque都是由动态数组构建的。当一个项插入到这种基于数组的容器的中间时，数组尾部所有项都必须复制（或移动）到新位置，以腾出空间供插入项使用。如果必须一次插入一个项，则插入范围的成本是O(n2)，这对于大型容器来说是一个大问题。
有一种优化可以使在基于数组的容器中间插入一系列项目变为 O(n)。如果该范围的迭代器是随机访问迭代器（就像我的测试中使用的 vector 的迭代器），那么这些迭代器之间的距离可以常数时间给出要插入的项目数量。该值可用于在一次操作中为所有项目腾出空间。如果迭代器是前向或双向迭代器，则可以通过计数在 O(n) 时间内计算距离。这仍然可能比一次插入一个项目更有效。如果迭代器是输入迭代器，则无法进行优化，成本仍为 O(n2)。
在std::deque的前端插入一个范围的成本是O(n)，因为单个项可以以常数时间推入deque。对于boost::circular_buffer来说，这种优化是可能的，但在boost版本1.62中没有实现。
在std::list中插入到处都是O(n)，因为每个节点都占用自己的动态变量，因此无需复制。这是list性能的少数亮点之一。
向 boost::circular_buffer 插入单个项目
`insert()` 的另一个重载是将单个项插入容器。对于所有序列容器，包括 `boost::circular_buffer`，当在后端插入时，此 `insert()` 重载是 O(1)，并且与 `push_back()` 具有相同的行为。
对于某些容器，在其他任何位置插入比其他容器更高效。std::vector的insert()成员函数必须复制插入点之后的所有项，以便为要插入的新项腾出空间，这使得该函数在前端插入项时为O(n)。在std::deque的前端插入是O(1)，但在中间插入是O(n)。在std::list中的任何位置插入都是O(1)，但查找插入位置通常是O(n)。boost::circular_buffer中的插入被定义为移动插入点之后的所有项以腾出空间，因此是O(n)。但是，可以通过特殊处理前端插入来提高此性能。
将项目插入到boost::circular_buffer后端的代码如下所示。该代码与上面插入到后端的代码类似，此处不再赘述。
std::vector<kvstruct> random_vector;
...
auto size = random_vector.size();
boost::circular_buffer<kvstruct> test_container(size);
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
test_container.insert(test_container.end(), *it);
一项重复将来自向量迭代器的100,000个项目插入到boost::circular_buffer后端的测试耗时1,826毫秒。先前的经验和多疑的本性促使我也测试了从下标向量插入。虽然这两个测试对于其他一些容器的性能差异显著，但从下标向量插入到循环缓冲区耗时1,778毫秒，差异不到3%。
我还进行了一项测试，以将项目插入到四个序列容器的前端。
下表总结了循环缓冲区（标记为“ring”）与std::vector、std::deque和std::list在前端和后端插入时的性能。我减去了每次循环迭代结束时删除数据结构的成本。
| 环 | 向量 | 双端队列 | 列表 | |
.insert(end()) 来自 vector[] | 1842 | 4662 | 11823 | 6566 |
.insert(end()) 来自向量迭代器 | 1523 | 4647 | 10945 | 6696 |
相同，但带 reserve() | 1614 | |||
.insert(begin()) 来自 vector[] | 8562849 | 4025888 | 11764 | 6890 |
.insert(begin()) 来自向量迭代器 | 9147849 | 4084888 | 13195 | 6745 |
std::vector 表现不佳。在 vector 的前端一个接一个地插入 100,000 个项目，比在后端插入要贵数千倍。std::deque 表现好得多。项目可以在 deque 的前端以常数时间插入。这是由于 std::deque 的数组的数组实现。std::list 是基于节点的，支持在任何位置以常数时间插入，在此测试中也表现良好。令人惊讶的是，boost::circular_buffer 表现得与 std::vector 一样差，尽管 push_front() 成员函数可以以常数时间推送到前端。显然，deque 实现了一种 boost::circular_buffer 1.62 版本没有的优化。
push_front() 和 push_back()
所有序列容器，包括 `boost::circular_buffer`，都提供了一个成员函数 `push_back()`，它能高效地（即在常数时间内）将项目放到容器的末尾。当能够高效地提供时，`push_front()` 将项目放到前端。`boost::circular_buffer` 可以在常数时间内 `push_back()` 和 `push_front()`。测试循环缓冲区 `push_back()` 的代码如下所示。将项目推到循环缓冲区前端的代码类似，此处不再赘述。
std::vector<kvstruct> random_vector;
...
auto size = random_vector.size();
boost::circular_buffer<kvstruct> test_container(size);
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
test_container.push_back(*it);
一项测试该代码的实验反复将一个包含 100,000 个条目的向量推送到循环缓冲区的末尾，耗时 1,225 毫秒。对于 push_front()，相应的时间是 1,286 毫秒。
下表总结了循环缓冲区（标记为“ring”）与std::vector、std::deque和std::list在push_back()和push_front()上的性能。
| 环 | 向量 | 双端队列 | 列表 | |
.push_back() 来自 vector[] | 1218 | 4539 | 6711 | 6759 |
.push_back() 来自向量迭代器 | 997 | 4724 | 6814 | 6635 |
相同，但带 reserve() | 1412 | |||
.push_front() 来自 vector[] | 1265 | 6588 | 6878 | |
.push_front() 来自向量迭代器 | 1212 | 6738 | 6641 |
经验告诉我，在进行优化时不要妄下结论，所以我尝试了两个版本的 `push_back()` 测试：一个使用向量迭代器，另一个使用下标向量。对于 `boost::circular_buffer`，使用下标向量的循环耗时延长了 22%。相比之下，在 `std::vector` 的 `push_back()` 测试中，使用向量迭代器的循环耗时延长了 4%。
boost::circular_buffer 完成 push_back() 测试的速度比 std::vector 快 3.7 到 4.7 倍，这几乎肯定是因为 circular_buffer 无需分配内存来增加容量。程序可以通过提前预留 vector 的容量来提高 vector 的插入性能，这样它的动态数组只需分配一次。公平地说，这正是 circular_buffer 构造函数的 size 参数所做的。当我测试这种优化时，circular_buffer 比 vector 快大约 50%。circular_buffer 在将项目推入后端或前端时，比 std::deque 和 std::list 快 5.5 到 6.5 倍。只有 vector 的性能具有可比性，而且只有在 vector 可以预分配的情况下。
std::vector 没有 push_front() 成员函数，因为将项目推到 vector 的前端效率不高。如以下代码片段所示，在开头插入会产生与 push_front() 相同的结果，但速度要慢得多。
std::vector<kvstruct> random_vector, test_container;;
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it)
test_container.insert(test_container.begin(), *it);
不幸的是，此操作在每次插入时都必须复制整个向量，以便为插入的项腾出空间。对于每个被推送的项，它是 O(n) 的，使得完整的测试是 O(n^2) 的。在向量前端插入 100,000 个项比在后端插入慢数千倍。
听过 Bjarne Stroustrup 关于倾向于使用 `std::vector` 以获得其优越性能的建议的开发人员，可能会不顾这一弱点而寻求使用 vector。如果可以一次从前端移除许多项目，则有一个范围 `erase()` 成员函数，其复杂度为 O(n)。如果可以一次在前端插入许多项目，vector 的范围 `insert()` 成员函数复杂度为 O(n)。当然，这只解决了一半问题。另一半问题是，将项目推到前端与插入一个范围不会产生相同的结果。如果一个程序将范围 [1, 2, 3, 4, 5] 插入到一个空 vector 中，则 vector 的内容将是 [1, 2, 3, 4, 5]。如果项目 1、2、3、4 和 5 被一个接一个地推到前端，则生成的 vector 将是 [5, 4, 3, 2, 1]。此问题可以使用要插入范围的反向迭代器来解决。生成的代码片段如下所示：
std::vector<kvstruct> random_vector, test_container;;
...
test_container.insert(test_container.begin(),
random_vector.rbegin(),
random_vector.rend());
此代码片段比boost::circular_buffer的push_front()测试慢14%。这是一个最佳情况结果，在实际应用中可能无法实现。因此，将std::vector强行用作队列是可能的，但为什么要这样做呢？circular_buffer仍然更快、更灵活、更易于使用。
在 boost::circular_buffer 中迭代
程序可以通过两种方式遍历循环缓冲区的元素：通过将其像原始数组一样进行索引，或通过递增迭代器遍历每个元素。直觉认为这些方法应该具有相似的性能，但经验促使我同时测试了这两种方法。
boost::circular_buffer<kvstruct> test_container(size);
...
unsigned sum = 0;
for (auto it=test_container.begin(); it!=test_container.end(); ++it)
sum += it->value;
boost::circular_buffer<kvstruct> test_container(size);
...
unsigned sum = 0;
for (unsigned i = 0; i < nelts; ++i)
sum += test_container[i].value;
此循环的下标版本（重复运行以使总时间可测量）耗时209毫秒。迭代器版本耗时154毫秒。在Visual Studio 2017中，基于迭代器的循环大约快36%。
下表总结了循环缓冲区（标记为“ring”）与std::vector、std::deque和std::list在迭代测试中的性能。
| 环 | 向量 | 双端队列 | 列表 | |
| 遍历容器（下标） | 226 | 215 | 1167 | |
| 遍历容器（迭代器） | 154 | 158 | 554 | 388 |
迭代在所有序列容器中都是高效的。尽管如此，boost::circular_buffer仍与std::vector具有竞争力，比std::deque快3.6倍，比std::list快2.5倍。
对 boost::circular_buffer 进行排序
C++标准库排序算法std::sort()和std::stable_sort()如果它们的迭代器参数是随机访问迭代器，则可以在O(n log2 n)时间内对容器进行排序。boost::circular_buffer的迭代器是随机访问迭代器。两种算法在已经排序的数据上运行速度都稍快。排序通过此程序片段完成：
size_t nelts = ...;
boost::circular_buffer<kvstruct> random_container(nelts),
sorted_container(nelts);
...
sorted_container = random_container;
std::sort(sorted_container.begin(), sorted_container.end());
下表总结了boost::circular_buffer（标记为“ring”）与std::vector、std::deque和std::list的排序性能。
| 环 | 向量 | 双端队列 | 列表 | |
sort() 容器 | 3337.9 | 2335.8 | 2968.5 | 3333.5 |
sort() 已排序容器 | 954.9 | 420.8 | 460.5 | 1301.5 |
stable_sort() 容器 | 2630.9 | 1981.8 | 2524.5 | |
stable_sort() 已排序容器 | 1231.9 | 978.8 | 970.5 |
std::list 的迭代器只是双向迭代器。在这种情况下，std::sort() 的时间复杂度为 O(n2)。幸运的是，list 有一个 sort() 成员函数，其时间复杂度为 O(n log2 n)。
在 boost::circular_buffer 中搜索
C++ 标准库包含的算法可以在 O(log2 n) 时间内搜索已排序的容器，如果它支持随机访问迭代器，所有序列容器都支持。以下程序片段在 sorted_container 中查找 random_vector 中的每个键。
std::vector<kvstruct> random_vector;
...
auto size = random_vector.size();
boost::circular_buffer<kvstruct> sorted_container(size);
...
for (auto it=random_vector.begin(); it!=random_vector.end(); ++it) {
kp = std::lower_bound(
sorted_container.begin(),
sorted_container.end(),
*it);
if (kp != sorted_container.end() && *it < *kp)
kp = sorted_container.end();
}
我进行了一项实验，重复查找已排序的 boost::circular_buffer 中的所有 100,000 个键。该实验耗时 3,264 毫秒。
下表总结了循环缓冲区（标记为“ring”）与std::vector和std::deque的性能。对于std::list，没有快速的搜索算法。
| 环 | 向量 | 双端队列 | 列表 | |
| 搜索容器 | 3580 | 2452 | 3729 |
boost::circular_buffer 作为队列
我的测试表明，std::vector 在插入和遍历方面比 std::deque 或 std::list 效率显著更高。然而，如前所述，std::vector 不太适合用作队列，因为插入和移除操作仅在后端是 O(1)。由于将每个项目复制到新的存储位置的成本，在 vector 前端插入或移除的成本要高数千倍。
我对boost::circular_buffer、std::deque和std::list进行了额外的测试，以查看循环缓冲区在用作队列时是否保持其相对于deque和list的性能优势。在测试中，我创建了一个包含20,000个条目的循环缓冲区。我通过向后端推入10,000个项目预填充它，然后开始为每个推入的项目从前端弹出一个项目，保持一个包含10,000个项目的队列。这要求循环缓冲区多次循环，从而充分发挥其行为的各个方面。当所有100,000个项目都被推入后，我从队列中弹出剩余的项目。我对deque和list重复了相同的测试，只是list或deque没有预留容量的机制。以下代码片段实现了针对circular_buffer的此测试。
std::vector<kvstruct> random_vector;
boost::circular_buffer<kvstruct> test_container(20000);
...
kvstruct popped(0);
auto nelts = random_vector.size();
auto it = random_vector.begin();
for (unsigned i = 0; i < nelts / 10; ++i) {
test_container.push_back(*it++);
}
while (it != random_vector.end()) {
popped = test_container.front();
test_container.pop_front();
test_container.push_back(*it++);
}
while (!test_container.empty()) {
popped = test_container.front();
test_container.pop_front();
}
下表总结了循环缓冲区（标记为“ring”）作为队列的性能，与std::deque和std::queue的比较。std::vector不适合用作队列。
| 环 | 向量 | 双端队列 | 列表 | |
push/pop 作为队列 | 1155 | 1848 | 8463 |
结果略微令人惊讶，但仍与之前的实验一致。循环缓冲区测试耗时 1,155 毫秒。std::list 的测试耗时 8,463 毫秒，是 boost::circular_buffer 的 7.3 倍，与之前的测试结果一致。
std::deque 的测试耗时 1,848 毫秒，比 boost::circular buffer 大约长 60%。考虑到循环缓冲区与 deque 在其他插入/删除任务上的相对性能，这有点令人惊讶。
分析与结论
boost::circular_buffer 在我书中的标准测试中的性能与 std::vector 相当，并且在相同测试中至少比 std::deque 或 std::list 快五倍。考虑到 circular_buffer 和 vector 实现之间的相似性，这并不令人惊讶。我还进行了测试，以评估 list、deque 和 circular_buffer 在用作队列时的性能。正如预期的那样，循环缓冲区优于 list 和 deque。
循环缓冲区是设计中放宽约束如何能够带来性能提升的一个例子。`std::vector` 有一个非常严格的约束，即程序可以在常数时间内获取指向存储按顺序排列项目的数组的指针。这个约束比两端常数时间推入和弹出、常数时间下标、常数时间距离计算或高效搜索和排序所需的约束更强。
boost::circular_buffer 的设计仅仅稍微放宽了此约束，使得生成原始数组的成本变为 O(n)，因为缓冲区条目可能需要移动才能在连续存储位置中生成。放宽此约束允许循环缓冲区在两端提供高效的插入和删除，同时保留高效的搜索、排序和索引。获取指向存储的裸指针并像原始数组一样使用此指针可能更昂贵，但此功能并非总是（甚至可能不经常）需要。与 vector 相比，放宽容器自动增长的约束是灵活性和性能之间直接的权衡。结果是，循环缓冲区可以完成 deque 的大部分功能，但具有 vector 的高效性能，并且可以完成 vector 的大部分功能，仅损失少量功能和性能。
历史
- 2017年4月27日：原始版本
- 2017年5月12日：小的格式调整