共計 3211 個字符，預計需要花費 9 分鐘才能閱讀完成。
這篇文章主要介紹了如何實現 STL 容器的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇如何實現 STL 容器文章都會有所收獲，下面我們一起來看看吧。
無鎖對象（lock-free object）的正式定義如下 [Her91]：判斷一個共享對象是否為無鎖類型（非阻塞對象），就看它是否能確保一些線程在有限的系統步驟中完成某個操作，并且與其他線程的操作結果無關（即便其它線程操作沒有成功）。一個更加嚴格的非等待對象（wait-free object）是這樣定義的：判斷某個對象是否為非等待，就看每個線程是否是在有限的步驟中完成了在該對象上的操作。無鎖的條件是至少保證一個線程完成任務，而更苛刻的非等待條件則是要保證所有的線程都能成功完成任務。線性化（linearizability）在競爭數據結構上也有理論性的定義 [Her90]，作為一種標準，在驗證無鎖算法正確性方面，發揮著重要作用。簡而言之，算法是否為線性化的，就看算法完成之后的操作結果是否顯而易見，不言自明。舉個例子來說，只要插入函數完成，列表插入操作的結果就顯而易見的。聽起來很白癡，但沒有人能想出某個算法做了一個列表插入，卻不是線性化。再譬如，各種類型的緩存可能違反這種特性：我們先將一個新元素放入緩存中而非直接插入，接著命令其它線程“將該緩存中的此元素插入列表中”，直到此元素插入進去?；蛘咧挥挟斁彺嬷杏邢喈敂盗康脑貢r，我們才做一次插入。那么插入函數執行完畢，我們依舊不能保證此元素在列表中。可以確定的是，此元素遲早會被插入到列表中。
下面是一個非常簡單的代碼實現：
struct Node {
Node * m_pNext ;
};
class queue {
Node * m_pHead ;
Node * m_pTail ;
public:
queue(): m_pHead( NULL ), m_pTail( NULL ) {}
void enqueue( Node * p )
{
p- m_pNext = m_pTail ;
m_pTail = p ;
if ( !m_pHead )
m_pHead = p ;
}
Node * dequeue()
{
if ( !m_pHead ) return NULL ;
Node * p = m_pHead ;
m_pHead = p- m_pNext ;
if ( !m_pHead )
m_pTail = NULL ;
return p ;
}
};
甚至可以寫得更簡短一點，這就是無鎖 Michael Scott 隊列經典算法實現。它看起來就像入隊、出對方法（和壓棧、彈出的意思相同）。（代碼是 libcds 庫類 cds::intrusive::MSQueue 簡化版）
bool enqueue( value_type val )
{
node_type * pNew = node_traits::to_node_ptr( val );
typename gc::Guard guard;
back_off bkoff;
node_type * t;
while ( true ) {
t = guard.protect( m_pTail, node_to_value() );
node_type * pNext = t- m_pNext.load(memory_model::memory_order_acquire);
if ( pNext != null_ptr node_type * () ) {
// Tail is misplaced, advance it
m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed );
continue;
}
node_type * tmp = null_ptr node_type * () ;
if ( t- m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed ))
{
break;
}
bkoff();
}
++m_ItemCounter;
m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel,
CDS_ATOMIC::memory_order_relaxed );
return true;
}
value_type * dequeue()
{
node_type * pNext;
back_off bkoff;
typename gc::template GuardArray 2 guards;
node_type * h;
while ( true ) {
h = guards.protect( 0, m_pHead, node_to_value() );
pNext = guards.protect( 1, h- m_pNext, node_to_value() );
if ( m_pHead.load(memory_model::memory_order_relaxed) != h )
continue;
if ( pNext == null_ptr node_type * () )
return NULL; // empty queue
node_type * t = m_pTail.load(memory_model::memory_order_acquire);
if ( h == t ) {
// It is needed to help enqueue
m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release,
CDS_ATOMIC::memory_order_relaxed );
continue;
}
if ( m_pHead.compare_exchange_strong( h, pNext,
memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
{
break;
}
bkoff();
}
–m_ItemCounter;
dispose_node( h );
return pNext;
}
這是一個很復雜的算法，相同的單向鏈表。不過即使大體比較一下，也能看出無鎖隊列的一些特征。在無鎖隊列中，我們可以找到如下描述：
無限循環：稍后我們會嘗試執行這個操作，這是一個實現了原子性操作 compare_exchange 的典型模式；
局部變量的安全性（guards），需借助于無鎖算法中安全內存收回方法。本例中，為風險指針（Hazard Pointers）方法；
采用 C ++11 標準的原子性原語：load、compare_exchange 以及內存柵欄（memory fences）memory_order_xxx;
helping：一種廣泛存在于無鎖算法中的方法，特別是在一個線程幫助其它線程去執行任務場景中；
補償策略（functor bkoff）：這不是必須的，但可以在連接很多的情況下緩解處理器的壓力，尤其是多個線程逐個地調用隊列時。
關于“如何實現 STL 容器”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“如何實現 STL 容器”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注丸趣 TV 行業資訊頻道。
