title: O(1) deletion in an unordered vector
body: <p>In a C++ program I have a collection of plain-old-data for which I need be able to efficiently:</p>
  
  <ul>
  <li>Add elements.</li>
  <li>Iterate over the whole collection.</li>
  <li>Remove some of those elements (see update below).iteration, see below).</li>
  </ul>
  
  <p>I do not have to use a set or map type because there is no <em>external</em> requirement for:</p>
  
  <ul>
  <li>Indexing into it</li>
  <li>Maintaining ordering.</li>
  <li>Efficiently finding elements or test for them being in the collection.</li>
  </ul>
  
  <p>If I had to write it from scratch in C, I would use an exponentially growing dynamic array and the deletion operation would move the last element into the freed-up slot.  That way deletion is O(1).</p>
  
  <p>If I want to use a C++ standard container it seems I could (a) use a <code>std::vector</code> but write the deletion operation by hand or (b) use an <code>std::list</code>.  I have a mild, but definite, dislike of linked lists.</p>
  
  <p>Both solutions are acceptable to me, but I would really rather have it both ways: to use a vector but using only standard operations.  Is there a way to do this.</p>
  
  <p><strong>Update:</strong></p>
  
  <p>The comments below made clear that I am not looking for a general deletion operation.  My problem requires me to iterate over the collection frequently and on each pass I expect to discover that some elements have to be removed.  </p>
  
  <p>I can do that whole operation in O(n) time regardless of the number of deletions.  But this is obviously a bespoke operation and I should have known I need to write my own loop.  Surprisingly though <code>remove_if</code> <em>almost</em> solves my problem.  If the only thing I needed to do in the iteration pass was identify the out-of-date elements, then <code>remove_if</code> would do the job, but I need to do other processing too.</p>