[range] Is it conceivable to have it extended?
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. What I think is missing is the "parent" concept of a "sequence". Say, template<iterator_type, sentry_type> struct sequence { iterator_type begin(); sentry_type sentry(); }; Then "range" would implement and refine the "sequence" concept by template<iterator_type> struct range : sequence<iterator_type, iterator_type> { 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<typename Iterator, typename Sentry, typename Function> 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 ended up having such an "extended" range in Boost.Convert (to handle C string traversals efficiently) but I hate having/maintaining the code and much prefer the standard solution. Any suggestions? Vladimir.
On Monday 14 July 2014 07:10:23 Vladimir Batov 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 process (that is assuming the integer may not be the whole string; otherwise the end iterator is already provided by the range).
What I think is missing is the "parent" concept of a "sequence". Say,
template<iterator_type, sentry_type> struct sequence { iterator_type begin(); sentry_type sentry(); };
Then "range" would implement and refine the "sequence" concept by
template<iterator_type> struct range : sequence<iterator_type, iterator_type> { 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<typename Iterator, typename Sentry, typename Function> 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?
On 07/14/2014 10:00 AM, Andrey Semashev wrote:
On Monday 14 July 2014 07:10:23 Vladimir Batov 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 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<iterator_type, sentry_type> struct sequence { iterator_type begin(); sentry_type sentry(); };
Then "range" would implement and refine the "sequence" concept by
template<iterator_type> struct range : sequence<iterator_type, iterator_type> { 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<typename Iterator, typename Sentry, typename Function> 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<T*, typename enable_if<cnv::is_char<T>, void>::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<char const*> r(str); for_each(e.begin(), r.sentry(), fun); without finding the "end" first. V.
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.
What I think is missing is the "parent" concept of a "sequence". Say,
template<iterator_type, sentry_type> struct sequence { iterator_type begin(); sentry_type sentry(); };
Then "range" would implement and refine the "sequence" concept by
template<iterator_type> struct range : sequence<iterator_type, iterator_type> { 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<typename Iterator, typename Sentry, typename Function> 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 ended up having such an "extended" range in Boost.Convert (to handle C string traversals efficiently) but I hate having/maintaining the code and much prefer the standard solution.
Eric Niebler ran into the same problem and came up with a solution more or less along the same lines: an Iterable concept which generalizes a Range, which has begin and end iterators of potentially different types [1]. My understanding is that Eric plans to present a library implementing his approach at the next C++ standards committee meeting in November. Regards, Nate [1] http://ericniebler.com/2014/02/21/introducing-iterables/
Thanks for the link. I'll certainly have a look... Uhm, it's in Nov. and for C++ standard committee. So, it's in far perspective... and the industry I am in is always a few years behind the Standard. :-( Would not that be possible/sensible to address that in Boost for the time being? On 07/14/2014 12:22 PM, Nathan Ridge wrote:
Eric Niebler ran into the same problem and came up with a solution more or less along the same lines: an Iterable concept which generalizes a Range, which has begin and end iterators of potentially different types [1].
My understanding is that Eric plans to present a library implementing his approach at the next C++ standards committee meeting in November.
Regards, Nate
[1] http://ericniebler.com/2014/02/21/introducing-iterables/
Thanks for the link. I'll certainly have a look... Uhm, it's in Nov. and for C++ standard committee. So, it's in far perspective... and the industry I am in is always a few years behind the Standard. :-( Would not that be possible/sensible to address that in Boost for the time being?
Last I spoke to Eric, he had no plans to propose his library (which, by the way, can be found here [1]) to Boost, but that doesn't mean someone else who's willing to do the work couldn't. I'm curious what Neil thinks of this library as a possible future direction for Boost.Range. Regards, Nate [1] https://github.com/ericniebler/range-v3
On 7/13/2014 9:12 PM, Nathan Ridge wrote:
Thanks for the link. I'll certainly have a look... Uhm, it's in Nov. and for C++ standard committee. So, it's in far perspective... and the industry I am in is always a few years behind the Standard. :-( Would not that be possible/sensible to address that in Boost for the time being?
Last I spoke to Eric, he had no plans to propose his library (which, by the way, can be found here [1]) to Boost, but that doesn't mean someone else who's willing to do the work couldn't.
Right. I'm not opposed to getting it into Boost. It's just that C++17 is closer than you might think, and my #1 priority to getting ranges into the standard.
I'm curious what Neil thinks of this library as a possible future direction for Boost.Range.
Me too.
-- Eric Niebler Boost.org http://www.boost.org
participants (4)
-
Andrey Semashev -
Eric Niebler -
Nathan Ridge -
Vladimir Batov