从并发关联容器中擦除 (concurrent_unordered_map)

Question

我正在寻找一个并发关联容器，我concurrent_unordered_map从 Thead Building Blocks 中找到了它似乎满足我的所有需求。即使我阅读了文档，我也没有找到一个关于擦除如何工作的例子。

A concurrent_unordered_map supports concurrent insertion and traversal, but not concurrent erasure. The interface has no visible locking. It may hold locks internally, but never while calling user-defined code. It has semantics similar to the C++11 std::unordered_map except as follows:

这实际上意味着什么？只要我仅从单个线程中擦除，从该地图中擦除是否安全？如果没有，我该怎么做？

Answer 1

并发映射标准化的提议解释了为什么并发容器没有erase. （搜索“为什么不支持并发擦除”部分。）

C++ 标准库中的容器负责删除它们的内容。内容“在”容器中，就像元素“在”数组中一样。 operator[]返回对所包含对象的引用，一旦返回引用，容器不知道请求线程将“挂起”引用多长时间。因此，如果另一个线程出现要求删除该元素，则容器不知道该元素是否可以安全删除。

我一直在想一些方法可以解决这个限制，但对擦除问题的解释带来了一个更大的问题：保护对存储在映射中的元素的并发访问始终是调用者的责任。

例如：假设您有一个并发映射 from inttofloat并且您执行以下操作：

thread A                   thread B
the_map[99] = 0.0;
                   ...
the_map[99] = 1.0;         if (the_map[99] == 1.0) ...  // data race!!!

这是数据竞争的原因是，即使表达式the_map[99]受保护，它也会返回一个引用，对它的访问不受保护。由于对引用的访问不受保护，因此只允许对引用指向的内存进行读取。（或者您需要锁定对该内存的所有访问）。

这是我能想到的最便宜的替代品（而且真的很贵）：

typedef concurrent_unordered_map<MyKey_t, atomic<MyMapped_t*> > MyContainer_t;

现在查找一个项目意味着：

MyMapped_t* x = the_map[a_key].load();

插入一个项目是：

the_map[a_key].store(ptr_to_new_value);

擦除一个项目是：

the_map[a_key].store(0);

并测试一个项目是否真的在地图中是：

if (the_map[a_key].load() != 0) ...

最后，如果您要进行任何类型的条件擦除（或修改），它必须比以下内容更复杂：

MyMapped_t* x;
do {
  x = the_map[a_key].load();
} while (condition_for_erasing(x) && !the_map[a_key].compare_exchange_strong(x, 0));

（以上是错误的，因为它存在 ABA 问题。）

即便如此：这仍然不能保护您免受对底层的同时修改，MyMapped_t并且需要您自己完成所有的构建、存储管理和销毁MyMapped_t。

:(