Gammon Forum : Programming : STL : List vs. Vector?

Entire forum ➜ Programming ➜ STL ➜ List vs. Vector?

List vs. Vector?

It is now over 60 days since the last post. This thread is closed. Refresh page

Posted by

David Haley USA (3,881 posts) Bio

Date

Sun 20 Jul 2003 12:41 PM (UTC)

Message

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... :)

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org

Top

Posted by

Nick Gammon Australia (23,046 posts) Bio Forum Administrator

Date

Reply #1 on Sun 20 Jul 2003 09:12 PM (UTC)

Message

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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

Top

Posted by

David Haley USA (3,881 posts) Bio

Date

Reply #2 on Mon 21 Jul 2003 01:00 PM (UTC)

Message

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...

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org

Top

Posted by

Nick Gammon Australia (23,046 posts) Bio Forum Administrator

Date

Reply #3 on Mon 21 Jul 2003 08:25 PM (UTC)

Message

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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

Top

Posted by

Ishandutta2007 (1 post) Bio

Date

Reply #4 on Mon 19 Sep 2011 03:19 AM (UTC)

Message

Nick Gammon said:

Lists are double-linked lists.
there is a dequeue (double-ended queue) which is really a collection of vectors.
vectors shine in random access

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.

Top

Posted by

Nick Gammon Australia (23,046 posts) Bio Forum Administrator

Date

Reply #5 on Mon 19 Sep 2011 07:15 AM (UTC)

Message

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.

- Nick Gammon

www.gammon.com.au, www.mushclient.com

Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

81,809 views.

It is now over 60 days since the last post. This thread is closed. Refresh page

Go to topic: Search the forum

top