由来

在最近的项目中，我需要用到一个能设置固定长度的优先级队列，查了一下知名的第三方库，没有找到合适的，于是，决定自己写一个。

需要的功能主要是：

  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中的分配器：