循环优先级队列
2019-11-06 16:00:58来源:博客园 阅读 ()
循环优先级队列
由来
在最近的项目中,我需要用到一个能设置固定长度的优先级队列,查了一下知名的第三方库,没有找到合适的,于是,决定自己写一个。
需要的功能主要是:
- 一个能存放对象的队列,支持push和pop
- 容量固定,可以配置
- 能自动排序
- 能够遍历
- 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,如果有人提出来,我非常感谢!
原文链接:https://www.cnblogs.com/zuofaqi/p/11808767.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 单调队列模板【附例题】 2020-05-05
- STL之queue 2020-04-08
- DSA_06:队列 2020-03-29
- 单调队列 2020-02-07
- 二叉树(四)二叉堆 2020-02-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash