std::vector / std::list - just wondering...

[Morten Aune Lyrstad]

Hi! I haven't been using the standard template libraries much. I have a hard
time trying to figure out just what is the practical difference between
std::vector and std::list. Aren't both basically a list of objects? Why the
two types? And most importantly of all: Which one is the faster? Is it
practical to use these in game programming for dynamic arrays, or are they
too slow?

Yours,
Morten Aune Lyrstad

 

[Rolf Magnus]

Hi! I haven't been using the standard template libraries much. I have
a hard time trying to figure out just what is the practical difference
between std::vector and std::list. Aren't both basically a list of
objects?
Yes.

Why the two types?

They store the data in different ways. std::vector stores the data as an
array internally, whereas std::list stores it as a doubly linked list.

And most importantly of all: Which one is the faster?

That depends on how you want to use them. That's the major reason for
both being available. In std::list, you can efficiently insert and
remove elements at arbitrary positions, while a vector only provides
that for adding or removing elements at the end. OTOH, vector provides
better locality of data (usually meaning better cache efficiency) and
supports direct access to the n-th element for any n between 0 and the
size of the vector, while a list must be traversed for that. There are
some other differences.

Is it practical to use these in game programming for dynamic arrays,
or are they too slow?

They can be efficient when used correctly. Sometimes, it might be better
to roll your own if you have special needs, but in many cases, standard
containers are sufficient. After all, they are general-purpose
containers and most implementations are heavily tested and optimized,
resulting in good stability and efficiency.

 

[Morten Aune Lyrstad]

Thanks alot, that cleared everything up nicely!