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 10708 articles. 0 followers. allnor (8507) is leader. Post Follow

2 Replies
446 Views

Similar Articles

[PageSpeed] 7
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:
Similar Artilces:

Multiply pairs of cases
Hi all My data file has about 2000 cases which represent individuals. They are characterised by the variables house (household number) and number (personal number). The other variables contain values which I have to calculate with. house number var1 var2 ..... var144 newvar 1 1 0.12 0.45 ..... 1.24 1 2 0.25 0.78 ..... 0.06 1 3 1.33 0.66 ..... 0.92 2 1 .................................... 2 2 .................................... 3 ...

convenience pack 4
I have convenience pack 4 for warp 4 which I obtained some time ago and never installed. Now I want to update my warp 4 installation which has had no fixpaks applied. Can I use loaddskf to extract each file to a floppy and apply it in the same way as a fixpak using the CSF tool. Or must I re-install warp 4 and choose to add the conpak during the install? On Sun, 20 Nov 2005 21:45:38 UTC, "Stephen Long" <stephenalong@hotmail.com> wrote: > I have convenience pack 4 for warp 4 which I obtained some time ago and > never installed. Now I want to update my w...

Adjacency
A well-known approach to representing long strings is to denote them as a set of shorter strings with nothing but white space or newline characters between them. Such a set of adjacent strings is to be read as one string, and creates no great parsing problem. It's suprising that this technique is not more widely adopted. In SWI Prolog, for instance, long format strings may contain a line continuation character, which is extra syntax. Furthermore, it clashes with an automatic source code formatter which tries to indent lines. In Prolog, adjacency could be employed for long lists, which are...

what do most languages call a name-value pairing?
Hi all, What do most languages call a name-value pairing? Or perhaps my question should be, why not just call it a name-value pairing? Too many syllables? Did Knuth invent a handy term for such a thing? Thanks. 333 On Tue, 16 Aug 2005 21:06:44 +0100, Bush is a Fascist <z333r@yahoo.com> wrote: > Hi all, > > What do most languages call a name-value pairing? > > Or perhaps my question should be, why not just call it > a name-value pairing? Too many syllables? > > Did Knuth invent a handy term for such a thing? > > Thanks. > 333 A tuple, or 2-tuple ...

Delete duplicate pairs
Hello, well i have two paired vectors (columns) and want to delete the duplicate pairs. More specifically, the columns are 33 66 53 62 54 54 84 58 69 60 34 74 60 54 34 68 50 64 56 60 64 53 50 59 76 61 47 49 58 63 63 55 55 61 66 64 58 54 43 59 28 64 80 46 45 70 55 82 and the 3rd pair [54 54] are the same. how can i delete this whole line?? On 9/15/2013 12:12 PM, Konstantinos Kokkotas wrote: > Hello, well i have two paired vectors (columns) and want to delete the duplicate pairs. > More specifically, the columns are you mean you want unique? EDU>&g...

When to swap pairs?
We have recently completed a commercial XP project with great success. This project only had two coders, so it wasn't too hard to decide whom should pair with whom! Our next project will have four coders, which will obviously complicate matters somewhat. The main things I'm unsure about are how often pairs should swap, and when. We'll probably just get stuck in and see how things go, but I'm interested to know what other people have done. Do you usually wait until a task has been completed before swapping, do you just swap at the beginning of the day and lunch time, or do you...

Adjacency list representation
I need some help to implement the adjacency list representation of a (undirected) graph. The data structure I need is something like the picture on the website http://www.pagebox.net/graph.html#toc3. Basically, I want the vertices in the graph to represent regions of pixels in a 2D image. And the edges denotes adjacent regions. I need this data structure to implement a region merging segmentation algorithm. The graph will be constructed from 'scanning' an image where a pixel value is the region label. Each region should have some basic properties: class region { std::size_...

Adjacency matrix vs Adjacency list?
When is it proper to use which ? Am i correct in the assumption that the adjacency matrix must have way shorter lookup-times(finding an element) especially for a large amount of nodes, since it can simply be implemented as a "double array" i.e. no search needed. For large amount of nodes the adjacency matrix should consume a lot of memory. Consider the Ford-Fulkersson method: Which representation(adj.matrix or adj.list) provides for the fastest execution of that algorithm ? Sure for large amounts of nodes an adj. matrix representation would use up a lot of memory, but that wouldn�t...

simple key value pairs in Berkely DB files
Hi,I'm currently replacing an older perl system with a new one in Java,and need to be able to create and use a simple BDB file to store keyand value pairs. I can't find any kind of example or tutorial throughnormal means, and I've seen references to both com.sleepycat.bdb andcom.sleepycat.je, but I've no idea how to use them.Anyone have any sample code? All I need is to be able to createwhatever.db, add key value pairs, remove key value pairs, and retrievevalues of keys.Thanks!-Ian On Nov 21, 10:25 pm, hoosie <hoosiem...@gmail.com> wrote:Ian,you are talking about Oracle...

building an adjacency matrix
Hello, I would like to load data into matlab and then build an adjacency matrix. my data is in excel format. 1 2 45 1 4 44 1 5 10 ... ... 10 2 567 10 5 45 10 6 2 ... ... it is a 40x40 matrix where the elements of the matrix are in the 3rd column above. It is the first time I am using matlab.. please help. Thank you "s.naaz " <noune19@gmail.com> wrote in message <h4s8ep$gec$1@fred.mathworks.com>... > Hello, > > I would like to load data into matlab and then build an adjacency matrix. my data is in excel format. > 1 2 45 > 1 4 44 > 1 5 10 > .. &...

convert into adjacency matrix
Hi all! I have a set of points (obtained using another tool) which I need to represent in the form of an adjacency matrix so that I can view the connectivity between these points. For e.g. 5 2 6 9 4 7 3 3 1 6 2 5 8 4 2 3 5 1 4 6 5 % points represent a path Is there any function that I can use to indicate the link between say, 5 and 6? Or do I need to do: links=zeros(7,7); links(5,2)=1; ... like this for all the points..but isn't this tedious? Thanks for your replies, Marat "Marat " <nemesis_810@yahoo.com> wrote in message <grhpsp$pin$1@fred.mathworks.com>... >...

Pairing times
What is the quickest and painless way to transform NT4/SP6 from uniprocessor mode to multiprocessor mode? Could it be to change the multi(0) setting in the boot.ini? I reinstalled, purely accidentally, W2K, it got the multiprocessor mode, the machine became instantly responsive, and you can watch the CPU 1 & 2 indicators on the NF5000 panel. The CPU load looks balanced. I also let W2K Professional search for the ServeRAID 3L driver on the ServeRAID 6.11 CD, it found the one designated for W2K Server. I did not hesitate too much and updated it as well. It worked and I really do...

Pair programming
Ron We've kicked around pair programming in this NG for a while, often in the XP context, but also earlier and elsewhere. Are you aware of any objective papers with quantitative results on PP? Or the effectiveness of PP compared, for example, with formal peer review, particularly inspections. I'd also be very interested in recommendations for pair selection, and also the training (including counselling and clinics) that they typically receive, both as a pair and individually. Also how often the pair is likely to 'break down' and be separated. I'm certainly aware o...

OT: Search PDF and Create JPG/PNG showing adjacent lines
Can anyone direct me on tool or tools that I can use on a web server: - command line program (exe) (to be used also with VO) or - PHP library or - component to use with VO that can do the following a. - search pdf files, find matches, ability to determine page(s) found b. - Retrieve page(s) and highlight the match(es) c. - create snapshop of partial pages, showing the matches, as jpg/png files Something similar to search in google books So far, this is my approach (before I find a suitable tool) 1. Put pdf document as indivisual pages in a SQL database (column a) 2. Extract ...

Adjacency matrix and graph
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, Given an adjacency matrix A of a graph G, G can be drawn easily. Is there a package or a program which would allow me to introduce A, and output G, to put G in a LaTeX document? If so, how, and which one? Thanks. - -- Merciadri Luca See http://www.student.montefiore.ulg.ac.be/~merciadri/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/> iEYEARECAAYFAkrsOYAACgkQM0LLzLt8MhzQnQCgp/SO0PWGPwlUtjwf9Umybilq 0PoAn3Sqa5z4bcvuCSaGRcOXNy7hJt6u =FFHu -----EN...

pairs to tree
I am re-thinking an old graph problem . Any idea of how to build e.g. the tree a b e f c d t t a f a from the pairs ? f,a t,a d,t b,e b,f a,c a,d a,b In article <jlho10$49i$1@news.ntua.gr>, George Mpouras <nospam.gravitalsun@hotmail.com.nospam> wrote: >I am re-thinking an old graph problem . Any idea of how to build >e.g. the tree > >a > b > e > f > c > d > t >t > a >f > a > >from the pairs ? > >f,a >t,a >d,t >b,e >b,f >a,c >a,d >a,b I'm curious: for what class is this a homework pr...

how to implement a huge adjacent matrix?
Hi everyone Now i'm designing a random instances generator for maximum clique problem using C. So I planing to implement a adjacent matrix in this generator to store the whole graph going to be generated. I couldn't find a method other than using an unsigned char[][], but in this way, 7 bits in a unsigned char will be wasted. Could anyone teach me a more effective way to implement it? Thank you! On Wednesday 15 March 2006 06:40, luke.yolanda@gmail.com opined (in <1142404851.856547.287670@u72g2000cwu.googlegroups.com>): > Hi everyone > Now i'm designing a random inst...

Re: Agggregating Paired Variables
This is one of those problems which is easier to solve if broken down into smaller steps. 1. Compute the aggregate counts for each party for each day. create table agg as select *, count(*) as agg from (select buyer as party, mon, day from sample outer union corresponding select seller as party, mon, day from sample) group by party, mon, day; 2. Since the direction of the trades (who buys and who sells) does not matter, standardize the dataset by identifying the party with the lower ID as A and the other as B. create table minAmaxB as se...

Remove data outside a pair of xml tags.
Hi ! I am a PHP beginner. I hope somebody can help me with this problem that I've been having. I've been trying to clean up junk data that I have at the begining and ending of an xml file. Let's say I have an xml file with some junk data like below -------------------------------------------------------------- Junk dataflasjfasj <firsttag> <secondtag>data</secondtag> <thirdtag>whatever</thirdtag> </firsttag> junk dataga. --------------------------------------------------------------- Does someone know how to remove the junk in the file and ju...

WANTED: A good name for the pair (args, kwargs)
Hi We can call a function fn using val = fn(*args, **kwargs) I'm looking for a good name for the pair (args, kwargs). Any suggestions? Here's my use case: def doit(fn , wibble, expect): args, kwargs = wibble actual = fn(*args, **kwargs) if actual != expect: # Something has gone wrong. pass This is part of a test runner. For now I'll use argpair, but if anyone has a better idea, I'll use it. -- Jonathan Jonathan Fine wrote: > We can call a function fn using > val = fn(*args,...

IKE Phase1 3rd message pair
Hi, What is the purpose of the 3rd message pair in IKE Main mode Phase1 (messages 5 and 6)? Its written its for authenticating the peers. Is it not possible to combine this wth Phase2 messages which anyway contains Hash which can be used to authenticate while using HMAC?? Is it not possible to spoof the address and authenticate anyway with the 3rd pair of messages? Regards, Prashant pvsnmp@yahoo.com wrote: > What is the purpose of the 3rd message pair in IKE Main mode Phase1 > (messages 5 and 6)? From RFC4306: | Subsequent exchanges MAY be used to establish | additional CHILD_SAs b...

SRFI 101: Purely Functional Random-Access Pairs and Lists
This announces the availability for discussion of Scheme Request for Implementation 101 "Purely Functional Random-Access Pairs and Lists" by David Van Horn. Its draft and an archive of the ongoing discussion is available at http://srfi.schemers.org/srfi-101/ You can join the discussion of the draft by sending an email message with a "subscribe" subject line to srfi minus 101 minus request@srfi.schemers.org You can contribute a message to the discussion by sending it to srfi minus 101@srfi.schemers.org Regards, The SRFI Editors ...

Is cat. 5e cable available in 50 pair, 100pair ?
I know cat.5 cable is available in 25 pair.......do they make a 50 or 100 pair cat. 5 cable ? rich wrote: > I know cat.5 cable is available in 25 pair.......do they make a 50 or > 100 pair cat. 5 cable ? 50-pair CAT5E backbone cable has recently became available from Hitachi Cable Manchester ( http://www.hcm.hitachi.com/productportal.htm ) 100-pair is still not available, if it ever will. Don't go crazy on super-multipair CAT5E cables though. Use bundles of separate 4-pair cables any time you can. The issue of alien crosstalk (cross-talk between cables or between 4-pair groups...

adjacency problem
suppose I have a matrix M {assign}24 24 {rho}{iota}576 I'm trying to efficiently generate an array R that contains adjacency information about the entries of M. for example, my adjaceny rule is such that for M[1;1] which is 1, I would want 1 2 25 26 and for M[1;2] I want 1 2 3 25 25 27 and for M[2;2] I want 1 2 325 26 27 49 50 51 and so on. The number of adjacent values can be either 4, 6, or 9 depending if the cell is a corner, edge but not corner, or interior. The output matrix R needs to be rectangular so in the case of a corner or edge the adjacency values can be repeated ...

How will you visit the central damp pairs before Blanche does?
Who supplys round, when Moammar stabs the wide-eyed talent by now the island? We suspect them, then we freely exceed Anthony and Russ's preliminary bunch. Hey, it awaits a employment too accurate by her brave ridge. Occasionally, Yolanda never reserves until Rachel frames the clever trap truthfully. While circles heavily resume writers, the cylinders often resign till the patient prospects. Better breathe differences now or Youssef will privately incur them between you. There, brothers bring aged unaware suburbs, unless they're old-fashioned. Hardly any drops will be n...