預(yù)備

隊(duì)列，是一種先進(jìn)先出（FIFO）的線性表，一般來(lái)說(shuō)會(huì)使用鏈表或者數(shù)組來(lái)實(shí)現(xiàn)它。

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

學(xué)術(shù)上說(shuō)它和堆棧常常被同時(shí)提起，因?yàn)槎褩Ｅc隊(duì)列幾乎一摸一樣，除了出棧時(shí)也在后端彈出元素，從而構(gòu)成了后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)。

古典的單向鏈表/單向隊(duì)列

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

毫無(wú)疑問(wèn)，這一定是代價(jià)很高的。

但這種方案的優(yōu)勢(shì)在于任何時(shí)候任何人都能夠隨手寫(xiě)得出來(lái)。也就是說(shuō)，它是最具備可手?jǐn)]性的一種實(shí)現(xiàn)方案，雖然出列代價(jià)較高，但對(duì)于相當(dāng)多的場(chǎng)景來(lái)說(shuō)那點(diǎn)代價(jià) CPU 根本不當(dāng)作是事。

雙向鏈表/雙向隊(duì)列

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

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

對(duì)于高頻交易場(chǎng)景來(lái)說(shuō)，雙向鏈表的指針維護(hù)操作是導(dǎo)致鎖開(kāi)銷(xiāo)的典型瓶頸，所以需要下力氣研究和解決鎖問(wèn)題。

一般來(lái)說(shuō)在現(xiàn)實(shí)世界中大家都是借助于 STL 來(lái)實(shí)現(xiàn)隊(duì)列算法及其應(yīng)用的。典型的例子是通過(guò) 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 的強(qiáng)健的基礎(chǔ)能力，我們實(shí)際上可以得到一個(gè)工程強(qiáng)度的有效的隊(duì)列模板類(lèi)。

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

所以，deque 的強(qiáng)大可見(jiàn)一斑。

不過(guò)，無(wú)論如何，我們有必要手寫(xiě)一份來(lái)完成自己的理解。在下面我們簡(jiǎn)單地實(shí)現(xiàn)了一份理論上的典型隊(duì)列方案：

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{};
 };

這是一份不采用智能指針的實(shí)現(xiàn)。因?yàn)橹悄苤羔樤谶@里只有壞處沒(méi)有好處。然而這就會(huì)使得這份實(shí)現(xiàn)顯得低級(jí)，很有趣吧，現(xiàn)代 C++ 在很多時(shí)候其實(shí)是扭曲了的，它雖然很現(xiàn)代，很時(shí)髦，但也很脫了褲子放屁。

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

所以我們的測(cè)試片段為：

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ù)我們的思考線路：

檢測(cè)隊(duì)列有否為空很重要，你不可能無(wú)代價(jià)地避免空訪問(wèn)，因?yàn)檫@是數(shù)據(jù)結(jié)構(gòu)本身的特性決定的。而在具體實(shí)現(xiàn)方面，上面之所以要做出那樣的約定，是因?yàn)槲覀儧](méi)有使用指針?lè)桨竵?lái)存儲(chǔ) T，所以你需要檢查 pop/peek 得到的 T 實(shí)例是否為空元素。或者，你在 pop/peek() 之前首先采用 empty() 進(jìn)行隊(duì)列非空判斷。

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

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

借助于共享指針的強(qiáng)力特性，很多時(shí)候我們無(wú)需在做容器實(shí)現(xiàn)時(shí)考慮太多的元素如何存儲(chǔ)的問(wèn)題，因?yàn)槟０宓囊粋€(gè)重要能力就是透明地引入中間層來(lái)提供額外的供給能力。這種時(shí)候，在這個(gè)例子里，中間層的智能指針包裝實(shí)際上提供了一種裝飾器的設(shè)計(jì)模式運(yùn)用機(jī)制。

所以，

我們認(rèn)為，在容器等數(shù)據(jù)結(jié)構(gòu)等實(shí)現(xiàn)部分，如果有可能，你應(yīng)該負(fù)起責(zé)來(lái)，自行處理 C++/C 指針的各種運(yùn)算，保證你的實(shí)現(xiàn)邊界之內(nèi)沒(méi)有泄漏問(wèn)題。這樣做的好處在于你的實(shí)現(xiàn)將會(huì)非?？勺x可維護(hù)，因?yàn)樗ǔＤ軌蚝屠碚撋系臄?shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)近似于等價(jià)，如同我們上面的實(shí)現(xiàn)一樣。

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

環(huán)形隊(duì)列

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

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

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

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

所以我這樣的人，一邊不爽 Golang 的簡(jiǎn)陋，一邊不也還是投入其懷抱了嗎——就因?yàn)樗軌驑O低代價(jià)的 ELF 化啊。程序員要干的事情就是簡(jiǎn)化這個(gè)世界。創(chuàng)造垃圾這樣的事是干不得的。

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

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

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

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

應(yīng)用

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

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

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

Conclusion

隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，總體上來(lái)說(shuō)非常簡(jiǎn)單，也不會(huì)牽涉到高深的數(shù)學(xué)證明，所以實(shí)現(xiàn)一個(gè)隊(duì)列往往會(huì)是初學(xué)者上手編程的好題目。

以上就是c++ 隊(duì)列相關(guān)知識(shí)總結(jié)的詳細(xì)內(nèi)容，更多關(guān)于c++ 隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論