时间戳

首页 > 解决方案 > 当我不添加/删除键时，我可以并行使用 std::map 吗？

c++ - 当我不添加/删除键时，我可以并行使用 std::map 吗？

问题描述

我有一个使用很多std::map结构的程序。现在我想将它们与多个线程一起使用，并假设插入或删除键可能会改变整个数据结构并并行破坏它。但是当我不添加新密钥时，应该没问题，对吧？

以下程序显示了我想要做的事情：

#include <omp.h>                                                                

#include <iostream>                                                             
#include <map>                                                                  

int main(int const argc, char const *const *const argv) {                          
  // Take a map and allocate the elements, but not fill them at this point.        
  std::map<int, int> map;                                                          
  int size = 10000;                                                                
  for (int i = 0; i < size; ++i) {                                                 
    map[i];                                                                        
  }                                                                                

  // Go through the elements in parallel and write to them, but not create any  
  // new elements. Therefore there should not be any allocations and it should  
  // be thread-safe.                                                               
#pragma omp parallel                                                               
  {                                                                                
    int const me = omp_get_thread_num();                                           
#pragma omp for                                                                    
    for (int i = 0; i < size; ++i) {                                               
      map[i] = me;                                                                 
    }                                                                              
  }                                                                                

  // Now all threads access all the elements of the map, but as the map is not  
  // changed any more, nothing bad should happen.                               
#pragma omp parallel                                                               
  {                                                                                
    int const me = omp_get_thread_num();                                           
    int self = 0;                                                                  

    for (int i = 0; i < size; ++i) {                                               
      if (map[i] == me) {                                                          
        ++self;                                                                    
      }                                                                            
    }                                                                              

#pragma omp critical(cout)                                                         
    std::cout << "Thread " << me << " found " << self << " entries.\n";            
  }                                                                                
}

然后我用以下代码编译它：

$ g++ -fopenmp -O3 -Wall -Wpedantic -g -fsanitize=address -o concurrent-map concurrent-map.cpp

这似乎适用于四个线程。如果我注释掉第一个 for 循环并让线程填充映射，它会因分段错误而崩溃，正如我所料。

当然，我不能std::map以我这样认为的方式证明它是线程安全的，但它至少不能证明是否定的。我可以std::map以这种方式并行使用吗？

标签： c++multithreading

解决方案

我不认为map[i]对于所有 C++ 实现来说，使用特别是线程安全的，即使它没有插入新元素。该标准不要求operator[]关联容器没有数据竞争：

C++17 标准草案的[container.requirement.dataraces]/1部分包含不应导致数据竞争的函数列表，即使它们不是const. 该列表包括findand at，但不包括operator[]。

因此，您需要使用findorat代替operator[]. 一个特定的实现可能会提供更强的保证，如果map[i]没有插入新元素，这可能是可能的，但您需要使用您的编译器/标准库文档进行检查。

除此之外，访问甚至修改容器的不同元素总是可以的（除了vector<bool>），请参阅标准中的下一段。

推荐阅读