lists and sequences

[Erik Max Francis]

Bengt Richter wrote:

> I wonder how often that happens. If it happened a lot, I could see
> a time optimization based on keeping an offset to the first element
> in the allocated space and bumping that until there'se a worthwhile
> chunk to shift down over.

Keeping the internal implementation of a list as a straightforward
vector is really the best approach.  If you find yourself needing to
constantly insert and remove things from the beginning of a list, then
you've probably got the list reversed -- you should be appending and
popping things off the _end_, not the beginning.  If you really and
truly need to, say, push things on the end and remove them from the
beginning, then a linked list implementation of a queue might be a lot
more sensible.  Or you could have some proxy list type that uses a
normal list as a buffer in the way you describe above, and you just
periodically sync up the list so that you get rid of the wasted elements
at the beginning (before your "read head").

As with all such things, follow the First Rule of Optimization:  Make
sure that such a situation is really a bottleneck in your code before
you attempt to rectify it.  If you're getting O(n^2) behavior in one
case but it's dependent on O(e^n) behavior somewhere else, you're
wasting your time optimizing the former; you should be concentrating on
the latter.

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ Life is an effort that deserves a better cause.
\__/ Karl Kraus
    7 Sisters Productions / http://www.7sisters.com/
 Web design for the future.