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

From: John Torjo (john.lists_at_[hidden])
Date: 2003-11-19 18:42:17

Hi Thorsten,

> 
> If I had known that you intended to support algorithms, I would have
> contacted you sooner.
;)
> 

> 
> have you looked at the sequence_algo dir in the sandbox? For quite some time
> there have been container algorithms in there. This was the main motivation
> for
> having container traits.

Took a look at container_traits and container_algo.

Not sure why they got so little attention, this concept really rocks!

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

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

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

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)

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

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

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.

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

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.

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.

> 
> Please see Pavol's iterator_range class that was bundled with his string
> algorithms.

Did that, also talked to Pavol privately.

> You might won't to read some of the threads on our discussion of a range
> class.
> 

Will take another look - I know there were some discussions about this.
As I have picked up, the rtl range<> class can be used in string_algo as well 
(it's a superset of iterator_range).
But need to dig deeper.

>>while( r)
>>    std::cout << *r++ << std::endl;
> 
> 
> This seems like something that could be useful. Recently Eric presented his
> FOR_EACH macro
> which made traversing easy. It seems that this class is a bit like an
> iterator, maybe it could be
> a range_iterator<> on its own? (I haven't looked at the code, but I assume
> it's possible to pass two iterator's as argument to the constructor).
Indeed!
It's quite simple. Given a container, if you want to traverse manually, you do:
crange<container> r(c);
while (r) {
// do whatever
++r;
}

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

> 
> 
>>You can also manually set the beginning and end of a range:
>>// ignore first and last 5 elements
>>r.begin( v.begin() + 5);
>>r.end( v.end() - 5);
>>while( r)
>>    std::cout << *r++ << std::endl;
> 
> 
> why not just make a new one providing the smaller range as arguments to the
> constructor?

That is possible anyway.
The example was misleading. The idea is that if you want to change only the 
begin, or only the end, you can do it like shown above (instead of 
reconstructing the object)

> 
> 
>>The basic range classes are:
>>template< class container> class crange;
>>template< class iterator> class irange;
>>
>>Examples of usage:
>>crange< const container> r(...); // const range
>>crange< container> nr( ...); // non-const range
>>irange< iterator_type> ir(...); // from iterator
>>
>>A range can be created from a container/const container/2 iterators.
>>crange< container> r( cont); // const or non-const container
>>crange< container> r( beg, end); // two iterators
>>
> 
> what is the benefit of crange? AFAICT, irange is all we need.

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

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

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

> 
> As mentioned, there has already been some discussions regarding this. In the
> files section, one can find
> Jeremy's collection cencept which seems like the right thing (without

Yup, it looks right.

Now that I think about it, a range concept does not even need to be so complicated.
As explained above (in the original message):
- a range is a pair of iterators
- it has typedefs for value_type,pointer,reference
   (no const_pointer,no const_reference)
- it's got begin() and end()
- it's got an operator bool() that returns true if the
   range is non-empty.

Best,
John