循环优先级队列
由来
在最近的项目中，我需要用到一个能设置固定长度的优先级队列，查了一下知名的第三方库，没有找到合适的，于是，决定自己写一个。
需要的功能主要是：
- 一个能存放对象的队列，支持push和pop
- 容量固定，可以配置
- 能自动排序
- 能够遍历
- ring buffer
因为，我通读过stl的源码，对stl容器比较熟悉，写一个类似的应该不难，节约时间。所以就仿照stl的list，写了一个这样的容器
源码地址：
实现
首先想到的思路就是用循环数组，事先申请好固定长度的对象数组，循环使用，类似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，如果有人提出来，我非常感谢！