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