c++ 隊列相關(guān)知識總結(jié)

更新時間：2021年03月03日 09:18:25 作者：hedzr

這篇文章主要介紹了c++ 隊列相關(guān)知識總結(jié)，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下

預(yù)備

隊列，是一種先進先出（FIFO）的線性表，一般來說會使用鏈表或者數(shù)組來實現(xiàn)它。

隊列被允許從后端（rear）插入（insert）新元素，稱作入列（push，enqueue）；而從前端（front）彈出（pop）元素，稱作出列（pop，dequeue）。

學術(shù)上說它和堆棧常常被同時提起，因為堆棧與隊列幾乎一摸一樣，除了出棧時也在后端彈出元素，從而構(gòu)成了后進先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。

古典的單向鏈表/單向隊列

單向鏈表表示的隊列，出列時必須遍歷整個鏈表，直至鏈尾的前一位，然后摘除鏈尾來實現(xiàn)出列操作。

毫無疑問，這一定是代價很高的。

但這種方案的優(yōu)勢在于任何時候任何人都能夠隨手寫得出來。也就是說，它是最具備可手擼性的一種實現(xiàn)方案，雖然出列代價較高，但對于相當多的場景來說那點代價 CPU 根本不當作是事。

雙向鏈表/雙向隊列

雙向鏈表的好處是在鏈表頭尾的操作都是 O(1) 的，代價極低，可以視作毫無代價。但這是用額外的兩個指針的空間代價來達成的。對于像 std::deque<long> 這樣的雙向鏈表來說，每個鏈表元素的數(shù)據(jù)部分（payload）需要 8 bytes，而附著在 payload 上的指針則需要 16 bytes（典型的 64bit 計算時），相當于說超出數(shù)據(jù)實體兩倍的代價，不可謂不昂貴。幸而通常的實踐場景中很少會有這樣的實踐需求，往往更多的是一個 payload 的實體 struct 可能需要數(shù)百 bytes 甚至更多，這時候 16 bytes 就不算太起眼了。

雙向鏈表結(jié)構(gòu)的手寫，難點在于指針的同步修改，正確指向。

對于高頻交易場景來說，雙向鏈表的指針維護操作是導(dǎo)致鎖開銷的典型瓶頸，所以需要下力氣研究和解決鎖問題。

一般來說在現(xiàn)實世界中大家都是借助于 STL 來實現(xiàn)隊列算法及其應(yīng)用的。典型的例子是通過 deque：

#include <iostream>
#include <deque>
 
int main()
{
  // 創(chuàng)建容納整數(shù)的 deque
  std::deque<int> d{};
 
  // 約定 push_back 為入列操作
  d.push_back(13);
  d.push_back(25);
  d.push_back(7);
  d.push_back(2);
 
  // 約定 pop_front 為出列操作
  auto tmp = d.pop_front();
  std::cout << "FRONT: " << tmp << '\n';
 
  // 迭代并打印 deque 的值
  for(int n : d) {
    std::cout << n << '\n';
  }
}

得益于 deque 的強健的基礎(chǔ)能力，我們實際上可以得到一個工程強度的有效的隊列模板類。

同時，deque 也可以被毫無代價地實現(xiàn)強健的 Stack 數(shù)據(jù)結(jié)構(gòu)，僅僅是將出棧操作從上文的 pop_front 改為 pop_back() 即可。

所以，deque 的強大可見一斑。

不過，無論如何，我們有必要手寫一份來完成自己的理解。在下面我們簡單地實現(xiàn)了一份理論上的典型隊列方案：

template<class T>
 class ti_queue {
  public:
  struct element {
   T _data;
   element *_last;
   element *_next;
  };

  public:
  ti_queue() {
   _head = new element;
   _tail = new element;
   _head->_next = _tail;
   _tail->_last = _head;
  }
  ~ti_queue() {
   auto *p = _head;
   while (p != nullptr) {
    auto *t = p;
    p = p->_next;
    delete t;
   }
  }

  void push(T const &data) {
   auto h = _tail->_last;
   auto *ptr = new element{data, h, _tail};
   _tail->_last = ptr;
   h->_next = ptr;
  }

  T pop() {
   auto p = _head->_next;
   if (p == _tail) {
    return T{};
   }
   p->_last->_next = p->_next;
   p->_next->_last = p->_last;
   T t = p->_data;
   delete p;
   return t;
  }

  bool empty() const { return _tail->_last == _head; }

  T const &peek() const {
   if (empty()) return _tail->_data;
   return _tail->_last->_data;
  }

  private:
  element *_head{};
  element *_tail{};
 };

這是一份不采用智能指針的實現(xiàn)。因為智能指針在這里只有壞處沒有好處。然而這就會使得這份實現(xiàn)顯得低級，很有趣吧，現(xiàn)代 C++ 在很多時候其實是扭曲了的，它雖然很現(xiàn)代，很時髦，但也很脫了褲子放屁。

在這份實現(xiàn)中有一個重要的約定：我們認為你在提供 T 的具現(xiàn)類型時，你會隱含地約束零值初始化的 T 示例代表著空元素。所以當你 pop/peek 得到一個 T 實例時，如果它是零值將代表著隊列為空。

所以我們的測試片段為：

int main() {
 std::cout << '\n' << "queue: ";
 bet::ti_queue<int> tiq;
 tiq.push(31);
 tiq.push(17);
 tiq.push(19);
 tiq.push(73);

 auto tmp = tiq.pop();
 std::cout << tmp;

 while (!tiq.empty()) {
  tmp = tiq.pop();
  std::cout << ',' << tmp;
 }

 std::cout << '\n';
}

其結(jié)果應(yīng)該形如這樣：

queue: 31,17,19,73

OK，繼續(xù)我們的思考線路：

檢測隊列有否為空很重要，你不可能無代價地避免空訪問，因為這是數(shù)據(jù)結(jié)構(gòu)本身的特性決定的。而在具體實現(xiàn)方面，上面之所以要做出那樣的約定，是因為我們沒有使用指針方案來存儲 T，所以你需要檢查 pop/peek 得到的 T 實例是否為空元素。或者，你在 pop/peek() 之前首先采用 empty() 進行隊列非空判斷。

如果采用指針存儲方案的話，你可以順理成章地檢查 pop/peek 返回值是否 nullptr，這其實是 C/C++98 時代的典型實現(xiàn)方案。

如果是在 C++11 之后，盡管我們的實現(xiàn)有上述約定，但你也可以通過給 T 實例化為 std::shared_ptr<Real> 的方式來建立一個智能指針的緩沖層，因此你可以判斷該指針的非空性來鑒別返回值的非空性。

借助于共享指針的強力特性，很多時候我們無需在做容器實現(xiàn)時考慮太多的元素如何存儲的問題，因為模板的一個重要能力就是透明地引入中間層來提供額外的供給能力。這種時候，在這個例子里，中間層的智能指針包裝實際上提供了一種裝飾器的設(shè)計模式運用機制。

所以，

我們認為，在容器等數(shù)據(jù)結(jié)構(gòu)等實現(xiàn)部分，如果有可能，你應(yīng)該負起責來，自行處理 C++/C 指針的各種運算，保證你的實現(xiàn)邊界之內(nèi)沒有泄漏問題。這樣做的好處在于你的實現(xiàn)將會非?？勺x可維護，因為它通常能夠和理論上的數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)近似于等價，如同我們上面的實現(xiàn)一樣。

然而，如果你的目標是在面向兩個目標時則例外了：第一個目標是工程性的高性能線程安全性要求，此時應(yīng)該加上的鎖、優(yōu)化則取決于具體實現(xiàn)；第二個目標是用戶的使用簡便性，很顯然讓用戶直接具現(xiàn)他們的 T 而不是 shared_ptr<T> 是絕對有助于用戶的使用簡便性的，那么你就可能要在精打細算和借助智能指針方面做個選擇了。

環(huán)形隊列

此前，我其實在 Golang 針對高頻交易提出了一種無鎖環(huán)形隊列的實現(xiàn)方案，在那里使用了一種程序員直覺化的代碼編寫方法及直覺化的算法設(shè)計思路。事實上我個人偏好于那種直覺化的算法設(shè)計思路，我討厭搞委托交易，像 Spring framework 這樣的框架，在做無論什么的集成的時候如同脫了褲子放屁一般的老奶奶裹腳布似的做法，我鄙視之，所以我現(xiàn)在根本沒興趣討論 Java 的任何事情，這是被我判定了不值得的一種技術(shù)體系。

不過，RxJava 的思路是符合我的審美觀的。這才是對世界做抽象的正確態(tài)度。

那種頑固地拿著 XML 搞出一個龐大的 shit 堆的方法，我只能是表示敬而遠之。不但是 Java 的多數(shù)玩意如此地垃圾，.NET 畫界面 XAML，macOS XCode 畫界面的 Storyboard 統(tǒng)統(tǒng)都是毫無疑問的垃圾。任何和 XML 緊密捆綁的東西，沒說的，都是在創(chuàng)造垃圾。

那是一種將任何事情復(fù)雜化的思維模式，我拒絕的正是如此這般明顯愚蠢的模式。

所以我這樣的人，一邊不爽 Golang 的簡陋，一邊不也還是投入其懷抱了嗎——就因為它能夠極低代價的 ELF 化啊。程序員要干的事情就是簡化這個世界。創(chuàng)造垃圾這樣的事是干不得的。

所以，環(huán)形隊列在理論研究層面看，實際上就是一個數(shù)組，它是固定大小的，而后我們將其首尾相接（通過 put-pointer 和 get-pointer 自動回繞的方式），形成了抽象層面上的環(huán)形狀態(tài)。它的特點在于，當排除了分配每個元素的代價之后，它可以通過自己的固定緩沖區(qū)的特點來去除對象入列和出列時的潛在可能的復(fù)制開銷。

關(guān)于這一點，即使是充分利用 C++11 甚至 C++17 的現(xiàn)代語法，在借用 STL 來實現(xiàn)隊列的時候，你可能也往往無法避免出列時的復(fù)制開銷。如果考慮到高頻交易場景下想要避免鎖代價的影響的話，往往你可能連入列時的額外開銷也無法避免——只不過，很多時候鎖的代價更高過內(nèi)存分配已經(jīng)內(nèi)存復(fù)制的總線級代價，所以我們不得不兩害相權(quán)取其輕罷了。

為了解決這種特定的問題，一種方案是通過環(huán)形隊列來避免內(nèi)存分配問題；另一種則是自行構(gòu)造自己的隊列模板，通過專門的設(shè)計和實現(xiàn)來取得內(nèi)存分配、內(nèi)存復(fù)制與讀寫訪問、CPU Cache 等層面的鎖的問題等等的平衡。

再有一種方案，那就簡單了：用指針吧。鑒于 C++11 之后用裸指針被認為是跟不上時代的表現(xiàn)，所以：用智能指針吧。借助智能指針的移動語義或共享計數(shù)值技術(shù)，通?？梢暂^低代價地避免內(nèi)存反復(fù)頻繁分配以及內(nèi)存復(fù)制帶來的額外開銷問題。這種方案是有一點投機取巧，但是語言的基礎(chǔ)設(shè)施本就應(yīng)該提供給程序員以這樣的能力。反過來思考，如果一個程序員根本經(jīng)受不了 C 指針的蹂躪的話，他也不配被稱作程序員。話說今天這話也很沒意思，阿貓阿狗都是程序員的——劣幣正在驅(qū)逐良幣。

應(yīng)用

由于環(huán)形隊列是固定大小的，所以它極其適合這樣的場景：數(shù)據(jù)采樣工具，或者遙測場景。在數(shù)據(jù)采樣的場景，常常需要的是最最近幾十條記錄進行數(shù)學分析。當使用環(huán)形隊列來做相應(yīng)的數(shù)據(jù)緩沖時，老的數(shù)據(jù)不斷隨著插入指針的推進而被覆蓋掉，所以在取出指針一側(cè)總是最新的 N 條記錄，N 是環(huán)形隊列的預(yù)設(shè)大小。于是分析器可以面對這個環(huán)形隊列順利地提取到最新 N 條記錄用于計算和分析。

除此而外，我們還可以讓環(huán)形隊列的插入行為是非覆蓋的，于是當隊列滿時，插入操作就會在隊尾被阻塞，這是另一種環(huán)形隊列的應(yīng)用方式。

下幾期我將可能會考慮實現(xiàn)一份 C++ 版本的環(huán)形隊列，但這次可能不會做高頻版了，大約只會做適合毫秒級例如典型工業(yè) TCP 交易的版本。