std :: forward_list :: insert_afterスレッドセーフ

Question

std::forward_list共有では、同じ位置イテレータで決して呼び出さないことが保証されている場合、複数のスレッドが同時にinsert_afterを呼び出すことは安全ですか？挿入が他のイテレータを無効にしないことが保証され、コンテナにはsize()メソッドがありませんが、おそらく私は何かを見逃していることを考えれば、これは安全かもしれないようです。

編集：

私はロックせずにクランで正常に動作すると思われる小さな拷問テストプログラムを書いた：

#include <forward_list> 
#include <iostream> 
#include <thread> 
#include <vector> 

using List = std::forward_list<int>; 
using It = List::const_iterator; 

void insertAndBranch (List& list, It it, int depth) 
{ 
    if (depth-- > 0) { 
     It newIt = list.insert_after (it, depth); 
     std::thread thread0 ([&]{ insertAndBranch (list, it, depth); }); 
     std::thread thread1 ([&]{ insertAndBranch (list, newIt, depth); }); 
     thread0.join(); 
     thread1.join(); 
    } 
} 

int main() 
{ 
    List list; 
    insertAndBranch (list, list.before_begin(), 8); 

    std::vector<It> its; 
    for (It it = list.begin(); it != list.end(); ++it) { 
     its.push_back (it); 
    } 
    std::vector<std::thread> threads; 
    for (It it : its) { 
     threads.emplace_back ([&]{ list.insert_after (it, -1); }); 
    } 
    for (std::thread& thread : threads) { 
     thread.join(); 
    } 

    for (int i : list) { 
     std::cout << i << ' '; 
    } 
    std::cout << '\n'; 
} 

私は、これは何も証明していませんが、それはこのように私が期待します知っています安全です。私は標準からいくつかの確認なしにそれを使用することができますか分からない。共有std::listで

Answer 1

は、それは彼らが同じ 位置イテレータとそれを呼び出すことはありませんが保証されている場合は、複数のスレッドが同時に挿入 をコールするために安全ですか？

いいえ...（何であれ）安全ではありません。

std::listに挿入すると、反復子の位置にprevious nodeとnext node、リストのsizeにアクセスする必要があります。

位置が互いに離れていても、std::list::size()は一定時間（C++ 11）である必要があります。つまり、挿入するたびにstd::list::size()が更新されます。

---

編集：共有std::forward_listで

は、それらが同じ位置イテレータと それを呼び出すことはありませんが保証されて同時に場合 コールinsert_afterに、複数のスレッドのために、それは安全なのですか？

安全ではありません。推奨されていません。スレッドセーフでSTLコンテナは設計されていませんでした。

---

とにかく、いくつかの基本的な保証とさせて頂きます、std::forward_listの非常に単純なバージョンとさせて頂きます：insert_afterは、ノードが今、新たに挿入されたノードを指すようにノードがあなたのイテレータによって指さ変更し、新たに挿入されたノード間次のノードを指します。したがって、イテレータが少なくとも2つのノードから離れていて、アロケータがスレッドセーフであれば、そのノードは「安全」になります。

イラスト：あなたが見ることができるように

Initial Forward_list 
A -> B -> C -> D -> E 

Insert K after C 
A -> B -> C x D -> E 
      \/
      K 

、Cを読み取って変更されます。 Dが読み込まれ、Kが挿入されてもよい。私は「2つ以上のノードを離れて」と述べた理由として

---

、離れて1つのノードの場合を取ることができます：それぞれ仮定すると、2つのスレッドがC後Kを挿入したい、とD後M：

Initial Forward_list 
A -> B -> C -> D -> E 

Insert K after C 
A -> B -> C x D x E 
      \/\/
      K M 

cppreferenceから：

式の評価は、メモリ位置とに書き込み別の評価で同じメモリ位置が読み込まれたり変更されたりすると、 という式は競合すると言われています。

Answer 2

さえ別のスレッドは（更なる説明のためにhereを参照）リストにを書き込むとき操作はスレッドセーフで読み;

ロックを解除してリストを読み込んでも、リストが破損することはありません。別のスレッドが読み込み中にリストが変更された場合、どちらかのスレッドが破損する可能性があります、または不正確な結果を生成する）。

ロックが必要です。期間。