title: How can I use merge to merge two maps/multimaps (C++11 STL)
body: <p>My project deals with divide-n-conquer strategy to parralelize an existing algorithm.
  The algoritm returns a <code>std::multimap&lt;int, std::pair&lt;int, int&gt;&gt;</code>. Above is a sketch of a premilinary (single_thread) version.</p>
  
  <pre><code>typedef std::multimap&lt;int, std::pair&lt;int, int&gt;&gt; Map ;
  struct Box
  {
    std::pair&lt;int, int&gt; top_left, bottom_right ;
  }
  Map my_algo(Box, a_box)
  {
    Map final_m ;
    if (not is_small(a_box))
    {
      box b1, b2 ;
      split_box(a_box, &amp;b1, &amp;b2) ; // this function divides the box in two halves
      Map m1 = my_algo(b1) ;
      Map m2 = my_algo(b2) ;
  
      // this line will not compile. final_m.begin() is not accepted.
      std::merge (m1.begin(), m1.end(), m2.begin(), m2.end(), final_m.begin()) ; 
    }
   return final_m ;
  }
  </code></pre>
  
  <p>I know I could use insert instead or merge to do the merging (as explained <a href="https://stackoverflow.com/questions/3639741/merge-stl-maps">here</a>). But insert is in O(N.Log(n)) while merge is in O((N)). Because of the number of merging operations involved in the algorithm, time-complexity matters.</p>
  
  <p>Thanks for helping,
  Olivier</p>
  
  <p>EDIT:</p>
  
  <p>Thanks to jogojapan (see answer below), this is a working demo of the corrected code:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;map&gt;
  #include &lt;iterator&gt;
  #include &lt;algorithm&gt;
  
  typedef std::pair&lt;int, int&gt; Cell ;
  typedef std::multimap&lt;int, Cell&gt; Border_map ;
  
  void test_merge_maps_1()
  {
  Border_map a, b, c ;
  std::cout &lt;&lt; std::endl &lt;&lt; "a" &lt;&lt; std::endl ;
  for (int i=1; i&lt;10; i+=2)
  {
      a.insert(std::pair&lt;int, Cell&gt;(i, Cell(i,i))) ;
      std::cout &lt;&lt; i &lt;&lt; " " ;
  }
  
  std::cout &lt;&lt; std::endl &lt;&lt; "b" &lt;&lt; std::endl ;
  for (int i=2; i&lt;11; i+=2)
  {
      b.insert(std::pair&lt;int, Cell&gt;(i, Cell(i,i))) ;
      std::cout &lt;&lt; i &lt;&lt; " " ;
  }
  
  std::cout &lt;&lt; std::endl &lt;&lt; "merge" &lt;&lt; std::endl ;
  std::merge(a.begin(), a.end(), b.begin(), b.end(), inserter(c,end(c))) ;
  
  std::cout &lt;&lt; "result" &lt;&lt; std::endl ;
  for(auto x: c)
      std::cout &lt;&lt; x.first &lt;&lt; " " ;
  std::cout &lt;&lt; std::endl ;
  }
  
  int main(void)
  {
      test_merge_maps_1() ;
      return 0 ;
  }
  </code></pre>