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

时间:2022-11-02 无水先生人气:0

提要

库 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 更有效地管理内存，因此在某些情况下可能是更好的选择。例如，如果您需要一个大容量的循环缓冲区，它可能是一个不错的选择，但您的程序并不总是使用完整的缓冲区。

加载全部内容