如何实现STL容器

共计 3211 个字符，预计需要花费 9 分钟才能阅读完成。

这篇文章主要介绍了如何实现 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 容器”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注丸趣 TV 行业资讯频道。