title: OpenMP/__gnu_parallel for an unordered_map
body: <p>At some point in my code I have to make operations on all elements in an unordered_map. In order to accelerate this process I want to use openMP, but the naive approach does not work:</p>
  
  <pre><code>std::unordered_map&lt;size_t, double&gt; hastTable;
  
  #pragma omp for
  for(auto it = hastTable.begin();
      it != hastTable.end();
      it ++){
  //do something
  }
  </code></pre>
  
  <p>The reason for this is, that the iterator of an unordered_map is no random access iterator.
  As an alternative I have tried the __gnu_parallel directives working on for_each. But the following code</p>
  
  <pre><code>#include &lt;parallel/algorithm&gt;
  #include &lt;omp.h&gt;
  
  __gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair&lt;const size_t, double&gt; &amp; item)
                          {
                            //do something with item.secon
                          });
  </code></pre>
  
  <p>compiled with (gcc 4.8.2)</p>
  
  <pre><code> g++ -fopenmp -march=native -std=c++11
  </code></pre>
  
  <p>does not run parallel. Switching the unordered_map with a vector and using the same __gnu_parallel directive runs in parallel.</p>
  
  <p>Why does it not run in parallel in case of the unordered map? Are there workarounds?</p>
  
  <p>In the following I give you some simple code, which reproduces my problem.</p>
  
  <pre><code>#include &lt;unordered_map&gt;
  #include &lt;parallel/algorithm&gt;
  #include &lt;omp.h&gt;
  
  int main(){
  
  //unordered_map                                                                                                                                      
  std::unordered_map&lt;size_t, double&gt; hashTable;
  double val = 1.;
  for(size_t i = 0; i&lt;100000000; i++){
    hashTable.emplace(i, val);
    val += 1.;
  }
  __gnu_parallel::for_each (hashTable.begin(), hashTable.end(),[](std::pair&lt;const size_t, double&gt; &amp; item)
                          {
                            item.second *= 2.;
                          });
  
  //vector                                                                                                                                             
  std::vector&lt;double&gt; simpleVector;
  val = 1.;
  for(size_t i = 0; i&lt;100000000; i++){
    simpleVector.push_back(val);
    val += 1.;
  }
  __gnu_parallel::for_each (simpleVector.begin(), simpleVector.end(),[](double &amp; item)
                          {
                            item *= 2.;
                          });
  
  }
  </code></pre>
  
  <p>I am looking forward to your answers.</p>