C++线程安全双链表

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

注意:虽然接口和性能特性看起来像一个双链表,但在内部,这些结构非常复杂,基于哈希表或其他结构。没有任何东西可以在内部创建一个双链接列表,同时不受锁定。我不记得见过证据,但我认为这是不可能的。

Windows API single linked list instead . 添加use InterlockedPushEntrySList,删除use InterlockedPopEntrySList进行处理。

考虑:

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.

这会吗 http://www.boost.org/doc/libs/1_41_0/doc/html/boost/interprocess/message_queue.html 工作?

所以如果你能用锁,也许可以用这样的东西: Concurrent FIFO Queue with Boost