AW: Problem with a list of times

Posted by Jens Thiel on Oct 02, 2002; 5:46am
URL: http://quantlib.414.s1.nabble.com/Problem-with-a-list-of-times-tp2221p2223.html

Hi,

it's not a bad implementation in the STL, but a bad choice of the programmer
;-)   list, deque, vector, ... have all different strengths and weaknesses.

A list is optimal if your applications needs to insert objects in the middle
of the list and processing is usually done sequentially. Elements in the
list are "chained" with each other. Finding the n-th element (also called
random access) means to walk the whole chain - a rather expensive
operation - and to re-link the chain with the new element (cheap op). Adding
at the end is usually cheap because the container stores pointers to the
first and last element.

A vector on the other hand has instant random access because all elements
are stored sequentially in the memory. Adding at the end _could_ be very
expensive if you did not reserve enough room: the container needs to
allocate new space, copy ALL the existing elements, and then add the new
element with a single operation. Inserting somewhere inbetween is always
expensive, because all elements have to be moved up one place.

So if you just need to store times, and you know the required element count
or have a good guess (add some extra space here), reserve and use a vector
for your data.

Regards,

Jens.


> Regarding the sorting issue, I was using the sort method of the
> list object,
> as in your first example. The deque class works much better, the
> sorting is
> practically instantaneous (I am not a programmer and this sounds quite
> strange to me, I'd be tempted to say that the sort algorithm of
> the list has
> been implemented very badly!!).