std :: forward_list :: insert_after безопасность потока

Question

В общем случае std::forward_list безопасно для нескольких потоков для вызова insert_after одновременно, если они не могут никогда называть его одинаковым итератором позиции? Кажется, что это может быть безопасным, учитывая, что вставка гарантируется, что не приведет к аннулированию других итераторов, а в контейнере нет метода size(), но, может быть, я что-то упустил?

Edit:

Я написал тестовую программу небольшой пытки, которые, кажется, прекрасно работать в Clang без блокировки:

#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'; 
} 

Я знаю, что это ничего не доказывает, но это заставляет меня надеяться, что это безопасно. Я не уверен, что могу использовать его без какого-либо подтверждения со стандарта.

Answer 1

В общем std::list это безопасно для нескольких потоков для вызова вставки одновременно, если они гарантированно никогда не называйте его с тем же позиции итератора?

Нет. Это было бы небезопасно ... (независимо от того, что).

Вставка в std::list потребуется доступ к previous node и next node в позиции итератора, а size списка.

Даже если позиции находятся далеко друг от друга, необходимо, чтобы std::list::size() был постоянным временем (C++ 11). Это означает, что каждая вставка обновит std::list::size().

---

Edit:

В общем std::forward_list это безопасно для нескольких потоков в insert_after вызовов одновременно, если они гарантированно никогда не называть его с той же позиции итератора?

Это небезопасно. и не рекомендуется. Контейнер STL не был спроектирован с безопасностью потока.

---

Во всяком случае, позволяет предположить некоторые основные гарантии, позволяет предположить очень простую версию std::forward_list: insert_after изменяет узел, на который указывает итератор так, что узел теперь указывает на вновь вставленной узел, в то время как вновь вставленной узел указывает на следующий узел. Таким образом, он будет только «безопасным», если итераторы будут расположены как минимум на два узла друг от друга, а ваш распределитель будет потокобезопасным.

Иллюстрация:

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

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

Как вы можете видеть, C чтения и модификации. D может быть прочитан, а вставлен K.

---

Как почему я сказал, «по крайней мере, два узла прочь», давайте случай одного узла в сторону: Если предположить, что два потока вставить K после C и M после D соответственно:

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 для дальнейших объяснений); поэтому: несколько записей не являются потокобезопасными:

Хотя чтение из списка без блокировки не приведет к повреждению списка, если список изменен, когда другой поток читает с него, либо поток может стать поврежденным (например, сбой , или произвести неверные результаты).

Вам нужен какой-то замок. Период.