亲宝软件园·资讯

展开

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

无水先生 人气:0

提要

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

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

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

加载全部内容

相关教程
猜你喜欢
用户评论