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.

这里因为锁的粒度比较大，所以可以保证整个写算法的一致性。