Re: List container: Insert and Delete

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Nick Roberts wrote:
> 
> Your delicate distinction between an 'iterator' and a 'position' is a little
> silly. The reasons why it should not be done with iterators are the same as
> the reasons why it should not be done with positions.

No, the idea that they are the same is a little silly. An iterator, by
definition, is something that iterates. A position within a list does
not iterate. If you can provide an example of a position iterating I
will change my position.

> The indexed operations will, of course, be of O(1) for the bounded list, yet
> being both based on the abstract list type, they will be algorithmically
> interchangeable. So there is a deeper reason for my insistence on indexed
> operations: I am trying to make a bigger plan 'come together'.

They will be O(N) in both versions, unless you make the extremely poor
implementation decision for the bounded version to implement insertions
and deletions by moving entire slices of the underlying array. I suspect
such an implementation will be universally considered unacceptable.
Making insertions and deletions O(N) so that indexing can be O(1) is a
poor choice, especially considering that both can be O(1).

The abstraction of a position should be the same for both bounded and
unbounded lists. The underlying implementation of a position for a
bounded list will be an index into the underlying array, but it is quite
likely that the component at index N of the array will not be the Nth
element in the list.

> Finally, my proposal includes all the usual head and tail dicing operations.
> Chopping off, or adding on, one item to either end of a list will be the
> most frequently used operations anyway, for which arguments about indexing
> don't apply. The indexed operations are mainly there for convenience. As I
> showed in an example in another thread, really serious manipulations of
> lists are best done sequentially.

There are no "usual" head and tail operations for a list. In decades of
using and implementing data structure libraries, TED's specification is
the first I've encountered that emphasizes dequeue- and string-like
operations.

The whole point of a list is that insertions and deletions are needed at
arbitrary positions. If you're only operating at the ends of the
sequence, then you want a dequeue, not a list, and you should not be
using a list.

> 
> I hope you will look at my proposal, and perhaps be a little more convinced!

I'll take a look.

-- 
Jeffrey Carter