title: What container to store unique values?
body: <p>I've got the following problem. I have a game which runs on average 60 frames per second. Each frame I need to store values in a container and there must be no duplicates. </p>
  
  <p>It probably has to store less than 100 items per frame, but the number of insert-calls will be alot more (and many rejected due to it has to be unique). Only at the end of the frame do I need to traverse the container. So about 60 iterations of the container per frame, but alot more insertions.</p>
  
  <p>Keep in mind the items to store are simple integer.</p>
  
  <p>There are a bunch of containers I can use for this but I cannot make up my mind what to pick. Performance is the key issue for this.</p>
  
  <p>Some pros/cons that I've gathered:</p>
  
  <hr>
  
  <p><strong>vector</strong></p>
  
  <ul>
  <li>(PRO): Contigous memory, a huge factor. </li>
  <li>(PRO): Memory can be reserved first, very few allocations/deallocations afterwards</li>
  <li>(CON): No alternative than to traverse the container (std::find) each insert() to find unique keys? The comparison is simple though (integers) and the whole container can probably fit the cache</li>
  </ul>
  
  <p><strong>set</strong></p>
  
  <ul>
  <li>(PRO): Simple, clearly meant for this</li>
  <li>(CON): Not constant insert-time</li>
  <li>(CON): Alot of allocations/deallocations per frame</li>
  <li>(CON): Not contigous memory. Traversing a set of hundreds of objects means jumping around alot in memory.</li>
  </ul>
  
  <p><strong>unordered_set</strong></p>
  
  <ul>
  <li>(PRO): Simple, clearly meant for this</li>
  <li>(PRO): Average case constant time insert</li>
  <li>(CON): Seeing as I store integers, hash operation is probably alot more expensive than anything else</li>
  <li>(CON): Alot of allocations/deallocations per frame</li>
  <li>(CON): Not contigous memory. Traversing a set of hundreds of objects means jumping around alot in memory.</li>
  </ul>
  
  <hr>
  
  <p>I'm leaning on going the vector-route because of memory access patterns, even though set is clearly meant for this issue. The big issue that is unclear to me is whether traversing the vector for each insert is more costly than the allocations/deallocations (especially considering how often this must be done) and the memory lookups of set.</p>
  
  <p>I know ultimately it all comes down to profiling each case, but if nothing else than as a headstart or just theoretically, what would probably be best in this scenario? Are there any pros/cons I might've missed aswell?</p>
  
  <p>EDIT: As I didnt mention, the container is cleared() at the end of each frame</p>