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

From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2003-11-19 23:14:17

"John Torjo" <john.lists_at_[hidden]> wrote in message
news:3FBCF956.6040703_at_torjo.com...
> >>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?
>
> If it's a collection, you actually do a find by key ( coll.find(v)), so
the
> actual value type you're sending when using boost::find, is the key_type,
not
> value_type.
>
> This IMO means that the user still needs to know about the fact that the
> container he's searching is a collection (associative array).
> Otherwise, a compile-time error would occur.
>
> In other words:
> std::map<int,std::string> m;
> boost::find(m, 2);
> // this calls m.find(2)
>
> As said above, the programmer still needs to know that this is a
collection. If
> he does, I guess it would be clearer to just say:
> m.find(2) instead of boost::find.

maybe.

> >>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
>
> It has nothing to do with container traits.
> It's got to do with the fact that the following won't work with VC6:
>
> template<class T> void f( const T&) {}
> template<class T> void f( T&) {}
> const std::deque<int> d;
> f(d); // compile-time error in VC6

true. that's why the collection traits allows you to remedy this.
You simply provide one function wuth a T& argument and
use some metaprogramming to figure out the rest. You do loose the
probability to use rvalues, but vc6 users just have to accept that.

[snip]
> Most of the time you need the range from the found iterator up to the
.end() of
> the container (in my experience - looked at some of my previous code).
>
> // plays very nice with range classes
> crange<container> r = rng::find_if( cont, pred);
> if (r) {
>    // do something with *r, even walk up to the .end(), if you wish
> }
>
> //plays very nice with algorithms
> // (taken from real-life code)
> rng::erase( m_snapshots, rng::unique( m_snapshots, snapshot_eq_time) );
>
> The above line uses ::std::unique to remove the duplicates (move them to
the end
> of the range, and returns then range of elements to be erased. Then
rng::erase
> calls m_snapshots.erase( remaining_range);

m_snapshots.erase( boost::unique( m_snapshots, snapshot_eq_time ),
m_snapshots.end() );

or with Pavols algos

erase_range( m_snapshots, make_iterator_range( unique( m_snapshots,
snapshot_eq_time ), m_snapshots.end() ) );

which could certainly be better. Maybe we need an erase_from(), erase_util()
took a single iterator?

> > 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.)
>
> You might think so.
> But, remember that in real code you'll use long names, etc.
> I designed ranges to even be returned from member-functions, instead of
the
> containers themselves. Imagine something like:
>
> // taken from real-life code
> if ( get_account_history().pending_orders().find( order_id) !=
> get_account_history().pending_orders().end() )

seriously, you're joking right? I would definitely make a temporary or
make a function that gave me the pending_orders. real life should never be
more complicated than

order_t orders = ...;
if( orders.find( order_id ) != orders.end() )

if it is, something else is wrong and a refactoring needs to be done.

> Indeed, in real-life it can get nasty.
> So I think that being able to say just:
> if (found)
> is a big advantage.

If the algorithm does indeed return a range, then I agree this is preferred.

> >
> >>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
> it does;)
>
> > iterator version;
>
> This is the purpose of the rtl: to eliminate redundant code.
> Besides being redundant, again, it could get real messy in real-life code.
>
> Imagine again:
> //
> some_range_class r( boost::find_if(
get_account_history().pending_orders(),
> pred), get_account_history().pending_orders().end() );

Please imagine

order_t orders = get_account_history().pending_orders();
some_range_class r( boost::find_if( orders, pred), orders.end() );

> compared to:
> some_range_class r = rtl::find_if(get_account_history().pending_orders(),
pred));

> > 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
>
> That's why in the future we want to provide the possibility to return an
> iterator as well - just in case you want it.
> And I think you have a very strong case - maybe we can return an iterator
by
> default, and if specified like rtl::find_if<to_end>, return a range.
>
> What do you think?

It seem ok, but I don't feel it's quite there. The hard thing must be to get
it down to a
minimum of algortihms.

> >>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
> >>);
> >>
> > ok, but why would anybody do so?
>
> Because it's possible:)

sure, we have to provide some compile time cheking, but we can't guard
agaist
stupidity or malicity. so I don't think it's a problem.

> >>Example:
> >>rng::erase( c, std::unique(c) );
> >>
> >>This allows for all erase algorithms to work.
> >
> > what does this do?
>
> For an erase algorithm, you have something like:
>
> c.erase( some_erase_algorithm( c.begin(), c.end() ...), c.end() );
>
> What rng::erase does is, call the erase algorithm (unique, remove,
remove_if,
> etc.), and that returns a range. Then calls c.erase( result_range.begin(),
> result_range.end() );
>
> So:
> c.erase( some_erase_algorithm( c.begin(), c.end() ...), c.end() );
>
> is equivalent to:
> rng::erase( c, some_erase_algorithm(c));

ok, then if we had erase_XX we could do

erase_from( c, std::unique( c ) );
erase_to( c, std::unique( c ) );

which is better?

>
> >
> >>(behind the scenes, it only increments the begin() iterator,
> >>  and has an operator bool() ).
> >
> > safe-bool, preferably.
> what do you mean?

not an operator bool(), but something convertible to bool (like a pointer to
a member) to prohibit misuse.

> >
> >>(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?
> Just take a look at the code, there's no need for that.

yep, sorry.

best regards

Thorsten