文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2022-11-13 19:08

关注

提要

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

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

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯