[range][algorithm] Looking for STL adaptations
Hi Everyone, Upon my daily chugging along with the very excellent Boost libraries, I notice that I found myself writing a lot of boilerplate still granted that we already have excellent libraries: Boost.Iterator, Boost.Range, some of which aren't really that hard to implement in a generic library such as Boost. Here's a couple of things that might be good to ponder about, if people have the time to collaboratively build these libraries: * Boost.Range friendly versions of the STL algorithms -- although this may be coming up in C++0x, seeing a version of std::copy, std::transform, etc. that work with Boost.Range+Boost.Iterator combo's will be very welcome. A simple code case is: std::copy( boost::make_filter_iterator_range( is_even() ), boost::make_function_output_iterator( my_serializer() ) ); * SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following: template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; }; So that you can go ahead and see code like (with the STL adapters from above): std::transform( boost::make_range(my_map), select<1>(), std::ostream_iterator<my_map::value_type::second_type>(std::cout) ); If this is already under works, I'd love to find documentation or at least progress. If this is already done and can be found somewhere, links would be greatly appreciated. If there's interest, perhaps we can build this in the sandbox and eventually get it reviewed and submitted as part of boost? Have a great day everyone, and keep them excellent libraries coming! -- Dean Michael C. Berris Software Engineer, Friendster, Inc. [http://cplusplus-soup.blogspot.com/] [mikhailberis@gmail.com] [+63 928 7291459] [+1 408 4049523]
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms -- although this may be coming up in C++0x, seeing a version of std::copy, std::transform, etc. that work with Boost.Range+Boost.Iterator combo's will be very welcome. A simple code case is:
std::copy( boost::make_filter_iterator_range( is_even() ), boost::make_function_output_iterator( my_serializer() ) );
You can try Oven @ http://www.boost-consulting.com/vault/index.php?directory=Algorithms Using it, copy(your_rng|filtered(is_even()), applier(my_serializer());
std::transform( boost::make_range(my_map), select<1>(), std::ostream_iterator<my_map::value_type::second_type>(std::cout) );
Using Oven, copy(my_map|map_values, stream_writer(std::cout)); std::transform will be obsolete by range adaptors, IMO. Regards, -- Shunsuke Sogame
On 11/19/07, shunsuke <pstade.mb@gmail.com> wrote:
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms -- although this may be coming up in C++0x, seeing a version of std::copy, std::transform, etc. that work with Boost.Range+Boost.Iterator combo's will be very welcome. [...]
You can try Oven @ http://www.boost-consulting.com/vault/index.php?directory=Algorithms
[...] copy(your_rng|filtered(is_even()), applier(my_serializer());
[...] copy(my_map|map_values, stream_writer(std::cout)); std::transform will be obsolete by range adaptors, IMO.
So will be many of the *_if variants of the std algorithms. I use my own simple wrappers around boost::filter_iterator and boost::transform_iterator and are a pleasure to use. -- gpd
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms
The Range_ex library is quite possibly what you're looking for. http://www.boost-consulting.com/vault/index.php?directory=Algorithms Documentation is here: http://boost-sandbox.sf.net/libs/range_ex This work is based on an earlier containers algorithm library by Jeremy Siek and Vladimir Prus.
* SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following:
template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; };
So that you can go ahead and see code like (with the STL adapters from above):
std::transform( boost::make_range(my_map), select<1>(), std::ostream_iterator<my_map::value_type::second_type>(std::cout) );
Could be pretty useful. I'm not aware of anything like this in Boost already. -- Eric Niebler Boost Consulting www.boost-consulting.com
Hi Eric! On Nov 19, 2007 11:54 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms
The Range_ex library is quite possibly what you're looking for.
http://www.boost-consulting.com/vault/index.php?directory=Algorithms
Documentation is here:
http://boost-sandbox.sf.net/libs/range_ex
This work is based on an earlier containers algorithm library by Jeremy Siek and Vladimir Prus.
Thank you very much! This definitely looks like something worth looking at. Is there any chance this work can get completed soon? Or is there just too many STL algorithms to 're-implement'? I'm quite possibly looking at helping here if there's anybody else needing help with the implementation of this library.
* SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following:
template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; };
So that you can go ahead and see code like (with the STL adapters from above):
std::transform( boost::make_range(my_map), select<1>(), std::ostream_iterator<my_map::value_type::second_type>(std::cout) );
Could be pretty useful. I'm not aware of anything like this in Boost already.
Great! So in this regard, I'm attaching a simple initial implementation of the select<> template. If there's anyone interested in expounding on this library, I don't mind getting all the help I can get. Currently it's tested and made to generalize the selector function object to work with std::pair<,>'s and boost::tuple<>'s. Could this simple header library be put into the Fast Track review queue? -- Dean Michael C. Berris Software Engineer, Friendster, Inc. [http://cplusplus-soup.blogspot.com/] [mikhailberis@gmail.com] [+63 928 7291459] [+1 408 4049523]
Dean Michael Berris wrote:
Hi Eric!
On Nov 19, 2007 11:54 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms The Range_ex library is quite possibly what you're looking for.
http://www.boost-consulting.com/vault/index.php?directory=Algorithms
Documentation is here:
http://boost-sandbox.sf.net/libs/range_ex
This work is based on an earlier containers algorithm library by Jeremy Siek and Vladimir Prus.
Thank you very much! This definitely looks like something worth looking at. Is there any chance this work can get completed soon? Or is there just too many STL algorithms to 're-implement'?
Oh it's "complete", as in all the STL algorithms are represented.
I'm quite possibly looking at helping here if there's anybody else needing help with the implementation of this library.
There are some surprisingly thorny issues wrt range-based algorithms, which I list in the appendix of the range_ex docs. In particular, does an "output range" make sense? Range_ex uses output iterators instead of output ranges. At the time, I thought that was unsatisfactory. Less so now, but it's still an open issue.
* SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following:
template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; }; <snip>
Could this simple header library be put into the Fast Track review queue?
I think I would make this part of boost/functional.hpp, but I'm not sure who is maintaining that these days. -- Eric Niebler Boost Consulting www.boost-consulting.com
Eric Niebler wrote: ...
There are some surprisingly thorny issues wrt range-based algorithms, which I list in the appendix of the range_ex docs. In particular, does an "output range" make sense? Range_ex uses output iterators instead of output ranges. At the time, I thought that was unsatisfactory. Less so now, but it's still an open issue.
What's the issue with returning a range? How else can they be chained? What is your opinion of this style of algorithm? template<typename out_t, typename in_t> inline out_t algorithm (in_t const& in) { out_t out (boost::size (in)); assuming output size same as input do_something_with(in) return out; } This assumes return value optimization, which I've verified on recent gcc.
You might also want to lookat dataflow iterators in the serializaiton library. RObert Ramey Eric Niebler wrote:
Dean Michael Berris wrote:
Hi Eric!
On Nov 19, 2007 11:54 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Dean Michael Berris wrote:
* Boost.Range friendly versions of the STL algorithms The Range_ex library is quite possibly what you're looking for.
http://www.boost-consulting.com/vault/index.php?directory=Algorithms
Documentation is here:
http://boost-sandbox.sf.net/libs/range_ex
This work is based on an earlier containers algorithm library by Jeremy Siek and Vladimir Prus.
Thank you very much! This definitely looks like something worth looking at. Is there any chance this work can get completed soon? Or is there just too many STL algorithms to 're-implement'?
Oh it's "complete", as in all the STL algorithms are represented.
I'm quite possibly looking at helping here if there's anybody else needing help with the implementation of this library.
There are some surprisingly thorny issues wrt range-based algorithms, which I list in the appendix of the range_ex docs. In particular, does an "output range" make sense? Range_ex uses output iterators instead of output ranges. At the time, I thought that was unsatisfactory. Less so now, but it's still an open issue.
* SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following:
template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; }; <snip>
Could this simple header library be put into the Fast Track review queue?
I think I would make this part of boost/functional.hpp, but I'm not sure who is maintaining that these days.
Eric Niebler wrote:
There are some surprisingly thorny issues wrt range-based algorithms, which I list in the appendix of the range_ex docs. In particular, does an "output range" make sense? Range_ex uses output iterators instead of output ranges. At the time, I thought that was unsatisfactory. Less so now, but it's still an open issue.
OutputIterator doesn't have an end iterator. So, I think OutputIterator can't be a range. I tend to think OutputIterator is not even Iterator, per se. BTW, infinite range is possible. Regards, -- Shunsuke Sogame
Hi Eric! On Nov 19, 2007 12:17 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Dean Michael Berris wrote:
Thank you very much! This definitely looks like something worth looking at. Is there any chance this work can get completed soon? Or is there just too many STL algorithms to 're-implement'?
Oh it's "complete", as in all the STL algorithms are represented.
Ah. The documentation "TODO's" are there to throw me off... Thank for the links! Will this get into Boost through the Boost.Range library, or will it go through a different review?
I'm quite possibly looking at helping here if there's anybody else needing help with the implementation of this library.
There are some surprisingly thorny issues wrt range-based algorithms, which I list in the appendix of the range_ex docs. In particular, does an "output range" make sense? Range_ex uses output iterators instead of output ranges. At the time, I thought that was unsatisfactory. Less so now, but it's still an open issue.
When I look at the SGI extensions to the STL, there are versions of std::transform that take in a couple of ranges: one an input iterator range, and another an output iterator range. These make sense if you're putting the results of a function application f(x) into a predefined range usually associated with a non-const container. Example: std::transform( input_range(my_vector), output_range(other_vector), f() ); The preconditions are that output_range's size and input_range's size are the same. This can also be extended to the concept of an infinite range, in cases of the ostream_iterator: std::transform( input_range(my_vector), ostream_range(std::cout), f() ); For the precise case also for when you want the transformation 'f(x)' are applied to the same input range: std::transform( input_range(my_vector), output_range(my_vector), f() ); I hope this makes a case for output ranges -- but then they can be precisely overloads of std::transform, which they precisely are.
* SGI's select1st and select2nd generalized -- I'm not sure if you've found yourself dealing with std::map's and std::list<std::pair<,> >'s a lot, but I do, and there is a lot of merit in something like the following:
template <const N> struct select { template <class T> mpl::at_c<T, N>::type operator() (T element) const { return mpl::at_c<T, N>(element); }; }; <snip>
Could this simple header library be put into the Fast Track review queue?
I think I would make this part of boost/functional.hpp, but I'm not sure who is maintaining that these days.
That makes sense as well. I'll try starting another thread for this one. -- Dean Michael C. Berris Software Engineer, Friendster, Inc. [http://cplusplus-soup.blogspot.com/] [mikhailberis@gmail.com] [+63 928 7291459] [+1 408 4049523]
On Nov 19, 2007 1:01 AM, Dean Michael Berris <mikhailberis@gmail.com> wrote:
* Boost.Range friendly versions of the STL algorithms
The Adobe Source Library's range/bind-friendly versions of the standard algorithms might also be of some use to you: <http://opensource.adobe.com/group__stl__algorithm.html> -Mat
Mat Marcus wrote:
On Nov 19, 2007 1:01 AM, Dean Michael Berris <mikhailberis@gmail.com> wrote:
* Boost.Range friendly versions of the STL algorithms
The Adobe Source Library's range/bind-friendly versions of the standard algorithms might also be of some use to you: <http://opensource.adobe.com/group__stl__algorithm.html>
Interesting, Adobe stayed away from output ranges, too. Also interesting that the algos that take 2 input sequences (e.g., transform) take a range and an iterator instead of two ranges. That's another thorny issue. I went the other way, I think. Does Adobe has a design rational for these algos? -- Eric Niebler Boost Consulting www.boost-consulting.com
On Nov 19, 2007 10:37 PM, Eric Niebler <eric@boost-consulting.com> wrote:
Mat Marcus wrote:
On Nov 19, 2007 1:01 AM, Dean Michael Berris <mikhailberis@gmail.com> wrote:
* Boost.Range friendly versions of the STL algorithms
The Adobe Source Library's range/bind-friendly versions of the standard algorithms might also be of some use to you: <http://opensource.adobe.com/group__stl__algorithm.html>
Interesting, Adobe stayed away from output ranges, too. Also interesting that the algos that take 2 input sequences (e.g., transform) take a range and an iterator instead of two ranges. That's another thorny issue. I went the other way, I think. Does Adobe has a design rational for these algos?
I've gone too for the route of taking two ranges instead of a range and an iterator. My rationale was that it is much easier to compose algorithm invocations this way. Also I do bound checking on *both* sequences, not only the first (i.e. i iterate 'till the end of the shorter sequence), If you do not bound checks both sequences, taking a range as second parameter might be misleading. Finally, I didn't implement the two parameter transform. I use the single parameter one composed with zip (which, unlike boost::zip_iterator, stops at the end of the smaller sequence). I only provide algorithms that take two sequences if I have to iterate on the sequences at different speed, like in std::merge or in a relational join. BTW, I've been wondering if algorithms that return a single iterator, should return instead a range: for example upper_bound should return [first, found), lower_bound should return [found, end) and equal_range the intersection of the two i.e. [lower_found, upper_found). -- gpd
Giovanni Piero Deretta wrote:
Finally, I didn't implement the two parameter transform. I use the single parameter one composed with zip (which, unlike boost::zip_iterator, stops at the end of the smaller sequence). I only provide algorithms that take two sequences if I have to iterate on the sequences at different speed, like in std::merge or in a relational join.
BTW, std::merge too will be obsolete by range adaptor `merged`.
BTW, I've been wondering if algorithms that return a single iterator, should return instead a range: for example upper_bound should return [first, found), lower_bound should return [found, end) and equal_range the intersection of the two i.e. [lower_found, upper_found).
For some reason, user might want [found, end) from upper_bound. Fortunately every algorithm of Oven is a FunctionObject which can be used with Boost.Lambda, so that you can write `rng|applied(bind(upper_bound, _1, v), end)`. Lambda support seems essential feature for functional programming. Regards, -- Shunsuke Sogame
Eric Niebler wrote:
Interesting, Adobe stayed away from output ranges, too. Also interesting that the algos that take 2 input sequences (e.g., transform) take a range and an iterator instead of two ranges. That's another thorny issue. I went the other way, I think. Does Adobe has a design rational for these algos?
My rationale was that "if an algorithm doesn't need a range, you don't need to pass a range.". So, Oven went the same way as adobe. If you need bounds-checking, a range adaptor `checked` is useful. After all, you don't need to be worried about algorithms which will be obsolete. :-) -- Shunsuke Sogame
participants (7)
-
Dean Michael Berris -
Eric Niebler -
Giovanni Piero Deretta -
Mat Marcus -
Neal Becker -
Robert Ramey -
shunsuke