如何在C++中迭代std::list，同时其他线程从中删除元素？

Question

我有一个多线程程序，其中一个线程正在迭代一个列表，只读取值，而第二个线程正在从中删除一些元素：

std::list<Type> items;

void* Thread1(void*)
{
    while(true)
        for(auto item = items.begin(); item != items.end(); ++item) {
            cout << item << std::endl;
            sleep(1);
        }
}

void* Thread2(void*)
{
    for(auto item = items.begin(); item != items.end(); ++item) {
        if(/*check some condition on item*/) {
            items.erase(item);
            break;
        }
    }
}

我不能在Thread1的整个for循环上放置互斥锁，因为该列表非常大，这会导致整个程序变慢。

此外，Thread2将被多次调用，我们无法确定何时会发生，而Thread1必须一直监视列表。

有没有一种线程安全的方法来迭代一个大小可以实时更改的列表，而不会得到分段故障、未定义行为或可能跳过某些元素？

- DarKreter

---

除了您已经发现的潜在竞态条件之外，您还需要注意std::list::erase中的“...被删除元素的引用和迭代器将失效...”这一点。如果删除线程和迭代线程位于同一元素上，则会使item失效。 - Richard Critten

简短回答：不行。std::list 不是线程安全的，需要进行某种形式的锁定。 - Sam Varshavchik

使用索引而不是迭代器的向量可能更安全（尽管您仍然很容易遇到未定义的行为）。 - Alan Birtles

@SamVarshavchik，哪种容器是线程安全的？如果我只需要在修改列表时进行锁定，那么应该在哪里放置互斥锁？我思考了一段时间，但我不知道如何使用信号量来安全解决它。 - DarKreter

C++库中的所有容器都不是线程安全的。在多线程环境下，使用任何容器时都必须锁定互斥量。如果这会导致问题，则需要重新设计类和容器，以实现可用的线程安全性。 - Sam Varshavchik

一般来说，任何可以称之为“容器”的东西本身都不是线程安全的。例如，如果查询容器中有多少元素，在获取结果后立即将其变得无效是完全可能的。线程安全是您在程序中设计的内容，而不是通过库添加的内容。选择适当的多线程实现强烈依赖于您的应用程序要执行的任务。“在修改时迭代”太低级了；您必须考虑到您的程序所做的所有事情，而不仅仅是您注意到的一个事情。 - Pete Becker

Answer 1

在调用erase（或任何其他修改函数）时，调用列表的任何其他成员函数都不能保证不会出现数据竞争，因此会导致未定义的行为。除此之外，另一个线程中的迭代器可能正好指向正在被删除的元素，而std::list没有提供任何保护或检测措施。

如果您不想锁定，则需要实现自己的无锁链表，使用原子指针来实现对数据竞争的保护。标准库没有这种类型的容器。它们在修改时都需要外部锁定。

- user17732522