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

云霄網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),云霄網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為云霄上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站制作要多少錢，請找那個(gè)售后服務(wù)好的云霄做網(wǎng)站的公司定做！

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

下面是一個(gè)非常簡單的代碼實(shí)現(xiàn)：

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 ;

        }

};

甚至可以寫得更簡短一點(diǎn)，這就是無鎖 Michael&Scott 隊(duì)列經(jīng)典算法實(shí)現(xiàn)。它看起來就像入隊(duì)、出對方法（和壓棧、彈出的意思相同）。（代碼是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() ) {

                // 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() ;

          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() )

                 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;

}

這是一個(gè)很復(fù)雜的算法，相同的單向鏈表。不過即使大體比較一下，也能看出無鎖隊(duì)列的一些特征。在無鎖隊(duì)列中，我們可以找到如下描述：

• 無限循環(huán)：稍后我們會嘗試執(zhí)行這個(gè)操作，這是一個(gè)實(shí)現(xiàn)了原子性操作compare_exchange的典型模式；

• 局部變量的安全性（guards），需借助于無鎖算法中安全內(nèi)存收回方法。本例中，為風(fēng)險(xiǎn)指針（Hazard Pointers）方法；

• 采用C++11標(biāo)準(zhǔn)的原子性原語：load、compare_exchange以及內(nèi)存柵欄（memory fences）memory_order_xxx;

• helping ：一種廣泛存在于無鎖算法中的方法，特別是在一個(gè)線程幫助其它線程去執(zhí)行任務(wù)場景中；

• 補(bǔ)償策略（functor bkoff）： 這不是必須的，但可以在連接很多的情況下緩解處理器的壓力，尤其是多個(gè)線程逐個(gè)地調(diào)用隊(duì)列時(shí)。

關(guān)于“如何實(shí)現(xiàn)STL容器”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“如何實(shí)現(xiàn)STL容器”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。