title: Is stability of std::remove and std::remove_if design fail?
body: <p>Recently (from one SO comment) I learned that <code>std::remove</code> and <code>std:remove_if</code> are stable. Am I wrong to think this is a terrible design choice since it prevents certain optimizations?</p>
  
  <p>Imagine removing the first and fifth elements of a 1M <code>std::vector</code>. Because of stability, we can't implement <code>remove</code> with swap. Instead we must shift every remaining element. :(  </p>
  
  <p>If we weren't limited by stability we could (for RA and BD iter) practically have 2 iters, one from front, second from behind, and then use swap to bring to-be-removed items to end. I'm sure smart people could maybe do even better. My question is in general, not about specific optimization I'm talking about. </p>
  
  <p><strong>EDIT:</strong> please note that C++ advertizes the zero overhead principle, and also there are <code>std::sort</code> and <code>std::stable_sort</code> sort algorithms. </p>
  
  <p><strong>EDIT2:</strong> 
  optimization would be something like the following:</p>
  
  <p>For <code>remove_if</code>:</p>
  
  <ul>
  <li>bad_iter looks from the beginning for those elements for which the predicate returns true.</li>
  <li>good_iter looks from the end for those elements for which the predicate returns false.</li>
  </ul>
  
  <p>when both have found what is expected they swap their elements. Termination is at <code>good_iter &lt;= bad_iter</code>.</p>
  
  <p>If it helps, think of it like one iter in quick sort algorithm, but we don't compare them to a special element, but instead we use the above predicate. </p>
  
  <p><strong>EDIT3:</strong> I played around and tried to find worst case (worst case for <code>remove_if</code> - notice how rarely the predicate would be true) and I got this:</p>
  
  <pre><code>#include &lt;vector&gt;
  #include &lt;string&gt;
  #include &lt;iostream&gt;
  #include &lt;map&gt;
  #include &lt;algorithm&gt;
  #include &lt;cassert&gt;
  #include &lt;chrono&gt;
  #include &lt;memory&gt;
  using namespace std;
  int main()
  {  
      vector&lt;string&gt; vsp;
      int n;
      cin &gt;&gt; n;
      for (int i =0; i &lt; n; ++i)
      {   string s = "123456";
          s.push_back('a' + (rand() %26));
          vsp.push_back(s);
      }
      auto vsp2 = vsp;
      auto remove_start = std::chrono::high_resolution_clock::now();
      auto it=remove_if(begin(vsp),end(vsp), [](const string&amp; s){ return s &lt; "123456b";});
      vsp.erase(it,vsp.end());
      cout &lt;&lt; vsp.size() &lt;&lt; endl;
      auto remove_end = std::chrono::high_resolution_clock::now();
      cout &lt;&lt; "erase-remove: " &lt;&lt; chrono::duration_cast&lt;std::chrono::milliseconds&gt;(remove_end-remove_start).count() &lt;&lt; " milliseconds\n";
  
      auto partition_start = std::chrono::high_resolution_clock::now();
      auto it2=partition(begin(vsp2),end(vsp2), [](const string&amp; s){ return s &gt;= "123456b";});
      vsp2.erase(it2,vsp2.end());
      cout &lt;&lt; vsp2.size() &lt;&lt; endl;
      auto partition_end = std::chrono::high_resolution_clock::now();
      cout &lt;&lt; "partition-remove: " &lt;&lt; chrono::duration_cast&lt;std::chrono::milliseconds&gt;(partition_end-partition_start).count() &lt;&lt; " milliseconds\n";
  }
  
  
  
  C:\STL\MinGW&gt;g++ test_int.cpp -O2 &amp;&amp; a.exe
  12345678
  11870995
  erase-remove: 1426 milliseconds
  11870995
  partition-remove: 658 milliseconds
  </code></pre>
  
  <p>For other usages, partition is bit faster, same or slower. Color me puzzled. :D</p>