由來
在最近的專案中，我需要用到一個能設定固定長度的優先級佇列，查了一下知名的第三方庫，沒有找到合適的，于是，決定自己寫一個，
需要的功能主要是：
- 一個能存放物件的佇列，支持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.uj5u.com/houduan/87978.html
標籤：C++
上一篇：Codeforces Round #595 (Div. 3)D1D2 貪心 STL
下一篇：Struct結構體