stl: list vs vector

They solve different problems, so it depends on the "shape" of your data, and which is more important to you, inserting, deleting or accessing quickly.Lists are double-linked lists, so insertion at either end, or in the middle (providing you know an existing element in the middle) is equally fast. Also, splicing is fast (eg. putting a list into the middle of another) - all that does is re-arrange the end pointers. All of those operations would be slower with vectors, because you would need to copy everything.eg. Inserting into the middle of a vector of 1000 items would involve moving 500 items up one. Similarly with deleting. In fact, vectors are really only good for insertion and deletion at the end.For things that require insertion and deletion, but only at *each* end (like a queue) then there is a dequeue (double-ended queue) which is really a collection of vectors. This is more efficient.However, vectors shine in random access - since they are organised sequentially in memory, whilst this is slow for insertion at anywhere other than the end, you can easily find, say, element 500, you simply index into the vector. Thus, vectors can be sorted, shuffled, and accessed randomly.When playing with STL - and these other MUD-related ideas - I am asking myself what is the need for each case - random access or fast insertion, and using the container appropriate to the case at hand.For instance, in the event management code I will post shortly, as I remove events from the queue I am keeping a copy of the auto-repeat ones, for later re-insertion. Now the copy is a temporary copy, and I don't need to access it in any special way, so I am using a simple vector. However the event queue itself is a priority queue (which I suspect is implemented as a map of queues).Vectors are designed to auto-grow, with the size - I believe they double in size each time they grow. eg. 2, 4, 8, 16 and so on. So, if you keep adding to them the number of memory allocations is pretty small. However if you know in advance how much they need (even roughly) then you can tell the vector to reserve that amount in advance.
(Thanks to Nick Gammon. Article taken from http://www.gammon.com.au/forum/bbshowpost.php?bbsubject_id=2993)