C++中關於跨平台中子線程式控制制的一些心得(2)：用於線程的同步的Async容器

02-12

繼續上一篇，來說說用於線程同步的非同步容器。

以Async Queue為例子來說好了。

非同步容器本身實質性上是起到了用於多線程共享的內存池的作用。相比於一般的容器，其增加的部分其實就是在數據進出時對semaphore的操作

代碼部分基於前一篇的。

首先來說一下基礎：非同步容器進行容器操作的時候，需要兩個信號量配合操作。把這個兩個信號量分別命名為Sema_size和Sema_impl，那麼：

Sema_size用於告知當前容器內的元素數量，該值應該始終和容器的Size值相等。其作用在於，當從容器中嘗試彈出元素時，應該首先進行SemaWait(&Sema_size)以確保容器中有元素可供彈出。反之，當加入新元素時，則應該進行SemaPost(&Sema_size)來開放容器。對於Sema_size，可以使用mas size無上限的semaphore。

而Sema_impl則是用於在任何讀寫操作時對容器加鎖的mutex。任何對於容器的操作都必須對該mutex進行一次鎖定/解鎖。所以為了簡化，使用std::mutex即可。注意頭文件#include <mutex>

然後是基於heap的PriorityQueue

優先隊列不是stl中的標準容器，所以需要自己進行實現。

其基本思路就是以std::vector<pair<K,V>>為容器實現一個最小堆，通過二分查找來實現複雜度為o(LogN)的join和leave操作，o(1)的front操作和o(N)的foreach操作。

直接上代碼

std::vector<std::pair<K,V>> elements;void join(const K& key,const V& value){ elements.push_back(std::make_pair(key,value)); size_t cur = elements.size()-1; while(cur != 0){ size_t pIdx = (cur-1)/2; if(elements[pIdx].first > elements[cur].first){ std::swap(elements[pIdx],elements[cur]); cur = pIdx; }else{ break; } } } void leave(void){ size_t tail = elements.size()-1; size_t head = 0; std::swap(elements[tail],elements[head]); elements.pop_back(); if(elements.empty()){ return; } tail--; size_t left; size_t right; size_t cur; while(true){ left = head*2+1; right = head*2+2; if(left > tail){ break; }else if(right > tail){ cur = left; }else{ if(elements[left].first < elements[right].first){ cur = left; }else{ cur = right; } } if(elements[head].first < elements[cur].first){ break; } std::swap(elements[head],elements[cur]); head = cur; } }void traversal(std::function<void(K,V)> callback){ for(auto & p : elements){ callback(p.first, p.second); }}

然後有時間了再繼續，恩。