Hello Vidar! Vidar Hasfjord wrote: > The Standard C++ Library currently includes a couple of algorithms that > operates on adjacent pairs in a sequence --- adjacent_find and > adjacent_difference. Unfortunately, in my experience, these are not > sufficient to cover some seemingly common needs, such as invoking a > function over all adjacent pairs, as well as transforms and > accumulation. I would think standard algorithms for these operations > would have been convenient in many areas such as geometry/graphics, > statistics, signal processing, compression, etc. > > Searches on the net do not turn up very many hits for such extensions. > Is everyone writing manual loops in these cases? Maybe but there is no need for doing so: the standard library already includes appropriate algorithms for these! > In particular, I see the need for the following algorithms: > > template <class II, class Proc> > inline Fun for_each_adjacent (II first, II last, Proc); You can use std::mismatch() for this: use a predicate always returning true after applying you procedure and increment the first iterator before passing it to the algorithm. In summary, your for_each_adjacent() would looks something like this: template <typename ForwardIterator, typename Proc> Fun for_each_adjacent(ForwardIterator beg, ForwardIterator end, Proc proc) { ForwardIterator tmp(beg); std::mismatch(++tmp, end, beg, true_predicate(proc)); return proc; } > template <class II, class OI, class BinOp> > inline OI transform_adjacent (II first, II last, OI dest, BinOp); This one is an obvious application of std::transform() taking two sequences. > template <class II, class T, class BinOp> > inline T accumulate_adjacent (II first, II last, T val, BinOp); .... and this one is std::mismatch() again. > Any comments about these algorithms, alternatives or their suitability > for inclusion in the standard library, are welcomed. I wouldn't include algorithms like this into the standard library: there seem to be rather special cases. Possibly, something like a "zip()" algorithm which takes two input sequences and an operation could be a reasonable thing, however: this would avoid the somewhat ugly reversal of arguments passed to the predicate (although this can be easily handled by the functor, too). What is missing are versions of the algorithms taking two sequences (e.g. std::mismatch() and std::transform()) which check both the first and the second sequence for having terminated. Good luck, Denise. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

10/22/2006 5:07:13 PM

Thanks for your reply, Denise! > > Is everyone writing manual loops in these cases? > > Maybe but there is no need for doing so: the standard library already > includes appropriate algorithms for these! I was aware of some algorithms that could be utilised (e.g. adjacent_find with a dummy predicate via an adapter). You have made me aware of a few more. That said, I am not sure I agree that these algorithms are "appropriate" in this context. These adaptations may solve the problem (I'll outline a few problems below), but the solution is not straight-forward nor intuitive. > > inline Fun for_each_adjacent (II first, II last, Proc); > You can use std::mismatch() for this: use a predicate always returning true Yes, this is similar to using adjacent_find in a similar manner. I find adjacent_find semantically closer to the intention. Unfortunately, both solutions require ForwardIterator. While the standard algorithms you use may require only InputIterators, providing the same InputIterator or copies for two inputs will operate outside the iterator requirements (one pass requirement). The for_each algorithm works with InputIterator, and it would be convenient if for_each_adjacent did the same. My following implementation is close: template <class II, class Fun> inline Fun for_each_adjacent (II first, II last, Fun fun) { if (first != last) for (II prev; (prev = first, ++first != last);) fun (*prev, *first); return fun; } This is a single-pass algorithm in the sense that the increment operator is applied only std::distance (first, last) times. Every item is referenced twice, although this is not against the rules. Unfortunately, "prev" is dereferenced after the increment of "first", and this is outside the InputIterator requirements: "++r --- post: any copies of the previous value of r are no longer required either to be dereferenceable or to be in the domain of ==" (Working Draft, Standard for Programming Language C++, p599). Although it isn't compliant, I have found the implementation above to work fine with stream iterators on my platform (VC++ 2005). An InputIterator compliant implementation of for_each_adjacent will have to use copying to avoid this problem: template <class II, class Fun> inline Fun for_each_adjacent (II first, II last, Fun fun) { if (first != last) for (;;) { std::iterator_traits <II>::value_type prev (*first); if (++first == last) break; fun (prev, *first); } return fun; } As far as I see this implementation should be InputIterator compliant, but if I've overlooked something, please let me know. Usage scenario: // Draw line segments from a stream of formatted points. istream_iterator <Point> begin (cin), end; for_each_adjacent (begin, end, DrawLine); > > inline OI transform_adjacent (II first, II last, OI dest, BinOp); > This one is an obvious application of std::transform() taking Again, this doesn't work with InputIterator. > > inline T accumulate_adjacent (II first, II last, T val, BinOp); > ... and this one is std::mismatch() again. Same problem. > I wouldn't include algorithms like this into the standard library: > there seem to be rather special cases. You may be right, although I find it somewhat surprising. I would think that this sort of thing was fairly common (i.e. prosessing successive pairs of elements in a sequence). But then again, the lack of hits from my net searches supports your view. Regards, Vidar -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

10/23/2006 5:01:46 AM