使用線程對向量排序

Question

C++ STL中的向量是否可重入或線程安全？ 我可以使用兩個線程並在不使用互斥鎖的情況下在矢量的兩半上工作（在這種情況下排序）嗎？ 例如：

int size = (Data_List.size())/2; 

Thread A() 
{ 

................ // Do we need to lock Data_list with a mutex 
sort(Data_List.begin(),Data_List.begin()+size,cmp); 
} 

Thread B() 
{ 
....// Do we need to lock Data_list with a mutex 
sort(Data_List.begin()+(size+1),Data_List.end(),cmp); 
} 

我的問題是我們需要鎖定DATA_LIST的使用互斥訪問？

注意：cmp函數是一個常規的int比較函數。

Answer 1

只要線程在內存的不同區域工作，並且您的比較函數僅適用於該內存和局部變量，那麼您應該沒問題。從本質上講，通過分割線程之間的工作並僅讓線程工作在其一半數據上，可以「鎖定」表的每一半。

Answer 2

如果線程在矢量的不相交部分上工作，你不應該有任何問題。

Answer 3

對於各種算法的線程版本，您可以使用GCC的並行模式（如果使用GCC）。 http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html

Answer 4

從技術上講，這個標準說這些類不是線程安全的，所以如果你從[]運算符那樣設置數據，那麼從技術上講，這是對一個對象的多次寫入。另一方面，在c數組的單獨部分上操作是安全的......所以這裏似乎有衝突。如果你想吱吱作響，請把第一個元素的地址作爲一個c數組。這裏有很多答案說，只要你處在陣列的不同部分，這很好，儘管在很多實現中這可能是對的

- >我認爲注意到一個實現是免費的並不能實現這一點很重要安全。

Answer 5

差不多，但不完全。這個代碼通常不是線程安全的，即使假設實現對vector的線程安全性做出了合理的保證。

假設Data_List::value_type是您的架構不提供原子訪問的類型。例如在x86上，字節寫和對齊的字和雙字寫是原子的，但短寫不是，用戶定義類型的寫入不是，除非它們碰巧是一個好的大小和對齊。如果您的UDT的大小爲3，則可能會出現問題。

要執行非原子短寫入，實現可能會執行兩個字節的寫操作。或者它可能會加載單詞，修改兩個字節，然後再寫回單詞。在字節寫入昂貴的架構上，後者是相當合理的。

現在，假設你的實現做了後者。進一步假設你對矢量的劃分恰好將一個單詞的前半部分放在一個部分中，而將另一半放在另一個單詞中。最後假設兩個不同的線程都試圖同時修改該字。這可能會出錯 - 他們可能會讀取相同的值，都會對其進行修改，但是之後會發生一次回寫，因此其中一項修改將被覆蓋並丟失。

原子字節訪問默認情況下不是通用的，我懷疑任何實現默認情況下不會原子位訪問。所以即使其他矢量類型是安全的，一個vector<bool>也是一個可能的問題：你的矢量劃分可能會落在一個字節的中間。這並不是說你一般會用排序 bools，但還有其他操作可能會嘗試分解向量，或者你的代碼可能是通用的。

可以通常期望字的訪問是原子的（和在C或C++，int訪問）。但語言標準不能保證，因此sig_atomic_t。你說你的cmp是一個int比較函數，這表明也許你的向量包含整數。但是你可以使用int比較函數完美地比較短褲，所以我不知道。

你真正需要做的是非常仔細地檢查你的執行/平臺，看看它說關於安全地從多個線程訪問內存。對於int的矢量來說可能很好。