taby said:
I have game pieces, and I store them in a list, because they get erased all the time. In a list, the erasure costs a constant amount of time — O(1) time complexity. When you do an erasure in the middle of a vector, the time complexity is like O(n/2)… much larger, where n is the number of elements in the vector. There is a reason why both containers exist in the STL. ?

But iterating the list means chasing pointers, so it's very slow because incoherent access.

yeah… we could discuss pro and con of various data structures til the end of time. : )

But it shows the problem is not really how to allocate memory, but how to address it.
In general we want those things:

Resolving indirection quickly.
Iterate in linear memory order for most.
Reduce dynamic allocation and fragmentation.

All contradict each other, so its hard to propose general solutions that work best for everything.

I don't search, and yeah, assigning a pointer is much faster than assigning a whack load of elements.

taby said:
I don't search, and yeah, assigning a pointer is much faster than assigning a whack load of elements.

In that case, you might have a slight advantage, but I wouldn't overestimate it (unless again you are having way over 100 elements). You don't just assign a pointer when deleting from a list. You have to fetch the previous node, then assign the pointer to the new-next node; fetch the new-next node and assign the pointer to the previous node (assuming a doubly-linked list); then deallocate the deleted list-node. All of which are randomly placed in memory so you are likely to get a few cache-misses down the line.
The vector-delete on the other hand will work on one continous block of memory which really benefits the CPU; with all cache and prefetching in place the operations are really not that much more expensive (unless your elements themselves are really expensive to copy/move as well).

And if you don't depend on a specific order of elements in the vector, you can swap&pop instead of delete (place the last element of the vector in the space where the deleting element is), and at that point list can finally eat it ?

Swap n pop. Good idea.

Thank you all for the useful replies, this really helped. Salute!