RE: Boost algorithm library (Was: [boost] New upload: algorithm.zip 1)

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2001-07-25 16:53:31

----- Original Message -----
From: Vesa Karvonen <vesa.karvonen_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, July 25, 2001 5:53 PM
Subject: Re: Boost algorithm library (Was: [boost] New upload: algorithm.zip
1)

> From: "Fernando Cacciola" <fcacciola_at_[hidden]>
> > From: Jeremy Siek <jsiek_at_[hidden]>
> [...]
> > I am not sure if a *standarized* container-like interface will have a
good
> > impact on a program design.
>
> I'm not so sure. Functional languages do quite well without iterators.
Take a
> look at functions such as 'foldr', 'map', 'filter', 'take', 'drop',
'rev',...
> that you can find in most functional languages (in some functional
languages
> they may be named differently).
>
I don't know about FP. I'll have to take a look at it.

> > The range interface is a *very* powerful abstraction, much much better
than
> > the abstraction of an (encapsulated) container.
>
> You almost always need both abstractions. Iterators are really a
supporting
> abstraction, that separates enumeration/traversal from containment.
>
> In fact, you don't need a "range interface", which I assume means a pair
of
> iterators, to separate enumeration from containment. A single object is
> sufficient for describing a range. The reason why C++ uses a pair of
iterators
> is due to the legacy pointer syntax.

With range interface I mean precisely something that separates enumeration
from containment. Whether an iterator pair or a range class.

>
> > IMHO, the decision to shortcut from (c.begin(),c.end()) to (c) should be
> > done consciously, not as the default practice; otherwise, a program
might
> > end up stuck in a design that cannot exploit the flexibility of the
range
> > abstraction.
>
> How? If you can write '(c)', then you can always write '(c.begin(),
c.end())'
> as long as 'c' is a container. I don't see how support for '(c)' could
ever
> prevent using '(c.begin(), c.end())'.
>
I am refering -as the OP proposed- to the case were 'c' refers to a standard
container, with container semantics.
If 'c' is a range-like object, with efficient support for sub-ranging and
bidirectionality, then there's no problem.
But not even the VTL provides a significative promotion of containers to a
traversal-interface supporting subranging and bidirectionality with the
efficiency and flexibility of the [start,end) signature.

> As related issue, it is possible to write functions that return an object
that
> has a container-like interface (has begin() and end()), but refers to the
> elements of the container differently. In particular, I'm thinking about
the
> functions 'drop', 'take' and 'filter' (but there are many more, such as
'rev')
> that you can find in many functional languages. I don't see anything that
> could not be done with such a container reference, but could be done with
a
> pair of iterators to a container.
>
Show, for example, and algorithm that recurses itself in subranges, and that
the user can invoke to traverse in either direction using *just* std
containers and the vtl. Of course, being as efficient and easy to understand
as it would be with [start,end)

>
> As a related issue, there are often very good reasons for providing an
> enumeration interface like this:
>
>     struct not_primarily_a_container
>     { struct functor
>       { virtual void operator()(element_param_type) = 0;
>         // ...
>       };
>
>       virtual void for_each(functor& ) = 0;
>       // ...
>     };
>
> instead of an STL-style iteration interface.
>
But again, how do I use this container to do subranging.

> The choice between  active/external and passive/internal iteration should
be a conscious decision.
Agreed.

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com