std::forward_list::insert_after thread safety

Question

In a shared std::forward_list is it safe for multiple threads to call insert_after concurrently if they are guaranteed to never call it with the same position iterator? It seems like this could be safe given that insert is guaranteed not to invalidate other iterators, and the container has no size() method, but maybe I'm missing something?

Edit:

I wrote a small torture test program that seems to run fine in Clang without any locking:

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

I know this doesn't prove anything but it makes me hopeful that this is safe. I'm not sure I can use it without some confirmation from the standard though.

Answer 1

In a shared std::list is it safe for multiple threads to call insert concurrently if they are guaranteed to never call it with the same position iterator?

No. It wouldn't be safe...(No matter what).

Inserting into a std::list will require access to the previous node and next node to the iterator position, and the size of the list.

Even if the positions are far off each other, the simple fact that std::list::size() is required to be constant time (C++11). It means each insertion will update std::list::size().

---

Edit:

In a shared std::forward_list is it safe for multiple threads to call insert_after concurrently if they are guaranteed to never call it with the same position iterator?

It's not safe. and not recommended. No STL container was designed with thread safety.

---

Anyway, lets assume some basic guarantees, lets assume a very simple version of std::forward_list: insert_after modifies the node pointed to by your iterator so that the node now points to the newly inserted node, while the newly inserted node points to the next node. So its only going to be "safe" if the iterators are at least two nodes away from each other and your allocator is thread-safe.

Illustration:

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

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

As you can see, C is read and modified. D may be read, while K is inserted.

---

As to why I said "at least two nodes away", lets take the case of one node away: Assuming two threads want to insert K after C, and M after D respectively:

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

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

From cppreference:

When an evaluation of an expression writes to a memory location and another evaluation reads or modifies the same memory location, the expressions are said to conflict.