Re: Wanted: Ada STL. Reward: Ada's Future

[Stephen Leake <Stephen.Leake@gsfc.nasa.gov>]

Hyman Rosen <hymie@prolifics.com> writes:

> Stephen Leake wrote:
> > I thought Matthew just did that, but you haven't answered the question
> > "why does the STL allow iteration past the end of the array". This
> > bugs me too. Is there a real reason here, or is it an accident of the
> > implementation?
> 
> STL iterators are analogous to C pointers; one goal of the STL design is to
> be able to use C pointers as iterators in any STL algorithm. Given that C
> allows a one-past-the-end pointer to an array, it becomes natural to
> express
> STL ranges as [i,j). This allows an entire array to be spanned, as well as
> allowing an empty range to be easily specified.

Ok, that's what I thought. The STL style of expressing ranges as [i,j)
is an consequence of the implementation, not a requirement of the
design.

I don't see why allowing pointers as iterators is a good idea in the
first place. How do you efficiently maintain the head and tail
pointers, or other list-wide state, for a doubly linked list when you
insert from a plain pointer? Apparently you don't!

So for an Ada "STL", we can either use [i,j) to be somewhat compatible
with C++ STL, or we can use [i .. j] to be more Ada-like. I'm not
clear what the best choice would be, but I lean towards being
Ada-like. I'd rather woo good Ada programers than ex-C++ programers :).
 
> > Perhaps it is the most general way to define an iterator that points
> > to nothing? Certainly if the underlying implementation of a collection
> > is an array, this makes sense. But if the underlying implementation is
> > a list, then a null pointer makes more sense. Why not make the
> > abstraction resemble a null pointer, rather than an out-of-bounds
> > index?
> 
> Because you don't always want to operate on the entire container, of
> course.
> STL algorithms take a pair of iterators when they need a range specified,
> and
> this allows them to work on arbitrary sections of a container. Also, when
> an
> algorithm requires a bidirectional iterator, you can go back from a
> past-the-end
> iterator, but not from a null pointer.

Depends on what else you store in the iterator data structure. If you
store a pointer to the container itself, you can do what's required.
Again, insisting that a plain pointer can be an iterator is too
restricting.

-- Stephe