如何实现STL容器

发布时间:2022-03-19 10:18:00 作者:iii
来源:亿速云 阅读:123

这篇文章主要介绍了如何实现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;

}

这是一个很复杂的算法,相同的单向链表。不过即使大体比较一下,也能看出无锁队列的一些特征。在无锁队列中,我们可以找到如下描述:

关于“如何实现STL容器”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“如何实现STL容器”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注亿速云行业资讯频道。

推荐阅读:
  1. STL容器之map与hash_map
  2. STL: vector容器成员函数resize的作用

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

stl

上一篇:Go如何使用字节数组或缓冲区可以提升字符串连接的速度

下一篇:GO字符串底层就是一个字节数组的示例分析

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》