Re: S-expression I/O in Ada

["Randy Brukardt" <randy@rrsoftware.com>]

"Natasha Kerensikova" <lithiumcat@gmail.com> wrote in message 
news:slrni6nioh.1efq.lithiumcat@sigil.instinctive.eu...
...
> Then I don't really understand the point of having both Vectors and
> Doubly_Linked_Lists. The interface of Vectors is a strict superset of
> the interface of Doubly_Linked_Lists, and the only difference in
> complexity (which is advice anyway, so non-guaranteed) is on Prepend.
>
> The only notable difference I've found is that
> Doubly_Linked_Lists.Cursor is more resistant to container changes than
> Vectors.Cursor, but I find it a bit weak to justify the existence of
> both types.
>
> What I am missing there?

You've obviously missed the Splice operations (which allow you to move nodes 
from one container to another without copying); those of course are 
impossible for Vectors. Similarly with the Swap_Links operations.

And the performance of Insert is O(log N) for lists while it is not 
specificed for vectors (typically it would O(N) or worse as all of the 
elements will need to moved to make room).

It's a subtle difference in fact; we argued about whether we needed both 
along the lines that you have, but eventually decided that the data 
structures are so fundamental that it would be weird to not to provide both.

                         Randy.


                                 Randy.