我一直在寻找并发关联容器,我从 Thead Building Blocks 中找到了 concurrent_unordered_map
,它似乎可以满足我的所有需求。即使我阅读了文档,我也没有找到一个关于删除如何工作的例子。
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:
这到底是什么意思?只要我只是从一个线程中删除这张 map 是否安全?如果没有,我该怎么做?
最佳答案
proposal for standardization of concurrent maps解释为什么并发容器没有 erase
。 (搜索“为什么不支持并发删除”部分。)
C++ 标准库中的容器负责删除它们的内容。内容在容器“中”,就像元素在数组“中”一样。 operator[]
返回对包含对象的引用,一旦返回引用,容器就不知道请求线程将“挂起”引用多长时间。因此,如果另一个线程要求删除该元素,则容器不知道该元素是否可以安全删除。
我一直在尝试想出一些解决该限制的方法,但对删除问题的解释带来了一个更大的问题:它始终是调用者的责任以保护对存储在 map 中的元素的并发访问。
例如:假设您有一个从 int
到 float
的并发映射,并且您这样做:
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]
受到保护,它也会返回一个引用,对其访问不 protected 。由于对引用的访问不 protected ,因此只允许读取引用指向的内存。 (或者您需要锁定对该内存的所有访问)。
这是我能想到的最便宜的替代方案(而且它真的很贵):
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);
测试一个项目是否真的在 map 中是:
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));
(上面是错误的,因为它受到 the ABA problem 的影响。)
即便如此:这仍然不能保护您免受同时修改底层 MyMapped_t
的影响,并且需要您完成 MyMapped_t
的所有构造、存储管理和销毁是你自己。
:(
关于c++ - 从并发关联容器中删除 (concurrent_unordered_map),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16747498/