迭代器失效规则是否意味着线程安全？

Question

Here in this Stack Overflow answer列出了C++11中标准容器的迭代器失效规则。特别是，有 insertion:

[multi]{set,map}：所有迭代器和引用不受影响[23.2.4/9]
unordered_[multi]{set,map}：当重新哈希发生时所有迭代器都失效，但引用不受影响 [23.2.5/8]。如果插入不会导致容器的大小超过 z * B，则不会发生重新散列，其中 z 是最大负载因子，B 是当前桶数。 [23.2.5/14]

擦除:
[multi]{set,map}和unordered_[multi]{set,map}：只有对被擦除元素的迭代器和引用无效

这些规则是否意味着我可以在一个线程中安全地进行插入和擦除，并在另一个线程中安全地访问，查找（使用 find）元素，只要这些元素不是被插入的元素和在第一个线程中删除，并确保没有发生重新散列？

如果不是，这些规则的确切含义是什么？

Answer 1

容器的元素的迭代器不会失效这一事实绝不意味着容器本身的线程安全。例如，size 成员变量需要以原子方式修改，这与在 insertion/deletion.

上无效（或不无效）的迭代器完全不同。

tl；博士；编号

这些规则只是告诉您元素的迭代器何时因操作而失效。例如，当向量调整大小时，底层数组会重新分配到别处，因此如果您有一个指向元素的迭代器（或指针），它在调整大小后将不再有效（因为它将指向旧数组的已删除元素).

Answer 2

使用find意味着遍历，至少遍历元素的一个子集。 insert 和 erase on [multi]{set,map} 导致重新平衡底层树，这会影响节点之间的链接。如果重新平衡与 find 同时发生，就会发生不好的事情。

如果您在 unordered_[multi]{set,map} insert 或 erase 期间尝试 find，同样会发生不好的事情。 insert 会导致重新散列。 insert 和 erase 都需要 link/unlink 列表中的元素。如果 find 在 link/unlink 期间搜索列表，你就输了。

[unordered][multi]{set,map} 上的

[] 是 "find and insert if not found" 上的 shorthand。对于 find，at 是 shorthand。所以不，这些也不安全。

如果您在 [multi]{set,map} 中有一个现有的迭代器，您可以在插入或删除另一个元素时继续取消引用（但不是 increment/decrement）该迭代器。对于 unordered_[multi]{set,map}，仅当您可以保证在插入时不会发生重新散列（它永远不会在擦除下发生）时，这才是正确的。

Answer 3

在 C++ std 容器上有两种操作。 Reader 和 Writer 操作（这些不是标准使用的术语，但这样读起来更容易）。另外还有对容器中元素的操作

const 方法是 Reader 方法，"lookup" 函数也是 const 因为它们 return 是非 const 对元素（或类似元素）的引用。标准中有完整列表，但常识应该有用。 vector::operator[]、begin()、map::find()都是"Readers"。 map::operator[] 是 而不是 一个 "Reader"。

您可以让任意数量的线程同时参与 Reader 操作，没问题。

如果您有任何线程参与 Writer 操作，不会对容器进行其他访问。

您不能安全地同时拥有一个Reader和一个Writer。如果您有任何 Writers，则必须排除所有其他访问权限。

您可以安全地同时拥有 1337 个读者。

对元素的操作有点相似，除了写入一个元素只需要排除对该元素的其他访问。你有责任让你的 const 方法相互配合。（std保证容器的const方法只会调用元素的const方法）

请注意，在 std:: 关联容器中更改排序顺序是 UB，无需修改容器。

一个没有失效的迭代器，你只是对元素进行操作，（我相信）将算作对元素的操作。只需要对该元素进行同步。

请注意std::vector<bool>不遵循上述规则。

如果你违反了以上规则，C++std库不会阻止你。它只是说明存在竞争条件——也就是未定义的行为。任何事情都可能发生。在 C++ std 库中，如果您不需要某些东西，则无需为它付费：并且这些容器的单线程使用不需要同步的重量。所以默认情况下你不会得到它。

A std::shared_timed_mutex 或 std::experimental::shared_mutex 都可用于保证上述保持。 unique_lock 写作，shared_lock 阅读。对元素的写访问必须 shared_locked 在受保护的容器上，和以某种方式防止对同一元素的重叠访问而不会出现死锁。

迭代器失效规则与线程安全规则相对正交。

Answer 4

这里还有其他答案涉及 线程安全 问题。因此，如果这些规则并不意味着 线程安全 那我们还能做什么呢？

If not, what do these rules exactly mean?

他们会告诉您何时不能再使用迭代器。

让我们举一个（欺骗性的无辜的）例子：

auto v = std::vector<int>{....};
//v.reserve(...);

for (auto it = std::begin(v); it != std::end(v); ++it) {
   if (*it == ...)
     std::insert(it, ...);
}

这里你遍历一个向量，对于每个测试条件的元素，你在那个位置插入一些东西。

现在这个代码有效吗？迭代器失效规则告诉您，如果向量的容量足够大，则插入只会使插入位置之后的迭代器失效。所以如果你能证明 reserve （注释行）足够大，那么是的，代码是有效的。如果不是，则代码无效，因为 insert 使 vector 的所有迭代器无效，这意味着 it 无效，这意味着您不能再使用它了。您必须重新获取它：

auto idx = std::distance(std::begin(v), it);
std::insert(it, ...);
it = std::begin(v) + idx;

迭代器失效规则是否意味着线程安全？

Do the iterator invalidation rules mean thread safety?

c++

multithreading

std

c++11