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

From: John Torjo (john.lists_at_[hidden])
Date: 2003-11-20 12:26:46

>>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.

> 
> 
>>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

>  (I sincerely hope people use classes instead of naked arrays)
> 

Me too! I haven't used a naked array in years! (excapt for legacy code)

> 
>>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. 

In my coding days;) I have reached a very interesting conclusion.
(if anyone has a different oppinion, please share it, I'm really intrested to 
see what others think)

When you use an algorithm that returns an iterator (other than output iterator) 
you'll usually need to either traverse the remaining range, or ask if it's a 
valid iterator (!= .end() ).

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);

> 
> 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() )

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

> 
> 
>>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() );

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?

> 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.
> 

This is another think I don't quite like. You put the algorithms straight in 
namespace boost.
I'm not sure if that's such a good idea, since I can see people doing
'using namespace boost;' quite a lot, and also a lot of people do
'using namespace std;' and you got trouble;)

> 
> 
>>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:)
> 
> 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.

My point is that you should, for those, create specific adaptors, since in my 
experience the general version just doesn't cut it.

> 
> 
>>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.
The genericity of count is similar to boost::find, which I explained above.

>>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?

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));

> 
>>(behind the scenes, it only increments the begin() iterator,
>>  and has an operator bool() ).
> 
> safe-bool, preferably.
what do you mean?
> 
>>>what is the benefit of crange? AFAICT, irange is all we need.
>>
>>Syntactic sugar.
> 
> sugar to some, salt to others.
;)
The reason is this: the crange class takes a template parameter, which is a 
container (or another range;)). At first, the template parameter could also be 
an iterator. But Pavol Droba suggested - and thank him a lot for that! - that I 
split this into two classes. One that takes a container as parameter (crange), 
and one that takes an iterator as paramter (irange). This was a great idea, and 
simplified the code a lot.

So, all irange does is adapt the iterator and make it look like a container to 
crange.
In other words, you would need an adaptor class anyway, something like:
// solution 1
crange<container> r; // ok
crange<iterator_adapt<some_iterator_type> > r; // adapts iterator, making it 
look like a container

// solution 2
crange<container> r;
irange<some_iterator_type> r;

I went with solution 2, since it's much easier to use in code, and lot less to type.

> 
>>(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.
The only reason for deriving is to adapt the iterator class into a container 
class (typedefs), and to pass the iterators at construction. That's all.

Best,
John