List vs vector

In a problem statement how can I decide, whether I should use a vector or a list?

1 Like

Lists are know to be a sequence containers that allow constant time insert and erase operations anywhere within the sequence. And ofcourse iteration in both the direction.

So list is usefull only if you have insertion and deletion in mid way of container. but it would lack diect access to element by position as if you want to access to 4th position of 10 element container then you have to traverse upto 4th element to get the result.

Unlike vector which is like array which uses contiguous memory allocation that means you can access any element in a constant O(1) time, that’s a advantage of vector but the problem is insertion and deletion takes a linear time according to the position of insertion.

So ultimately, if you have a large query of insertion and deletion in the mid way of container then would be usefull but if you have a large queries about accessing the element(like arrays) then vector would be usefull to you!

I hope it will clarify your whole doubt, otherwise ask again!

3 Likes

Just use vectors for most of your needs(including adj list in graphs) , except on very specific cases, especially if you need splicing or have to remove items from the middle of a , say, sorted list,because most of the time you will just only append (without worrying about order), sort and randomly access elements, all of which are best handled by vectors.

1 Like

You are wrong! See this http://www.cplusplus.com/reference/vector/vector/insert/

my bad! confused insert with push_back! you’re right.