多线程访问一个std::map，会导致不安全行为吗？

Question

如果有多个线程访问一个映射对象，但是我可以确保这些线程中的任何一个访问都不会具有相同的键，并且访问方式就像这样：

//find value by key
//if find
// erase the object or change the value
//else
// add new object of the key

操作会导致同步问题吗？

- MIKU_LINK

Answer 1

是的，如果没有适当的同步，进行并发更新可能会导致崩溃，即使您的线程访问不同的键： std::map 基于树结构，树会重新平衡，因此您可能会导致写入看似不相关的键的父节点。

此外，同时进行只读访问和写入、或未锁定搜索+写入是不安全的：如果您有可能更新或删除节点的线程，则必须在写入前锁定所有读者。

- Sergey Kalinichenko

---

谢谢！你的回答让我对这个问题更加清晰了。 - MIKU_LINK

Answer 2

如果任何一个线程向树中插入数据，就会出现并发问题。STL map 使用红黑树实现（至少我熟悉的是这样——我不知道标准是否规定了红黑树）。插入时可能需要重新平衡红黑树，这将导致线程之间各种竞争。

只读访问（绝对没有写入操作）是可以的，但请记住，operator[] 不是只读的；它可能会添加新元素。您需要使用 find() 方法获取迭代器，并自行引用。

- Tim Ruddick

---

谢谢！看起来我必须添加同步锁来防止问题。 - MIKU_LINK

C++11并不强制要求底层数据结构（就像ISO C并不要求qsort是快速排序一样，尽管很多人可能会这么认为），但是映射通常被实现为红黑树。 - paxdiablo

Answer 3

除非文档（即ISO C++11标准）说明它是线程安全的（而它们没有），否则就是这样。结束了。它不是线程安全的。

可能会有一些std::map的实现允许这样做，但这绝不是可移植的。

地图通常建立在红黑树或其他自动平衡数据结构上，以便对结构进行修改（例如插入或删除键）将导致重新平衡。

您应该使用类似于互斥信号量的东西来包装地图上的读写操作，以确保正确完成同步。

- paxdiablo