c++ - Visual C++ 2010 中的 STL 映射实现和线程安全

Question

我知道只要不需要调整大小，就可以读取一些单元格并同时写入 STL vector 的不同单元格。我想知道在 Visual C++ 2010 中是否允许同时获取某些键的值并同时将新的键值对插入到 STL 映射中，如果我保证每个线程访问/插入不同的键。

来自 http://www.cplusplus.com/reference/map/map/operator[]/:

Data races:

The container is accessed, and potentially modified. The function accesses an element and returns a reference that can be used to modify its mapped value. Concurrently accessing other elements is safe. If the function inserts a new element, concurrently iterating ranges in the container is not safe.

也就是说，如果我插入一个新元素，我就不能遍历容器。问题是访问不同的元素是否需要遍历容器。那安全吗？

如果我保证容器的大小永远不会超过N，是否安全？然后也许 map 的内部数据结构可以预先分配并保持不变——就像 vector 的内部一样，只要不调整 vector 的大小。

我知道有可用的线程安全映射实现，但它们可能要慢得多，所以我想知道标准映射对我来说是否足够，因为我正在修改的代码是我的应用程序。

谢谢，迈克尔

Answer 1

I'm wondering if it's allowed to concurrently get values for some keys and in the same time inserting new key-value pairs to the STL map in Visual C++ 2010, if I guarantee that each thread accesses/inserts a different key.

不，这是不允许的。查找涉及内部数据结构的遍历(对于 std::map 内部表示的常见方法是 binary search tree，如 Red–black tree)。另一方面，插入修改内部结构。

如果同时查找和插入是线程安全的，那么每次访问，即使在单线程环境中，也会涉及操作的高同步成本，这与 C++ 原则相矛盾——“你确实为你不使用的东西付出了代价” .

Thread Safety in MSVC 2010 :

If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected. For example, given an object A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

也就是说，如果您在其他线程中的插入操作之前已经引用了元素 - 通过该引用访问元素是安全的，因为在内部重新平衡期间不会移动对象。

ISO C++11 23.2.4/9:

The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

---

MSVC 2012(但不是 MSVC 2010)有 concurrency::concurrent_unordered_map 关联容器(注意它是无序的，这使得它类似于 std::unordered_map ，即它需要键的散列和相等性而不是严格的弱排序):

The concurrent_unordered_map class is a concurrency-safe container that controls a varying-length sequence of elements of type std::pair<const _Key_type, _Element_type>. The sequence is represented in a way that enables concurrency-safe append, element access, iterator access, and iterator traversal operations.

---

Intel TBB图书馆有类似的容器 - tbb::concurrent_unordered_map :

Template class for associative container that supports concurrent insertion and traversal.