title: OpenMP(C/C++): Efficient way of sharing an unordered_map<string, vector<int>> and a vector<int> between threads
body: <p>I have a for loop that I would like to make parallel, however the threads must share an <code>unordered_map</code> and a <code>vector</code>.</p>
  
  <p>Because the for loop is somewhat big I will post here a concise overview of it so that I can make my main problem clear. Please read the comments.</p>
  
  <pre><code>   unordered_map&lt;string, vector&lt;int&gt;&gt; sharedUM;
  
     /*
        here I call a function that updates the unordered_map with some
        initial data, however the unordered_map will need to be updated by
        the threads inside the for loop
     */
  
     vector&lt;int&gt; sharedVector;
    /* 
       the shared vector initially is empty, the threads will 
      fill it with integers, the order of these integers should be in ascending
      order, however I can simply sort the array after all the 
      threads finish executing so I guess we can assume that the order 
      does not matter
    */
  
     #pragma omp parallel for
     for(int i=0; i&lt;N; i++){
  
        key = generate_a_key_value_according_to_an_algorithm();
        std::unordered_map&lt;string, vector&lt;int&gt;::iterator it = sharedUM.find(key);
  
        /*
         according to the data inside it-&gt;second(the value), 
         the thread makes some conclusions which then
         uses in order to figure out whether 
         it should run a high complexity algorithm
         or not.
        */
         bool conclusion = make_conclusion();
  
         if(conclusion == true){
  
             results = run_expensive_algorithm();
  
            /*
               According to the results, 
               the thread updates some values of
               the key that it previously searched for inside the unordered_map
               this update may help other threads avoid running 
               the expensive algorithm
            */
  
         }
  
         sharedVector.push_back(i);
  
     }
  </code></pre>
  
  <p>Initially I left the code as it is, so I just used that <code>#pragma</code> over the for loop, however I got a few problems regarding the update of the <code>sharedVector</code>. So I decided to use simple locks in order to force a thread acquire the lock before writing to the vector. So in my implementation I had something like this:</p>
  
  <pre><code>      omp_lock_t sharedVectorLock;
        omp_init_lock(&amp;sharedVectorLock);
        ...
        for(...)
        ...
         omp_set_lock(&amp;sharedVectorLock);
         sharedVector.push_back(i);
         omp_unset_lock(&amp;sharedVectorLock);
        ...
        omp_destroy_lock(&amp;sharedVectorLock);
  </code></pre>
  
  <p>I had run my application many times and everything seemed to be working great, and that's until I decided to rerun it automatically too many times until I got wrong results. Because I'm very new to the world of OpenMP and the threads in general, I wasn't aware of the fact that we should lock all the readers when a writer is updating some shared data. As you can see here in my application the threads always read some data from the <code>unordered_map</code> in order make some conclusions and learn things about the key that was assigned to them. What happens though if two threads have to work with the same key, and while some other thread is trying to read the values of this key, another one has reached the point of updating those values? I believe that's where my problem occurs.</p>
  
  <p>However my main problem right now is that I'm not sure what would be the best way to avoid such things from happening. It's like my system works for 99% of the time, but that 1% ruins everything because two threads are rarely assigned with the same key which in turn is because my unordered_map is usually big.</p>
  
  <p>Would locking the unordered_map do my job? Most likely, but that wouldn't be efficient because a thread <code>A</code> that wants to work with the key <code>x</code> would have to wait for a thread <code>B</code> that is already working with the key <code>y</code> where <code>y</code> can be different than <code>x</code> to finish. </p>
  
  <p>So my main question is, how should I approach this problem? How can I lock the <code>unordered_map</code> if and only if two threads are working with the same key?</p>
  
  <p>Thank you in advance</p>