Speed and memory in STL lists as opposed to vectors

[ravenous]

Hi, this might be a quick question, if anyone "just knows" the answers.

I want to know a little about the differences between lists and vectors. For example, I think that the elements of a vector are stored in continuous blocks of memory (Maybe?) Are lists stored the same way, or does the OS just find space for one element of the list at a time and link them together with pointers?

Also, I think that when a vector is resized and will no longer fit contiguously into the space that was originally allocated it is moved to a new space that is big enough. But, I have also read that the memory that was previously used can only be filled with a vector that is small enough to fit in the old space. Does this mean that NOTHING can be put in this memory, like some other kind of array, or an int or anything? Is any of this true for lists as well?

Finally, I think that repeatedly using push_back() on a vector is less efficient that using a combination of one resize() and a subsequent bunch of at() 's. Both in terms of memory usage and speed. How does this rule apply to lists?

Many thanks.

[Ancient Dragon]

>>Are lists stored the same way,
no. Lists are linked list and each node has its own memory location.

>>But, I have also read that the memory that was previously used can only be filled with a vector that is small enough to fit in the old space.
The old memory is given back to the program's general memory manager, which can use the space for anything.

>>I think that repeatedly using push_back() on a vector is less efficient
Yes, sizing the vector before doing anything is a lot more effiecient then a lot of push_back() calls. But in order to do that the program needs to know how big an array to create. If the array size is not known then there may be no other choice but to use push_back().

[ravenous]

>>Yes, sizing the vector before doing anything is a lot more effiecient then a lot of push_back() calls. But in order to do that the program needs to know how big an array to create. If the array size is not known then there may be no other choice but to use push_back().

Does this also apply to lists?