如何實現STL容器

這篇文章主要介紹了如何實現STL容器的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇如何實現STL容器文章都會有所收獲，下面我們一起來看看吧。

無鎖對象（lock-free object）的正式定義如下 [Her91]：判斷一個共享對象是否為無鎖類型（非阻塞對象），就看它是否能確保一些線程在有限的系統步驟中完成某個操作，并且與其他線程的操作結果無關（即便其它線程操作沒有成功）。一個更加嚴格的非等待對象（wait-free object）是這樣定義的：判斷某個對象是否為非等待，就看每個線程是否是在有限的步驟中完成了在該對象上的操作。無鎖的條件是至少保證一個線程完成任務，而更苛刻的非等待條件則是要保證所有的線程都能成功完成任務。線性化（linearizability）在競爭數據結構上也有理論性的定義[Her90]，作為一種標準，在驗證無鎖算法正確性方面，發揮著重要作用。簡而言之，算法是否為線性化的，就看算法完成之后的操作結果是否顯而易見，不言自明。舉個例子來說，只要插入函數完成，列表插入操作的結果就顯而易見的。聽起來很白癡，但沒有人能想出某個算法做了一個列表插入，卻不是線性化。再譬如，各種類型的緩存可能違反這種特性：我們先將一個新元素放入緩存中而非直接插入，接著命令其它線程“將該緩存中的此元素插入列表中”，直到此元素插入進去。或者只有當緩存中有相當數量的元素時，我們才做一次插入。那么插入函數執行完畢，我們依舊不能保證此元素在列表中。可以確定的是，此元素遲早會被插入到列表中。

下面是一個非常簡單的代碼實現：

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容器”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。