DynamicArray vs LinkedList

[wekkew]

Hello

I've been away from C++ for many years now, but when I did work with C++ (prior to STL) I always believed that arrays were bad and linked lists were so GOOD. Now that the STL offers dynamic resizing of arrays, what's best for the following situation:

A collection of records (objects) which are frequently added/deleted.

Is there a marked performance difference between the Array in STL and a linked list? Does the STL Array still use contiguous memory?

I've read some stuff on websites that seems to infer that only "nerdy - make it as difficult as possible" people use linkedlists, whereas the Array would do the same job, in the same time, far quicker. This is a complete turn around to what I grew up believing.

Any advice?

Kate

 

[Guest_imported]

STL has many different containers. Each serves a different purpose. For the performance consideration, array is always the fastest for search. But you have to know the size in advance.(Of course, vector offers resizing). If frequent insertion/removal are needed and the performance of insertion and removal is critical, you had better use list. But you have to know it is slow to search a list. You can also use queue, dequeue, if the operation usually happens at the head and/or the tail.

Vector uses the contiguous memory. On every resizing, elements are copied to another reallocated contiguous memory and previous one is deleted.

 

[Jcan]

In my opinion considering the speed of pc's these days searching a list or a queue in STL is pretty fast even though dynamic lists are faster. The question is how fast do you want to be and is the difference really obvious?