vector/list

Hello..

Whats the difference betwen vector and list?
I know vector = array, list = linked list, and they can be used the same way..

When should I use vector and when list?

Think about what happens if you wish to insert something in the middle of a vector or the middle of a linked-list.

Which is faster?

(In theory) if you plan on doing insertions into the middle of a container then a linked-list would be quicker than a vector. Of course it depends on how the writer(s) of the STL actually implemented things.

Inserting into the middle of a linked list (constant time) would be faster than inserting into the middle of a vector (linear time).

It depends on the situation, that's why both are available. You should learn the differences between different data structures. You should also read up on the efficiencies of the different standard library containers. In general, you should use vector for most of your containment needs, but in some cases it makes more sense to use list.

<town cryer>
READ ALL ABOUT IT - http://www.sgi.com/tech/stl/table_of_contents.html
</town cryer>

There's also the matter of acessing the elements. What is good in terms of inserting, may not result so well if acessing the elements is the thick of the operations. If the container is going to be used mainly for random access, while the insert and erase operations are isolated events happening here and there, a vector is probably best.

I may be wrong here, so do correct me:

After analysing what is going to be the thich of the operations,

- If random access use a vector or deque
- If random insertions/deletions use a list
- If insertions/deletions at the front or back, use a deque
- if insertions at the middle and then random access, use a list and then copy it to a vector

EDIT: Oops 3 replies between starting and finishing my post.

In most of those cases I would actually use a vector first. If speed or efficiency were an issue, then I'd consider profiling and switching. Those are ok guidelines to follow, and it does make sense to use the right data structure from the beginning, but in many cases it actually turns out that vector is faster even when you would think that a list or deque should be. This is often because the overheads of other containers is larger than the vector overhead, and so it takes a large number of elements before the big-O performance improvements appear.