f



Adjacent convenience - algorithms on adjacent pairs

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?

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);

   template <class II, class OI, class BinOp>
   inline OI transform_adjacent (II first, II last, OI dest, BinOp);

   template <class II, class T, class BinOp>
   inline T accumulate_adjacent (II first, II last, T val, BinOp);

Code examples/rationale:

   typedef vector <Point> Points;
   typedef vector <Line> Lines;
   Points p = GetPoints ();

   // Perform op on all adjacent pairs.

   void DrawLine (Point a, Point b);
   for_each_adjacent (p.begin (), p.end (), &DrawLine);

   // Transform all adjacent pairs (create line segments).

   Line CreateLine (Point a, Point b);
   Lines s; s.reserve (p.size () - 1);
   transform_adjacent (p.begin (), p.end (), back_inserter (s),
     &CreateLine);

   // Accumulate op on adjacent pairs (calculate distance).

   float Distance (Point a, Point b);
   float d1 = accumulate_adjacent (p.begin (), p.end (), float (0),
     &Distance);

Any comments about these algorithms, alternatives or their suitability
for inclusion in the standard library, are welcomed.

Regards,
Vidar


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

0
10/22/2006 2:23:53 PM
comp.lang.c++.moderated 10738 articles. 1 followers. allnor (8506) is leader. Post Follow

2 Replies
620 Views

Similar Articles

[PageSpeed] 26

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
Denise
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
Vidar
10/23/2006 5:01:46 AM
Reply: