title: Most efficient way of erasing/deleting multiple std::vector elements while retaining original order?
body: <p><br>
  i have a <code>std::vector&lt;int&gt;</code> and a second container holding iterators or indexes (no keys, i want constant access to the element) to this vector for deletion purposes.
  Let's assume i have a vector of 1000 elements and want to erase 200 of them. The order of the non-removed elements should be the same after the deletion operations like before.</p>
  
  <p>One more thing i missed in the first version of my question: the <em>values are unique</em>. They are identities.</p>
  
  <p><em>How would you do that in a safe (regarding the stl rules) and efficient manner (the decision for a vector shall be final)?</em></p>
  
  <p><strong>Possibilities</strong> or <strong>Methods</strong> i thought about:</p>
  
  <ul>
  <li>the <strong>erase-remove idiom</strong> (http://en.wikipedia.org/wiki/Erase-remove_idiom): originally for the deletion of elements which fulfill a condition (including linear search) but i think with ranges of size 1 this method could be used to with already given iterators and a dummy condition. <strong>Question: is the original order of elements kept and is it more performant than the last method?</strong>  </li>
  <li>loop over the indexes and erase the elements with the use of <code>vector.erase(vector.begin()+index+offset)</code> while keeping the indexes removed in a container for calculating the offset. This offset could be determined for every remove iteration with the use of a <code>std::lower_bound</code> n the container of already removed elements. <strong>The problem: A lot of binary_searches for getting the offset and a lot of move operations because of random-location-deletion.</strong></li>
  <li>At the moment I'm doing the following: get all the iterators for the elements to remove. Sort them in descending order according to the location in the vector and loop over them for the final deletion with <code>vector.erase</code>. Now I'm not invalidating any iterator and there are no vector rearrange-operations except for the deletion itself. <strong>The problem: a lot of sorting</strong></li>
  </ul>
  
  <p>So, how would you tackle this? Any new ideas? Any recommendations?</p>
  
  <p>Thanks for your input.</p>
  
  <p>Sascha</p>
  
  <p><strong>Edit / Update / Own results:</strong> I implemented the <strong>erase-remove idiom</strong>, which was also mentioned by KennyTM, with a <strong>predicate based on the lookup in a boost::dynamic_bitset</strong> and it's <strong>insanely fast</strong>. Furthermore i tried <strong>PigBen's move-and-truncate method</strong> (also mentioned by Steve Jessop) which is also accessing the bitset in it's while-loop. Both seem to be equally fast with my kind of data. I tried to delete 100 of 1000 Elements (unsigned ints), did this 100 deletes 1M times and there was no significant difference. Because i think the stl-based erase-remove idiom is kinda more "natural, i'm choosing this method (argument was also mentioned by KennyTM).</p>