C++线程安全双向链表

我正在编写的应用程序需要上述数据结构。我想知道是否有一个已经实现它的图书馆，或者我必须自己写这个图书馆吗？C++线程安全双向链表

如果没有必要，我并不想重新发明轮子。

我需要这个结构能够使用多线程添加和删除项目，而不必在此过程中锁定整个结构。

来源

2010-09-13 Tony The Lion

你会写什么样的操作，你真的从结构要求？也许你不需要双链表，其他结构也可以工作？ – Suma 2010-09-13 08:46:28

您希望线程安全吗？你想从任意线程写入任意位置？ – 2010-09-13 08:47:37

你需要多快的添加和删除？乍一看，它似乎是一个哈希表可能适合你。可扩展的线程安全哈希表很常见 - 只需搜索一些。 – Suma 2010-09-13 08:53:45

链接到相关的研究：Is a lock (wait) free doubly linked list possible?

当你没有请求无锁的容器，我不是标志着这是完全相同的副本。

注意：尽管接口和性能特征看起来像一个双链表，但内部这些结构非常复杂，基于散列表或其他结构。没有什么内部会有双重链接列表，并且可以同时锁定。我不记得看到一个证明，但我认为这是不可能的。

根据您的额外信息，我认为您根本不需要双链表。您可以使用Windows API single linked list instead。要添加使用InterlockedPushEntrySList，要删除处理使用InterlockedPopEntrySList。

来源

2010-09-13 08:43:02 Suma

是的！ InterlockedSLists速度非常快，已经内置于操作系统中 – 2010-09-13 16:21:18

可能有，但我认为这是在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.

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

来源

2010-09-13 08:46:47

请问这个http://www.boost.org/doc/libs/1_41_0/doc/html/boost/interprocess/message_queue.html的工作？

来源

2010-09-13 09:15:01

有许多关于使用汇编/编译器内在函数来执行原子操作来编写锁定空闲队列的论文，但实际上很难实现它。

所以，如果你可以使用锁，也许还可以利用这样的：Concurrent FIFO Queue with Boost

来源

2010-09-13 09:28:09