hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

轮回优先级行列

2019-11-18杂谈搜奇网78°c
A+ A-

由来

在近来的项目中,我须要用到一个能设置牢固长度的优先级行列,查了一下着名的第三方库,没有找到适宜的,因而,决议本身写一个。

须要的功用主假如:

  1. 一个能寄存对象的行列,支撑push和pop
  2. 容量牢固,可以设置
  3. 能自动排序
  4. 可以遍历
  5. ring buffer

由于,我通读过STL的源码,对stl容器比较熟习,写一个相似的应当不难,勤俭时刻。所以就模仿STL的list,写了一个如许的容器

源码地点:https://github.com/zfq559/ring_queue

完成

起首想到的思绪就是用轮回数组,事前请求好牢固长度的对象数组,轮回运用,相似vector,然则,增删的时刻,须要挪动元素,而且没法完成emplace函数了,写到一半,这个思绪就被烧毁了。因而,改用双向链表,如许,五个前提,都比较轻易满足,然则,假如内存不是一连的话,遍历的cache miss就比较高,因而就到场了内存池。

类定义为:

template <class T, uint32_t Size = 10, class Compare = std::less<T>>
class RingQueue;

个中,T为容器中寄存的数据范例,Size示意容器大小

元素节点定义成了如许:

template <class T> struct QueueNode { char data[sizeof(T)]; QueueNode<T> *prev{nullptr}; QueueNode<T> *next{nullptr}; };

STL中,data的范例是一个 T*。我这里之所以如许定义,为了只建立一个内存池对象,让内存尽量一连。

插进去元素运用的是插进去排序:

    Node *node = nullptr; for (node = dummy_->prev; node != dummy_; node = node->prev) { if (value_compare_(*(T *)node->data, value)) { break; } }

斟酌到,运用的时刻,更多情况下,按递次插进去元素,所以,这里寻觅插进去点的时刻,从后往前查找

推断行列是不是满,运用成员变量length_,假如插进去一个元素以后,行列凌驾Size大小了,删除头节点就可以了,由于头节点保留的是最小值:

    // if queue is full, delete head node
    if (length_ > Size) { Node *head = dummy_->next; _destroy((T *)head->data); // 析构节点中保留的对象 dummy_->next = head->next; // 删除节点 head->next->prev = dummy_; length_--; alloc_.PutNode(head); // 内存接纳 }

内存池也是相似STL中的分配器:

template <class T, uint32_t Num> class Allocator;

事前请求 (Num+2)*(sizeof(T)8字节对齐)的内存,每一个块,称为一个 pool,内存池自动扩容,不过最多请求10个 pool。不能自动削减容量

测试

运用 googletest 写了十几个用例,并和 std::list,std::set 作对照,在 win10/ubuntu18-x64/ubuntu16-armv8测试发明,这个容器机能是凌驾 std::set 的,更是凌驾了排序的 list

结语

TODO:须要到场 benchmark 和 profile。增添erase函数,删除指定节点

重要的特性就是上面所形貌的,个人不免有斟酌不到的处所,或许顺序有bug,假如有人提出来,我非常感谢!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
轮回优先级行列

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282412.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>