List vs. Vector?

Through reading your STL examples and some other research, it seems that vectors and lists both solve the same problem: having an extendable collection of objects. A linked list, basically, nicely maintained for you.

Now, when I look around, it seems that vectors have more functionality. Sorting, for one.

So, what's the deal? Is a vector a more specialized version of a list that has more features? Is a list simply meant to have less features? Is a vector slower? When do I use one, when do I use the other? In short... what's the difference?

I need to get my hands on one of those STL books you mentioned, Nick, so that I can answer these questions myself and not bother you with them... :)

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.

All this is covered very well in the Josuttis book.

Thanks for clearing that up.

It seems to me that in almost all circumstances, random access is better. The lists in MUDs seem only meant to just hold things, and very rarely are they spliced together... except perhaps when a container breaks and its contents are spilled out. But that's still a relatively rare event...

As for random access, that could be useful all the time. For example, "give me a random character in this room", or "give me a random object from that container". Those seem like they could be fairly frequent occurences (for example, stealing a random object from a player's backpack, a mob glaring and some random person...).

I'm not sure, I guess I would need to think longer to see which situations would require which containers. For now, my hunch is that vectors are probably more useful for random access. I'd have to look around and think some more, though...

Say, for instance, players are constantly entering and leaving rooms, and you have a "list of players in the room". Accessing them randomly might not be always required, however you would be constantly updating the list, and the one to leave would not necessarily be the last one who entered.

If you do need a random list (sorted, shuffled, whatever) you can always make a second copy - a vector this time - for the purpose.

If Lists are double-linked lists.
dequeue is a collection of vectors.
What exactly is vector.How exactly are they implement.from the nature I can assume it to be something like dynamic array.

A vector is a contiguously allocated block of memory (so yes, like a dynamic array).

However unlike "normal" arrays the STL will handle growing and shrinking without you need to worry about allocating more memory (and probably moving the existing data) when required.

Since it is contiguous, you can take the address of an element and treat it as a normal array (within the bounds of the size of it).

The disadvantage of vectors is that they are slow to add or remove items (particularly removing from the start) because of the need to shuffle things around.

A dequeue works around this by making a collection of vectors, where each vector is relatively small, so adding to the start, or the end, is relatively quick. However you then can't just index directly into (say) item 1000.