I wondered if there's an efficient option between using std::list or std::vector, and I did a benchmark to see it myself.
Scenario 1: Insert n items, traverse n times.
when n=100, there isn't a huge difference but list is better. For vector it's between 15ms and 78ms, and for list it's between 15ms and 62ms.
When I calculate the average of rates, I can see that list is ~%11 faster.
when n=300, I can't see a clear winner. For vector it's between 200ms and 310ms, and for list it's between 203ms and 343ms.
According to the average of rates, vector is ~%3 faster.
Here's the source for this benchmark:http://pastebin.com/f41f684cb
Scenario 2: Insert n items, traverse n times and replace %20 of items on every iteration whilst traversing.
when n=100, mostly list wins. For vector it's between 170msms and 250ms, and for list it's between 172ms and 190ms.
List is ~%5 faster on average.
when n=200, list is always the winner. For vector it's between 1360ms and 1531ms, and for list it's between 1297ms and 1422ms.
List is ~%7 faster.
Here's the source for this benchmark:http://pastebin.com/f522f7e6b
Conclusion
If the number of items in your world are around 300 or more, and you don't perform so many insert&remove operations, pick vector. Otherwise, pick list.
I think the reason behind the truth that vector can't deal with continuous insert&remove operations is that it has to relocate remaining elements in the array when you delete one of them. For list, it's far more easy because it's implemented as a linked-list which means it's just about modifying two pointers to remove an element.
On the other hand, I think the reason why the list beats vector for 100 items is about the allocation strategy that vector uses. I don't know exactly how MS implemented this in standard library, but it's generally something like doubling the allocated memory everytime it's completely consumed. If it starts with a number like 5, to reach 100 it must be doubled 5 times, and everytime it looks for a bigger chunk of memory. The memory management has to find a continuous part in the memory for it. And after 100, to reach 300 it hast to be doubled just twice.
