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