Re: list strawman

[dennison@telepath.com (Ted Dennison)]

dennison@telepath.com (Ted Dennison) wrote in message news:<4519e058.0201081910.51225bf@posting.google.com>...
> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> wrote in message news:<uwuys1qun.fsf@gsfc.nasa.gov>...
> > I vote for adding 'split'; it nicely compliments 'splice'.
> 
> OK. Next question(s): Can "split" be implemented as the inverse to
> "splice", where it spilts from the iterator to the end, or does it
> need to go from one iterator to another to be useful?
> 
> If the latter, should "splice" be changed to work the same way?

OK. I have bad news on this score. After playing with the code a bit,
I came to realise that, while Splice as it stands can be implemented
in O(C), Split and any iterator-to-iterator splice would both end up
being no better than O(n). The problem is our safe iterators. Since
iterators are associated with their list somehow, you have to go
through every iterator that got moved and change its list (or
invalidate it). There's no way to tell if a iterator's element got
moved by our theoretical "Split" without iterating through the
affected elements, which is O(n).

The current Splice escapes this fate by virtue of the fact that *all*
iterators are affected, so the algorithm can be made O(n) in iterators
but not in elements.

The only other option for other routines would to take the position
that all operations that can move a subrange of elements from one list
to another invalidate *all* the source lists' iterators. This looks
like a good solution on paper, but I think its quite liable to destroy
anyone's custom sort algorithm, which was the whole point of this
exercise in the first place.

So I'm not real sure we have a good reason for "Split" now after all.