[algorithm] adjacent_for_each interest?
Hi, Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range? #include <iostream> #include <boost/algorithm/adjacent_for_each.hpp> void PrintInts(int a, int b) { std::cout << '(' << a << ", " << b << ")\n"; } int main() { const int ints[] = {0, 1, 2, 3, 4}; boost::algorithm::adjacent_for_each(ints, ints + 5, PrintInts); } Output: (0, 1) (1, 2) (2, 3) (3, 4) Initial implementation available at http://github.com/irh/adjacent_for_each Best, Ian
10.02.2013 17:10, Ian Hobson:
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range? [...] Initial implementation available at http://github.com/irh/adjacent_for_each
I have implemented for_each_adjacent on project I worked on (sorry, can't share source). I had two versions: for InputIterator and ForwardIterator. Selection was implemented as tag dispatching of iterator_category. You need special version for InputIterator which maintains temporary copy of value_type, due to 24.1.1/3: [Note: For input iterators, a == b does not imply ++a == ++b. (Equality does not guarantee the substitution property or referential transparency.) Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms.] In this regard your version at https://github.com/irh/adjacent_for_each/blob/master/boost/algorithm/adjacen... is broken. Because it advertises to work on InputIterator, but it dereferences iterator at same position several times. As the result current implementation is for ForwardIterator. P.S. Consider implementation of companion - transform_adjacent. Maybe even consider version which accepts "count of adjacent elements within each iteration" as template non-type parameter. Or maybe choose some another approach involving Boost.Range? -- Evgeny Panasyuk
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range? [...]
P.S. Consider implementation of companion - transform_adjacent. Maybe even consider version which accepts "count of adjacent elements within each iteration" as template non-type parameter. Or maybe choose some another approach involving Boost.Range?
I think a more general approach would be a Boost.Range-style range adaptor [1] that presents a view of the range where elements in the view are pairs of (references to, if desired) elements in the underlying range. You can then use standard algorithms like for_each and transform on the adapted range. I have written such an adaptor in the past and called it 'adjacent_paired'. I've also seen (can't remember where) the name 'windowed' used for the more general version which presents a view of tuples of N adjacent elements. Regards, Nate [1] http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/ada...
11.02.2013 2:17, Nathan Ridge:
P.S. Consider implementation of companion - transform_adjacent. Maybe even consider version which accepts "count of adjacent elements within each iteration" as template non-type parameter. Or maybe choose some another approach involving Boost.Range?
I think a more general approach would be a Boost.Range-style range adaptor [1] that presents a view of the range where elements in the view are pairs of (references to, if desired) elements in the underlying range. You can then use standard algorithms like for_each and transform on the adapted range.
I have written such an adaptor in the past and called it 'adjacent_paired'. I've also seen (can't remember where) the name 'windowed' used for the more general version which presents a view of tuples of N adjacent elements.
Yes, I was thinking about something like that - use tuple views. Just for example(of tuple views): int arr[] = {0,1,2,3,4,5}; for_each ( make_zip_iterator( make_tuple(arr+0, arr+1) ), make_zip_iterator( make_tuple(end(arr)-1, end(arr)) ), cout << lambda::_1 << " " ); or boost::for_each ( combine(arr | sliced(0,size(arr)-1), arr | sliced(1,size(arr))), cout << lambda::_1 << " " ); output: (0 1) (1 2) (2 3) (3 4) (4 5) By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website. -- Evgeny Panasyuk
By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website.
I don't see it used as a helper by anything else, so I'm guessing it should be public API. I filed a ticket for documenting it: https://svn.boost.org/trac/boost/ticket/8028 Regards, Nate
On 2/11/2013 5:09 AM, Evgeny Panasyuk wrote:
11.02.2013 2:17, Nathan Ridge:
P.S. Consider implementation of companion - transform_adjacent. Maybe even consider version which accepts "count of adjacent elements within each iteration" as template non-type parameter. Or maybe choose some another approach involving Boost.Range?
I think a more general approach would be a Boost.Range-style range adaptor [1] that presents a view of the range where elements in the view are pairs of (references to, if desired) elements in the underlying range. You can then use standard algorithms like for_each and transform on the adapted range.
I have written such an adaptor in the past and called it 'adjacent_paired'. I've also seen (can't remember where) the name 'windowed' used for the more general version which presents a view of tuples of N adjacent elements.
Yes, I was thinking about something like that - use tuple views.
Just for example(of tuple views):
int arr[] = {0,1,2,3,4,5};
for_each ( make_zip_iterator( make_tuple(arr+0, arr+1) ), make_zip_iterator( make_tuple(end(arr)-1, end(arr)) ), cout << lambda::_1 << " " );
or
boost::for_each ( combine(arr | sliced(0,size(arr)-1), arr | sliced(1,size(arr))), cout << lambda::_1 << " " );
output: (0 1) (1 2) (2 3) (3 4) (4 5)
By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website.
Nice find! I've been missing a zip_range! A few useful additions would be a corresponding adaptor and exposed range type(s) that are currently in the detail namespace. Jeff
By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website.
Nice find! I've been missing a zip_range! A few useful additions would be a corresponding adaptor
Do you mean 'r1 | zipped(r2)' in the place of 'zip(r1, r2)'? Somehow the asymmetry of that offends me... Regards, Nate
12.02.2013 22:37, Nathan Ridge:
By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website.
Nice find! I've been missing a zip_range! A few useful additions would be a corresponding adaptor
Do you mean 'r1 | zipped(r2)' in the place of 'zip(r1, r2)'?
Somehow the asymmetry of that offends me...
I agree. Especially if consider possible syntax: 1. zip(r1,r2,r3) 2. r1 | zipped(r2) | zipped(r3) Second is similar to zip(zip(r1,r2),r3) if express in terms of first. But I don't see quick and straightforward way how to express first in terms of second. Maybe something non-obvious and wild like: a) r1 | zipped(r2) | merge_zipped(r3) or b) r1 | merge_if_zipped(r2) | merge_if_zipped(r3) ? -- Evgeny Panasyuk
On 2/12/2013 1:37 PM, Nathan Ridge wrote:
By the way, is combine in boost/range/combine.hpp in public api? I don't see it on website.
Nice find! I've been missing a zip_range! A few useful additions would be a corresponding adaptor
Do you mean 'r1 | zipped(r2)' in the place of 'zip(r1, r2)'?
Somehow the asymmetry of that offends me...
Indeed, looks like I offended myself also without realizing it. :-p Jeff
Hi, 2013/2/11 Nathan Ridge <zeratul976@hotmail.com>
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range? [...]
P.S. Consider implementation of companion - transform_adjacent. Maybe even consider version which accepts "count of adjacent elements within each iteration" as template non-type parameter. Or maybe choose some another approach involving Boost.Range?
I think a more general approach would be a Boost.Range-style range adaptor [1] that presents a view of the range where elements in the view are pairs of (references to, if desired) elements in the underlying range. You can then use standard algorithms like for_each and transform on the adapted range.
I have written such an adaptor in the past and called it 'adjacent_paired'. I've also seen (can't remember where) the name 'windowed' used for the more general version which presents a view of tuples of N adjacent elements.
Regards, Nate
[1] http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/reference/ada...
Agree. I have range-adaptor implementation already. Please see: http://dl.dropbox.com/u/1682460/git/OvenToBoost/libs/range/doc/html/range_ex... https://github.com/faithandbrave/OvenToBoost/blob/master/boost/range/adaptor...
======================== Akira Takahashi mailto:faithandbrave@gmail.com site: https://sites.google.com/site/faithandbrave/about/en
on Sun Feb 10 2013, Evgeny Panasyuk <evgeny.panasyuk-AT-gmail.com> wrote:
10.02.2013 17:10, Ian Hobson:
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range? [...] Initial implementation available at http://github.com/irh/adjacent_for_each
I have implemented for_each_adjacent on project I worked on (sorry, can't share source). I had two versions: for InputIterator and ForwardIterator. Selection was implemented as tag dispatching of iterator_category.
You need special version for InputIterator which maintains temporary copy of value_type, due to 24.1.1/3:
[Note: For input iterators, a == b does not imply ++a == ++b. (Equality does not guarantee the substitution property or referential transparency.) Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms.]
In this regard your version at https://github.com/irh/adjacent_for_each/blob/master/boost/algorithm/adjacen... is broken. Because it advertises to work on InputIterator, but it dereferences iterator at same position several times. As the result current implementation is for ForwardIterator.
That's incorrect. The mental model for InputIterator is an ephemeral input stream *with a one-element backing buffer*. You are allowed to dereference the same InputIterator multiple times at the same position until that iterator or a copy of it is incremented. Table 107 spells this out: +---------------+----------------+------------+-------------------------------+ |Expression |Return Type |Operational | Assertion/note | | | |Semantics |pre-/post-condition | +===============+================+============+===============================+ |*a |convertible to T| |pre: a is dereferenceable. | | | | |**The expression (void)*a, *a | | | | |is equivalent to *a.** | | | | |(emphasis mine). | +---------------+----------------+------------+-------------------------------+ -- Dave Abrahams
11.02.2013 3:09, Dave Abrahams:
In this regard your version at https://github.com/irh/adjacent_for_each/blob/master/boost/algorithm/adjacen... is broken. Because it advertises to work on InputIterator, but it dereferences iterator at same position several times. As the result current implementation is for ForwardIterator.
That's incorrect. The mental model for InputIterator is an ephemeral input stream *with a one-element backing buffer*. You are allowed to dereference the same InputIterator multiple times at the same position until that iterator or a copy of it is incremented.
Thanks for correction, I should re-phrase my sentence as: "but it dereferences iterator at same position several times *after passing to next and/or dereferencing it*" ( https://github.com/irh/adjacent_for_each/blob/382070171df195afb945f86db442a8... ) -- Evgeny Panasyuk
on Mon Feb 11 2013, Evgeny Panasyuk <evgeny.panasyuk-AT-gmail.com> wrote:
11.02.2013 3:09, Dave Abrahams:
In this regard your version at https://github.com/irh/adjacent_for_each/blob/master/boost/algorithm/adjacen... is broken. Because it advertises to work on InputIterator, but it dereferences iterator at same position several times. As the result current implementation is for ForwardIterator.
That's incorrect. The mental model for InputIterator is an ephemeral input stream *with a one-element backing buffer*. You are allowed to dereference the same InputIterator multiple times at the same position until that iterator or a copy of it is incremented.
Thanks for correction, I should re-phrase my sentence as: "but it dereferences iterator at same position several times *after passing to next and/or dereferencing it*" ( https://github.com/irh/adjacent_for_each/blob/382070171df195afb945f86db442a8... )
OK, but the last part of that sentence remains irrelevant. It should end with the word "next." -- Dave Abrahams
10.02.2013 17:10, Ian Hobson:
Initial implementation available at http://github.com/irh/adjacent_for_each
I have just noticed that you use: for (InputIterator next = first + 1; next != last; first++, next++) "first + 1" is legal only for RandomAccessIterator. You should test your algorithm on real InputIterator. P.S. Also consider http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/index.html#new-style-... and http://www.boost.org/doc/libs/1_53_0/libs/concept_check/concept_check.htm -- Evgeny Panasyuk
On 10 Feb 2013, at 16:29, Evgeny Panasyuk <evgeny.panasyuk@gmail.com> wrote:
10.02.2013 17:10, Ian Hobson:
Initial implementation available at http://github.com/irh/adjacent_for_each
I have just noticed that you use:
for (InputIterator next = first + 1; next != last; first++, next++)
"first + 1" is legal only for RandomAccessIterator. You should test your algorithm on real InputIterator.
Thanks. I've updated the implementation to correct this, and to document that it's suitable for ForwardIterators. I'll look in to adding support for InputIterators.
on Sun Feb 10 2013, Ian Hobson <ian.r.hobson-AT-gmail.com> wrote:
On 10 Feb 2013, at 16:29, Evgeny Panasyuk <evgeny.panasyuk@gmail.com> wrote:
10.02.2013 17:10, Ian Hobson:
Initial implementation available at http://github.com/irh/adjacent_for_each
I have just noticed that you use:
for (InputIterator next = first + 1; next != last; first++, next++)
"first + 1" is legal only for RandomAccessIterator. You should test your algorithm on real InputIterator.
Thanks. I've updated the implementation to correct this, and to document that it's suitable for ForwardIterators. I'll look in to adding support for InputIterators.
FYI: this is why boost::next(first) was created. -- Dave Abrahams
On 10-02-2013 14:10, Ian Hobson wrote:
Hi,
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range?
#include <iostream> #include <boost/algorithm/adjacent_for_each.hpp>
void PrintInts(int a, int b) { std::cout << '(' << a << ", " << b << ")\n"; }
int main() { const int ints[] = {0, 1, 2, 3, 4}; boost::algorithm::adjacent_for_each(ints, ints + 5, PrintInts); }
Yes, I think would be a good utillity. But consider generalizing: for_each_slice<N>( ..., PrintInts() ) so we can decide how big the sliding window is. Perhaps it's better with a run-time argument: for_each_slice( 3, // size of slize iterator begin, iterator end, Functor fun ) and provide range overload in terms of the iterator version. -Thorsten
I've updated the implementation with support for input iterators. I think it makes a nice companion to adjacent_find so I'll leave it operating on element pairs for now. I like the idea of also adding adjacent_transform. I would be very interested in an adaptor for boost.range for general windowing tasks, with parameters for window size and hop size. Best, Ian On 12 Feb 2013, at 14:24, Thorsten Ottosen <thorsten.ottosen@dezide.com> wrote:
On 10-02-2013 14:10, Ian Hobson wrote:
Hi,
Is there any interest in a version of for_each that operates on each adjacent pair of elements in a range?
#include <iostream> #include <boost/algorithm/adjacent_for_each.hpp>
void PrintInts(int a, int b) { std::cout << '(' << a << ", " << b << ")\n"; }
int main() { const int ints[] = {0, 1, 2, 3, 4}; boost::algorithm::adjacent_for_each(ints, ints + 5, PrintInts); }
Yes, I think would be a good utillity. But consider generalizing:
for_each_slice<N>( ..., PrintInts() )
so we can decide how big the sliding window is. Perhaps it's better with a run-time argument:
for_each_slice( 3, // size of slize iterator begin, iterator end, Functor fun )
and provide range overload in terms of the iterator version.
-Thorsten
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 17-02-2013 15:57, Ian Hobson wrote:
I've updated the implementation with support for input iterators.
I think it makes a nice companion to adjacent_find so I'll leave it operating on element pairs for now. I like the idea of also adding adjacent_transform.
Well, if this goes to review, consider my vote to be -1. -Thorsten
participants (7)
-
Akira Takahashi -
Dave Abrahams -
Evgeny Panasyuk -
Ian Hobson -
Jeff Flinn -
Nathan Ridge -
Thorsten Ottosen