title: std::inserter with set - insert to begin() or end()?
body: <p>I have some code that looks like this:</p>
  
  <pre><code>std::set&lt;int&gt; s1, s2, out;
  
  // ... s1 and s2 are populated ...
  
  std::set_intersection(s1.begin(), s1.end(),
                        s2.begin(), s2.end(),
                        std::inserter(out, out.end()));
  </code></pre>
  
  <p>I've read inserts can be done in amortized constant time if the value being inserted to the set immediately follows the iterator given as a "hint".  This would obviously be beneficial when running the set intersection, especially since everything being written to <code>out</code> is already in sorted order.</p>
  
  <p>How do I guarantee this optimal performance?  When creating the <code>std::inserter</code>, <code>out</code> is empty so <code>out.begin() == out.end()</code> so I can't see it makes any difference whether I specify <code>out.begin()</code> or <code>out.end()</code> as the hint.  However, if this is interpreted at inserting every element at <code>begin()</code>, it doesn't seem that I would get the optimum algorithmic performance.  Can this be done better?</p>