Re: [boost] [range] Is it conceivable to have it extended?

14 Jul 2014

      On 07/14/2014 10:00 AM, Andrey Semashev wrote:
...
...
boost::iterator_range is a great concept/class but it does not seem to
play efficiently with certain input sequences and seem to be too strong
a requirement for certain algorithms. I have an old-fashioned C string
in mind (I am sure there are other examples) and traversing algorithms.
When I tried deploying boost::iterator_range for string-to-int
conversion purposes, I quickly realized that I was traversing the string
twice -- first to find the end and second to do the work.
Not sure why would you need to find the end - it can be found in the parsing
On Monday 14 July 2014 07:10:23 Vladimir Batov wrote:
process (that is assuming the integer may not be the whole string; otherwise
the end iterator is already provided by the range).
"Otherwise" means I have to have two implementations for ranges (where I 
check it != end) and for sequences (like C strings) where I do not have 
"end" and, therefore, check "for (char* p = beg; *p; ++p)". 
Alternatively, to have one implementation, we usually convert a C string 
to a range with boost::as_literal() and then call the range-based 
function. boost::as_literal() does the first traversal to fing the end.
...
...
What I think is missing is the "parent" concept of a "sequence". Say,
template
struct sequence
{
      iterator_type begin();
      sentry_type sentry();
};
Then "range" would implement and refine the "sequence" concept  by
template
struct range : sequence
{
      iterator_type begin();
      iterator_type end();
      sentry_type sentry() { return end; }
}
I.e., as "range" implements/is the "sequence", the boost::iterator_range
will have one additional "useless" sentry() method.
That way all the old code (using and/or needing end()) would still work
but traversing algorithms might gradually adapt to only require
"sequences" instead of "ranges":
template
Function
for_each(Iterator beg, Sentry sentry, Function fun)
{
      for (; beg != sentry; ++beg) fun(*beg);
      return fun;
}
That means that now all "open-ended" (with no known "end") "ranges"
(they are not even "ranges" in the strict meaning of the word but rather
"sequences") can be handled efficiently.
I don't see much difference with the current ranges, where end iterators are
singular. Can you provide a strong motivating example for the sentry() method?
The difference is that "sentry" does not have to be an iterator... and 
it is not in the case of "sequences". Below is the "extended" range 
(which is a "sequence") specialization for a C string:

     template<typename T>
     struct range::type>
     {
         typedef typename remove_const<T>::type char_type;
         typedef T* iterator;

         struct sentry_type
         {
             friend bool operator!=(iterator it, sentry_type const&) { 
return !!*it; }
         };

         range (T* b, T* e =0) : begin_(b), end_(e) {}

         iterator const begin () const { return begin_; }
         iterator const   end () const { return end_ ? end_ : (end_ = 
begin_ + strlen(base_)); }
         sentry_type    sentry () const { return sentry_type(); }

         private:

         iterator       begin_;
         mutable iterator end_;
     };

That allows traversals without finding the end (i.e. extra traversal to 
find "end").

Namely, it still works with std::for_each(). However, is now can work 
more efficiently with the "for_each" I showed above, i.e.

     char const* str = ...;
     range r(str);

     for_each(e.begin(), r.sentry(), fun);

without finding the "end" first.

V.