title: Implementing Battlefield 3's std::vector swap trick to "remove/add" an element
body: <p>I'm trying to implement an algorithm and I stumbled upon DICE's "swap trick" as described <a href="http://www.frostbite.com/wp-content/uploads/2013/05/CullingTheBattlefield.pdf" rel="nofollow noreferrer">here</a> (slide 19).</p>
  
  <p>From what I understand, we first create a vector with all of our elements and then when an element needs to be deleted, it is swapped with the last one and we decrease the "size" of the vector. This "size" is an external variable to keep track of our "virtual" size (because a vector <a href="https://stackoverflow.com/questions/39175949/how-to-resize-an-stdvector-without-loosing-the-existing-data">doesn't support this internally</a>).</p>
  
  <p>NOTE: ordering/sorting is not important. Also, when I say "delete", nothing is de-allocated, it's just saying that the element is moved outside of the "usable" range.</p>
  
  <p>Now, when the moment comes to add an element (from the deleted ones) back in the usable part of the vector, we need to swap it back somewhere. And this is where I'm blocking a bit. Because, when we swap it, we could be swapping it with an element that needs to be there at this iteration and this same element would need to be swapped back and so on...</p>
  
  <p>This is an example how it should work :</p>
  
  <p>iteration 1 : |1 2 3 4| (size 4)</p>
  
  <p>iteration 2 : |1 3| 2 4 (size 2 with the elements '2' and '4' still there in memory but not accounted for in the size of the vector)</p>
  
  <p>iteration 3 : |2 1 3| 4 (size 3 with the element '4' still there)</p>
  
  <p>I might be over-thinking it, but if anyone has an idea of how to get this algorithm right, that would be helpful.</p>
  
  <p>Thanks for any help.</p>