C++ Boost CircularBuffer算法超详细精讲

提要

库 Boost.CircularBuffer 提供了一个循环缓冲区，它是一个具有以下两个基本属性的容器：

• 循环缓冲区的容量是恒定的，由您设置。当您调用成员函数（例如 push_back()）时，容量不会自动更改。只有您可以更改循环缓冲区的容量。循环缓冲区的大小不能超过您设置的容量。
• 尽管容量不变，但您可以随时调用 push_back() 将元素插入循环缓冲区。如果已达到最大大小并且循环缓冲区已满，则将覆盖元素。

当可用内存量有限并且您需要防止容器任意增长时，循环缓冲区是有意义的。另一个例子是连续数据流，随着新数据的可用，旧数据变得无关紧要。通过覆盖旧数据自动重用内存。

要使用 Boost.CircularBuffer 中的循环缓冲区，请包含头文件 boost/circular_buffer.hpp。此头文件定义类 boost::circular_buffer。

示例 16.1。使用 boost::circular_buffer

#include <boost/circular_buffer.hpp>
#include <iostream>
int main()
{
  typedef boost::circular_buffer<int> circular_buffer;
  circular_buffer cb{3};
  std::cout << cb.capacity() << '\n';
  std::cout << cb.size() << '\n';
  cb.push_back(0);
  cb.push_back(1);
  cb.push_back(2);
  std::cout << cb.size() << '\n';
  cb.push_back(3);
  cb.push_back(4);
  cb.push_back(5);
  std::cout << cb.size() << '\n';
  for (int i : cb)
    std::cout << i << '\n';
}

boost::circular_buffer 是一个模板，必须用类型实例化。例如，示例 16.1 中的循环缓冲区 cb 存储 int 类型的数字。

循环缓冲区的容量是在实例化类时指定的，而不是通过模板参数。 boost::circular_buffer 的默认构造函数创建一个容量为零的缓冲区。另一个构造函数可用于设置容量。在示例 16.1 中，缓冲区 cb 具有三个元素的容量。

可以通过调用 capacity() 来查询循环缓冲区的容量。在示例 16.1 中，capacity() 将返回 3。

容量不等于存储元素的数量。虽然 capacity() 的返回值是常数，但 size() 返回缓冲区中元素的数量，这可能不同。 size() 的返回值始终介于 0 和循环缓冲区的容量之间。

Example16.1

示例 16.1 在第一次调用 size() 时返回 0，因为缓冲区不包含任何数据。调用 push_back() 三次后，缓冲区包含三个元素，第二次调用 size() 将返回 3。再次调用 push_back() 不会导致缓冲区增长。这三个新数字会覆盖之前的三个数字。因此，size() 在第三次调用时会返回 3。

作为验证，存储的数字会在示例 16.1 的末尾写入标准输出。输出包含数字 3、4 和 5，因为先前存储的数字已被覆盖。

示例 16.2。 boost::circular_buffer 的各种成员函数

#include <boost/circular_buffer.hpp>
#include <iostream>
int main()
{
  typedef boost::circular_buffer<int> circular_buffer;
  circular_buffer cb{3};
  cb.push_back(0);
  cb.push_back(1);
  cb.push_back(2);
  cb.push_back(3);
  std::cout << std::boolalpha << cb.is_linearized() << '\n';
  circular_buffer::array_range ar1, ar2;
  ar1 = cb.array_one();
  ar2 = cb.array_two();
  std::cout << ar1.second << ";" << ar2.second << '\n';
  for (int i : cb)
    std::cout << i << '\n';
  cb.linearize();
  ar1 = cb.array_one();
  ar2 = cb.array_two();
  std::cout << ar1.second << ";" << ar2.second << '\n';
}

Example16.2

示例 16.2 使用了其他容器中不存在的成员函数 is_linearized()、array_one()、array_two() 和 linearize()。这些成员函数阐明了循环缓冲区的内部结构。

循环缓冲区本质上类似于 std::vector。因为开始和结束的定义很好，所以可以将向量视为传统的 C 数组。也就是说，内存是连续的，第一个和最后一个元素总是在最低和最高的内存地址。但是，循环缓冲区不提供这样的保证。

尽管谈论循环缓冲区的开始和结束可能听起来很奇怪，但它们确实存在。可以通过迭代器访问元素，并且 boost::circular_buffer 提供了成员函数，例如 begin() 和 end()。虽然使用迭代器时不需要关心开始和结束的位置，但使用常规指针访问元素时情况会变得有点复杂，除非你使用 is_linearized()、array_one()、array_two()、和线性化（）。

如果循环缓冲区的开头位于最低内存地址，则成员函数 is_linearized() 返回 true。在这种情况下，缓冲区中的所有元素从头到尾连续存储在不断增加的内存地址中，并且可以像传统的 C 数组一样访问元素。

如果 is_linearized() 返回 false，则循环缓冲区的开头不在最低内存地址，示例 16.2 中就是这种情况。虽然前三个元素 0、1 和 2 完全按此顺序存储，但第四次调用 push_back() 将用数字 3 覆盖数字 0。因为 3 是调用 push_back() 添加的最后一个元素，它现在是循环缓冲区的新端。现在开始是编号为 1 的元素，它存储在下一个更高的内存地址。这意味着元素不再连续存储在不断增加的内存地址中。

如果循环缓冲区的末尾位于比开头低的内存地址，则可以通过两个传统的 C 数组访问元素。为了避免计算每个数组的位置和大小，boost::circular_buffer 提供了成员函数 array_one() 和 array_two()。

array_one() 和 array_two() 都返回一个 std::pair，其第一个元素是指向相应数组的指针，第二个元素是大小。 array_one() 访问循环缓冲区开头的数组，array_two() 访问缓冲区末尾的数组。

如果循环缓冲区被线性化并且 is_linearized() 返回 true，则也可以调用 array_two()。但是，由于缓冲区中只有一个数组，因此第二个数组不包含任何元素。

为了简化问题并将循环缓冲区视为传统的 C 数组，您可以通过调用 linearize() 强制重新排列元素。完成后，您可以使用 array_one() 访问所有存储的元素，而无需使用 array_two()。

Boost.CircularBuffer 提供了一个名为 boost::circular_buffer_space_optimized 的附加类。此类也在 boost/circular_buffer.hpp 中定义。尽管此类的使用方式与 boost::circular_buffer 相同，但它在实例化时不保留任何内存。相反，内存是在添加元素时动态分配的，直到达到容量为止。删除元素会相应地释放内存。 boost::circular_buffer_space_optimized 更有效地管理内存，因此在某些情况下可能是更好的选择。例如，如果您需要一个大容量的循环缓冲区，它可能是一个不错的选择，但您的程序并不总是使用完整的缓冲区。

到此这篇关于C++ Boost CircularBuffer算法超详细精讲的文章就介绍到这了,更多相关C++ Boost CircularBuffer内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！