[boost] Re: Re: rtl (Range Template Library)

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2003-11-19 03:55:29

"John Torjo" <john.lists_at_[hidden]> wrote in message
news:3FBBFFD9.4000601_at_torjo.com...

> Took a look at container_traits and container_algo.
>
> Not sure why they got so little attention, this concept really rocks!

thanks.

> Anyway, I like the find algoritm, still do find it a little dangerous
> (if it's a collection, to go search for key.
>   In our library, we have coll_find, which clearly states that you have a
> collection).

what's the danger again?

> Also, the container_algo as is now won't compile for VC6 (due to one of
its
> stupid bugs).

this will be totally dependent on how portable the container traits can be
made, so far
vc6 support is no problem for std container or range-like classes; the
trouple is arrays.
Pavol made a mpl-hack that could make this work for built-in types, but I'm
not convinved it's the way
to go since it complicates the code; and besides, I would like to see people
that need the support
 (I sincerely hope people use classes instead of naked arrays)

> In rtl, some algorithms return a range. For instance, find_if.
> It returns the range from the found iterator, up to end().
> Therefore, you can use it in code like this:
> range<const container> found = rng::find_if(c, pred);
> if (found) {
> // whatever - you can for instance, walk through the remaining elements.
> }

I see, I guess there is a difference here then :-) My algorithms are
strictly a layer on top of the standard
algorithms. Pavol Droba's string algorihtms also return iterator ranges; but
in them you also search for
a range.

In your example above, you will be incompatible with the standard
algorithms; it's not a big win to
replace if( found ) with if( found != c.end() ) (though I do like
range-returning algos to support that.)

> In the future, we plan to allow the user to select what he expects,
something like:
> rng::find_if<iter>(c,pred); // returns the iterator
> rng::find_if<to_end>(c,pred); // returns the range [found,end)
> rng::find_if<from_beg>(c,pred); // returns the range [beg,found)

The idea is nice, but I might not think it is worth the trouple. If some
kind of range class
existed (like iterator_range<>), you could do all those with just the
iterator version;
The range stuff would make it easier if you needed a range and harder if you
only needed an
iterator and vice versa for the iterator version; however, the iterator
version is already standard
and seems a lot simpler to implement too; If, however, the algortihms where
searching for
a subrange (as Pavo's does) it would be natural (necessary) to return a
range.

> Also, don't understand why in container_algo you have adjacent_find in the
ext
> namespace.

the ext namespace is there to prevent overload ambiguities with
std-algorihtms.
I think that it might be resolved  with enable_if though.

> About container_traits:
> I'm not sure iterator_traits is such a good idea. Mixing iterators and
> containers can lead to trouble (this is a great advice, coming from Pavol
Droba!)

yeah, we  should really remove those iterators from the standard containers
:-)

> For instance, a user could mistakenly do:
> boost::find_first_of( container,iterator);
>
> This will actually compile with quite a misleading result, in case
> the iterator type is default constructible
> std::find_first_of(
>    c.begin(), c.end(), iterator, iterator_type() // default constructor
> );
>
> This does not happen in rtl - we don't allow that.

ok, but why would anybody do so?

OTOH, there was people saying (and I think Alisdair was one of them) that
they still wanted the algos to work with default constructed iterators.

> I'm not sure the genericity of boost::count() is needed
> (to search for a key within collections). The genericity rocks, but I
think it's
> misleading (same as for find).

I'm missing your point here; please explain.

> Again, why some algorithms are in namespace ext?
>
> I don't like remove_and_erase/remove_and_erase_if, since they are just two
> algorithms. There are many more erase algorithms uncovered.

I'm not the author of those; I think it is Vladimir Prus. I'm not in favor
of them either.

> In rtl, we have:
> rng::erase( container, some_erase_algo);
>
> Example:
> rng::erase( c, std::unique(c) );
>
> This allows for all erase algorithms to work.

what does this do?

> (behind the scenes, it only increments the begin() iterator,
>   and has an operator bool() ).

safe-bool, preferably.

> > what is the benefit of crange? AFAICT, irange is all we need.
>
> Syntactic sugar.

sugar to some, salt to others.

> If, in your code, you know the type of the container, you use
> // crange = container range
> crange<container> r(...); //non-const
> crange<const container> r(..); // const
>
> However, if in your code, you only know the iterator type (but not the
container
> type), you can use irange.
> // irange = iterator range.
> irange<some_iterator_type> i(...);
>
> It's up to you.

there is really not much to win by having 2 classses. It will however, make
the implementation bigger and force the programmer to learn/read more
docs/code.

> (as a side-note, irange derives from crange)

if so publicly, it has a virtual destructor? I mean, we don't get
undefined behavior when deleting a pointer to a crange which really points
to a irange?

> >
> >
> >// prints the given list to console
> >>rng::copy( l, std::ostream_iterator<int>(std::cout," ") );
> >
> >
> > there is no major difference between this and the stuff in the sandbox.
One
> > thing
> > might be that if the container traits (soon to be rename collection
traits)
> > is used, we can use ordinary arrays too with the algorithms.
>
> Indeed, however there are a few facts that I donot like about those (see
above).
> Note also the fact about what we're trying to do with the algorithms that
return
> ranges.

noted. As I said above, I think that should be for algorithms that actually
search etc
on ranges, not for algos that find a single element.

besy regards

Thorsten