C++线程安全的双向链表

Question

对于我正在编写的应用程序,我需要上面的数据结构.我想知道是否有一个库已经实现了它,或者我是否必须自己编写它？

如果没有必要,我真的不想重新发明轮子.

我需要这种结构能够使用多个线程添加和删除项目,而不必在执行此操作时锁定整个结构.

Answer 1

可能会有,但我认为这是Java早期的经验教训之一 - 数据同步性通常不是容器的成员函数级别,而是上面的一步.您应该在访问非线程安全列表之前使用同步对象.

考虑:

ThreadSafeQueue tsq;
tsq.push_back(...); // add lots of data

...

// Find the first element that returns true for search_criteria(elem);
auto iter = tsq.find_if(search_criteria); 
// (1)                                  
if(iter != tsq.end()) // (2)
{
    tsq.erase(iter);
}

在此线程安全队列中,仍有两个"间隙",其中队列可由另一个线程更改.实际上,这些更改可能会使您的迭代器失效.现在比较:

Queue q;
q.push_back(...); // add lots of data

...

// Create some lock around a pre-existing mutex.
Lock lock(q_mutex);
// Find the first element that returns true for search_criteria(elem);
auto iter = q.find_if(search_criteria); 

if(iter != q.end())
{
    q.erase(iter);
}
// lock unlocks as it goes out of scope.

这里,因为锁具有更大的粒度,所以可以确保整个书面算法的一致性.