For the memory allocation issues, many people don’t know this but you can write custom allocators for your STL container classes. Allocators are basically policy classes you pass into your templates to determine how allocations are performed. Using these you can usually work around whatever memory issues are problematic on your platform of choice.
Of course, if you’re using the STL and doing dumb things like maps of strings to large, non-pointer types, then you have bigger problems on your hand.
The default STL has a fair number of issues that make it difficult to use with games, especially when it comes to memory alignment.
A customized variant such as the EA STL is specially designed for games and can get you much better memory performance and console usability. I haven’t seen an open source gaming STL variant, but it would not be impossible to replace piecemeal the important bits.
Use a list when iterator invalidation caused by modifying the middle of your data structure is going to cause a problem, or you need to keep your elements sorted so the swap and pop trick for quick middle collection deletes won’t work and you have a large number of mid collection deletes.
You may also want to consider using a Deque. It has similar performance characteristics to a vector but doesn’t have vector’s need for contiguous memory, and is a little more flexible.
The speed you’ll gain by having all your elements in your container in contiguous memory (and therefore more cache-friendly) is worth the offset of the additional costs of adding/removing/resizing the vector.
Edit: Just to clarify a bit more, of course it should go without saying that any kind of “which is faster” question should be tested on whatever platform with whatever data sets are pertinent to your particular needs. If I just need a collection of elements I just use vector (or deque, which is almost the same thing) unless there’s a good reason not to.