Sign in to follow this  
jake_Ghost

Whats the difference between a list and a vector?

Recommended Posts

Is there a difference, becuase at the moment, I use vectors to hold all my game nformation (Terrain, items, enemies, sounds, ect). Would there be a logical reason for me to want to switch to lists or use them for certain parts? Jake

Share this post


Link to post
Share on other sites
If you often want to insert and delete items from the middle of large vectors (i e, kilobyte-size or bigger), then it may be more efficient to use a list -- assuming you don't need to address elements by index.

Share this post


Link to post
Share on other sites
The primary difference is performance. Vectors are implemented with a resizable array. Vectors, therefore, are better at random access to elements (accessing an element by its index), but are slow on insertions or deletions at the beginning or middle of the list. A list is implemented as a linked list. Lists are good with insertions and deletions anywhere, but are slow when accessing items by its index (because one has to begin at the beginning or end of the list and follow the links until the index is reached). While both classes have a similar interface, they differ somewhat to emphasize an efficient use of the class (i.e. - a list does not support the random access operator []). You can still do all the same stuff with either class, however. The differences in performance depend on the size of the collection. For most uses, use vectors. If you need to make insertions into the middle of the list, and don't need to use random access often, then consider using a list instead.

Share this post


Link to post
Share on other sites
Thanks guys, you cleared that up really good. I guess I will stick with vectors because I use a lot of the random values to get data.

Jake

Share this post


Link to post
Share on other sites
A good general rule is to use lists when all you plan on doing is running through the data and a vector when you plan on selecting random elements. Also note that inserting in the middle of a vector is extremely slow, so if you're doing some kind of sorting, make sure you use a list.

[EDIT] And yes, Washu's right. Sorting a list is quite slow. I don't see why you'd be sorting enemies on the screen though. But, you never know.

[Edited by - Rob Loach on June 21, 2005 11:27:19 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Rob Loach
A good general rule is to use lists when all you plan on doing is running through the data and a vector when you plan on selecting random elements. Also note that inserting in the middle of a vector is extremely slow, so if you're doing some kind of sorting, make sure you use a list.


NO, use a vector. List sort is no where near as efficient as the sort algorithm based around random access iterators. If you have an arbitrary order in mind already, a set or map (or unordered_set/unordered_map) would be better choices.

Share this post


Link to post
Share on other sites
Quote:
Original post by jake_Ghost
Thanks guys, you cleared that up really good. I guess I will stick with vectors because I use a lot of the random values to get data.

If the data you have doesn't require to sit in a single contiguous chunk of memory, you might also want to try std::deque. This one can be very similar in performance, but easier on the OS.

comparison references: 1, 2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this