<vector> and <list>

[Lucas]

So, I've been learning from the Lazy Foo' SDL tutorials and websites like cprogramming.com, I have pretty much read everything I can on both websites (Although there is so much information it hasn't all stuck with me yet) and have started to experiment with the new and delete keywords to create things during run-time of a program.

So far I have been making a 'Zelda: A link to the past' rip off, and have been creating new Gaurd Sprites whenever you press the 'n' key, all of them would be deleted from memory when the program is closed.
But I started to wonder if it really matters whether I use a 'list' or 'vector' to store these new sprites?

On cprogramming.com it says:

You might wonder why there are both list and vector containers in the STL -- the reason is that the underlying representations are different, and each representation has its own costs and benefits. The vector has relatively costly insertions into the middle of the vector, but fast random access, whereas the list allows cheap insertions, but slow access (because the list has to be traversed to reach any item).

Which leads me to believe that both should be perfectly fine, but being new to this I'm not 100% sure.

So far I have only used a list to store these new sprites, but is there really much difference as to which one to use when it comes to games?
Or would it depend on how much deleting/inserting/accessing etc you were expecting to do?

(Hopefully this isn't too much of a nooby question :p)

Thanks in advance

[sparda]

So far I have only used a list to store these new sprites, but is there really much difference as to which one to use when it comes to games?
Or would it depend on how much deleting/inserting/accessing etc you were expecting to do?

When it comes to games, yes. When it comes to learning how to write games, not that much. Yes it would depend on how much deleting/inserting/access etc you would do as well.

This is all about data-structures.

The caveats mentioned would only be of concern if you use a massive data-set; e.g. a huge amount of sprites. So for learning purposes, I would say that it does not matter what representation you use for a sprite container at this point. The only thing I would point out is that with lists, you would not be able to index elements as they have bidirectional iterators, not random access. Whereas with vectors, you have both iterators.

So in other words, with lists you won't be able to do something like this:

Code: Select all

std::list<int> numbers(10);
numbers[0] = 10; //WRONG

The compiler would complain that there is no operator overloaded for the brackets (operator[]).
With vectors you can do this though.

[Lucas]

Thank you for your reply.

I'm slowly getting used to how each one is used. Since I'm still just learning I guess I'm just not using large enough amounts of data to see any real advantage to using one over the other yet, which is why I was wondering whether it made much difference.
I'm sure once I get past the main stage of learning everything it will start to become clearer

[MarauderIIC]

"The vector has relatively costly insertions into the middle of the vector, but fast random access, whereas the list allows cheap insertions, but slow access (because the list has to be traversed to reach any item)."

Well, look at it this way:
If you're never going to insert into the middle of the vector, you should use the vector. Inserting at the end of the vector is fine. So for some collection of bad guys where they can be killed in any order means that you should use a vector -- if you want to have a collection of things that you access a lot, use a vector. If you want to build a list of things, ie, you're doing continuous insertions but you're hardly ever accessing an element, use a list.

[Lucas]

Thanks Marauder, it seems quite simple to me now
I guess part of being a noob means posting questions and realising how simple the answer is straight after lol.
Thanks