std::forward_list::insert_after 线程安全

Question

在共享的 std::forward_list 中，如果多个线程保证永远不会使用相同的位置迭代器调用它，那么多个线程同时调用 insert_after 是否安全？这似乎是安全的，因为插入保证不会使其他迭代器无效，并且容器没有 size() 方法，但也许我遗漏了什么？

编辑：

我写了一个小的折磨测试程序，似乎运行在没有任何锁定的情况下在 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

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?

没有。这不安全...（无论如何）。

插入 std::list 将需要访问迭代器位置的 previous node 和 next node，以及列表的 size。

即使位置相距很远，std::list::size() 的简单事实也需要 常数时间 (C++11)。这意味着每次插入都会更新 std::list::size().

编辑：

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?

不安全。并且不推荐。没有一个 STL 容器被设计成线程安全的。

无论如何，让我们假设一些基本保证，让我们假设一个非常简单的 std::forward_list 版本： insert_after 修改迭代器指向的节点，以便该节点现在指向新插入的节点, 而新插入的节点指向下一个节点。因此，如果迭代器彼此相距至少两个节点并且您的分配器是 thread-safe.

，它只会是 "safe"

插图：

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

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

如你所见，C被读取和修改。 D 可能被读取，而 K 被插入。

为什么说"at least two nodes away"，我们拿一个节点的情况来说：假设两个线程想在C之后插入K，在M之后D分别为：

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

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

来自 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.

Answer 2

当另一个线程写入到列表时，甚至 read 操作都是 thread-safe（参见 here进一步解释）；所以：多次写入不是 thread-safe：

虽然在没有锁的情况下从列表中读取不会损坏列表，但如果在另一个线程正在读取列表时修改列表，则任一线程都可能损坏（即崩溃，或产生不正确的结果） ).

您需要某种锁定。期间.

std::forward_list::insert_after 线程安全

std::forward_list::insert_after thread safety

c++

multithreading

thread-safety

c++14

forward-list