如何安全地在一个线程中执行映射操作，而不会使另一个线程中的迭代器无效？-解网

问：

我有两个线程在共享地图上运行。一个线程（名为线程 1）只是不断在映射中插入对。另一个线程（名为线程 2）不断获取地图的第一个元素，对元素执行一些操作，最后将其从地图中删除。线程 2 操作的元素是否恰好在线程 1 插入元素后恰好位于映射的开头并不重要。但是，线程 2 中的 map 元素不得因线程 1 的插入而失效。

我知道 STL 容器本身并不是线程安全的，但如果调整得当，它们仍然非常有用。因此，我的方法是每次线程 2 获取一个元素时，我都会复制数据并完成我的工作。此外，映射方法是通过使用作为成员存储的互斥锁上的lock_guard来使映射方法原子化。

C++17下的伪代码如下

my_map {
    insert(value_type value){
        lock_guard(mutex)
        map.insert(value)
    }
    erase(iterator position){
        lock_guard(mutex)
        map.erase(position)
    }
    end(){
        lock_guard(mutex)
        map.end()
    }
    begin(){
        lock_guard(mutex)
        map.begin()
    }
}

线程 1：

while(1){
    sleep(1)
    my_map.insert(random())
}

线程 2：

while(!my_map.empty()){
    auto it = my_map.begin()
    auto k = it->first;
    auto v = it->second;
    work(k, v);
    my_map.erase(it);
}

锁应防止映射本身因同时发生突变而失效。我担心的是地图操作如何影响地图的迭代器和元素。考虑以下顺序：

如果图片中的序列发生，行为会怎样？也就是说，线程 1 中的插入是否会以某种方式使无效，或者线程 2 中的插入是否无效（例如扰乱迭代器，因此不对应，或者破坏迭代器，因此无法检索）？itkvkvkv

有人告诉我使用地图的副本是线程安全的，但迭代器不行，所以它是正确的吗？我如何复制映射中的一个元素或其他一些 STL 容器以实现线程安全？

C++ STL

插入对线程 2 的迭代器/引用的影响

对于和其他有序关联容器，插入不会使容器迭代器（或元素引用）无效，因此线程 2 中的（和）不应受到线程 1 的影响。（注意：这完全是由于容器的标准行为，而不是锁。尽管锁确保在线程 1 中并且不会重叠，但它们不会影响线程 1 中的插入和线程 2 中通过迭代器访问的交互。对于无序容器（例如 std：：unordered_set 和 std：：unordered_map）来说，情况就不同了，如果迭代器必须重新散列，它们将使迭代器失效。std::mapitit->firstit-secondmy_map.insertmy_map.insert(...)my_map.begin()my_map.erase(...)

其他操作对线程 2 的迭代器/引用的影响

由于线程 1 的插入不会影响或，因此不需要制作本地副本。通过添加同步方法（调用 map：：extract，由 C++17 添加），提取可以成为原子（只要元素在工作完成时不需要保留在 map 中）：it->firstit->secondmy_map::extract

my_map::node_type my_map::extract(iterator position) {
    lock_guard<decltype(my_map::mutex)> lock(mutex);
    return map::extract(position);
}

void thread2() {
    while(! my_map.empty()){
        auto element = my_map.extract(my_map.begin())
        work(element.key(), element.value());
    }
}

但是，如果其他线程要从映射中删除元素，则必须确保线程 2 中的数据不受影响，因为线程 2 可能会在调用和之间中断，并且擦除可能会使传递的迭代器无效。这应该是线程 2 中唯一的关键点，因为早期和原子地从映射中查找和删除元素应该确保其他线程无法擦除节点本身（尽管线程 2 可能会影响其他线程中的迭代器和引用，这需要在它们自己的关键部分中解决）。my_map::beginmy_map::extract

防止擦除

复制或提取需要通过锁等方式进行保护，以防止擦除中断操作; 就有这样的锁。从另一个角度来看，删除和返回第一个元素完全是对的操作，因此可以成为方法。my_mapmy_map

在其他语言中，此操作称为或。有一些类似名称的 STL 容器方法（和），尽管它们删除了一个元素但不返回它，并且没有这样的方法。我们调用该方法：popshiftpop_backpopmapshift

my_map::node_type my_map::shift() {
    lock_guard<decltype(my_map::mutex)> lock(mutex);
    return map::extract(map::begin());
}

void thread2() {
    while(! my_map.empty()){
        auto element = my_map.shift()
        work(element.key(), element.value());
    }
}

请注意，关于返回的元素有一些注意事项：extract

对提取的元素的指针和引用仍然有效，但当元素由节点句柄 [] 拥有时不能使用：如果将元素插入容器中，则它们将变得可用。node_type

有关详细信息，请参阅“std：：unordered_map：：extract references/pointers invalidation”，但要点是您可以通过 node_type：：key（）和 node_type：：value（） 方法访问数据（包括分配给它们，这就是为什么有一个警告）。通常的问题是，如果其他线程引用了同一元素，并且通过节点句柄对其进行了修改（线程 2 不这样做，但仍需要采取措施以确保安全），则可能会导致其他线程出现问题。

shift上面的返回值有点漏水。这可以通过返回值类型来解决：

my_map::value_type my_map::shift() {
    lock_guard<decltype(my_map::mutex)> lock(mutex);
    auto node = map::extract(map::begin());
    return value_type(std::move(node.key()), std::move(node.value()));
}

thread2() {
    while(! my_map.empty()){
        auto element = my_map.shift()
        work(element.first, element.second);
    }
}

由于和返回左值，in 用于将这些值转换为右值，以便返回的对从节点抓取数据，而不是进行复制。node_type::key()node_type::value()std::movemy_map::shift

或者，锁可以将调用作为关键部分进行保护，但如果花费相当长的时间，这将降低性能。通常，复制/提取会减少代码的关键部分，因此其他线程不需要等待实际工作完成。workwork(...)

擦除对线程 1 的影响

由于线程 1 不对地图的元素（仅对地图本身）进行操作，因此线程 2 在这方面没有任何影响。即使线程 1 确实对迭代器或对中的项的引用进行了操作，擦除也只会使擦除的元素失效（如上所述，线程 1 需要防止这种情况发生）。my_map.erase(...)my_map

上一个：如何通过函数返回 map<int， variant> 的值？

下一个：std：：execution：：sequenced_policy有什么用？

如何安全地在一个线程中执行映射操作，而不会使另一个线程中的迭代器无效？

How can map operations in one thread be done safely, without invalidate iterators in another?

评论

插入对线程 2 的迭代器/引用的影响

其他操作对线程 2 的迭代器/引用的影响

防止擦除

擦除对线程 1 的影响