Replace raw loop with std::algorithm

[Richard]

[Please do not mail me a copy of your followup]

Suppose I have a vector of pairs of integers, e.g.

using pair_vec = std::vector<std::pair<int, int>>;

Where the elements of v are sorted by the first int in the pair:

{ {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }

I need to do a certain amount of work once for each of the first
integers in the pair and a certain amount of work for each of the 2nd
integers in the pair, using some of the data computed for each of the
first integers.

Graphically, the outer loop is once for each of these chunks of the
sequence:

{ {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
+------------------+ +------------------+ +----------+ +---+

The inner loop is over each of the elements in the subsequence.

So I end up with a raw loop like this (not tested on a compiler):

void f(const pair_vec &v)
{
auto it = v.begin();
while (it != v.end())
{
auto state1 = do_work(it->first);
int sentinel = it->second;
for(; it != v.end() && it->second == sentinel; ++it)
{
more_work(state1, it);
}
}
}

What's an alternative for this raw loop using C++11 standard
algorithms that doesn't involve traversing the pair_vec elements more
than once?

(I think ranges would make it fairly easy, but I'm constrained to
using C++11 algorithms in this scenario.)
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Sam]

Richard writes:

> Where the elements of v are sorted by the first int in the pair:
>
> { {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
>
> I need to do a certain amount of work once for each of the first
> integers in the pair and a certain amount of work for each of the 2nd
> integers in the pair, using some of the data computed for each of the
> first integers.

> What's an alternative for this raw loop using C++11 standard
> algorithms that doesn't involve traversing the pair_vec elements more
> than once?

There does not seem to be any algorithm in the stnadard C++ library that
implements this.

This seems like the wrong container to pick for this kind of data. A more
appropriate container that represents this data would be std::map<int,
std::vector<int>>; with that, I could see, perhaps, implementing something
with std::for_each and std::accumulate.

I suppose you could use std::for_each to convert this vector into a map of
vector, then use std::for_each with std::accumulate. But that's a lot of bit
shuffling.

[Ralf Goertz]

Am Fri, 10 May 2019 00:04:17 -0000 (UTC)
schrieb legaliz...@mail.xmission.com (Richard):

You could use another container type:

using pair_vec = std::map<int,std::vector<int>>;

or

using pair_vec = std::multimap<int,int>;

Then use std::for_each (it is C++11, right?) with an appropriate
function or class. But I doubt that this would be even nearly as
efficient as your current approach. Anyway, here es an example:

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using pair_vec = std::map<int,std::vector<int>>;

int first;

struct work {
static void print_first_times_second( int j) { //more_work
std::cout<<" "<<first*j;
}
void operator() (pair_vec::value_type &it) {
first=it.first; //do_work
std::cout<<first<<":";
for_each (it.second.begin(),it.second.end(),print_first_times_second);
std::cout<<std::endl;
}
} worker;

int main() {
pair_vec pv;
pv.insert(std::make_pair<int,std::vector<int>>(2,{{2,17,3}}));
pv.insert(std::make_pair<int,std::vector<int>>(42,{{5,1}}));
for_each(pv.begin(),pv.end(),worker);
return 0;
}

Regrettably, I didn't get to have "first" within "work" since
print_first_times_second needs to be static.

[Ralf Goertz]

Am Fri, 10 May 2019 10:30:12 +0200
schrieb Ralf Goertz <m...@myprovider.invalid>:

> Regrettably, I didn't get to have "first" within "work" since
> print_first_times_second needs to be static.

Well, using a lambda and catching the whole first iterator solves that
problem and obliterates the necessity to use a class:

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using pair_vec = std::map<int,std::vector<int>>;

void work(pair_vec::value_type &it) {
std::cout<<it.first<<":";
for_each (it.second.begin(),it.second.end(),[&it](int i) {std::cout<<i*it.first<<" ";});
std::cout<<std::endl;

}

int main() {
pair_vec pv;
pv.insert(std::make_pair<int,std::vector<int>>(2,{{2,17,3}}));
pv.insert(std::make_pair<int,std::vector<int>>(42,{{5,1}}));

for_each(pv.begin(),pv.end(),work);
return 0;
}

[Manfred]

On 5/10/2019 2:04 AM, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> Suppose I have a vector of pairs of integers, e.g.
>
> using pair_vec = std::vector<std::pair<int, int>>;
>
> Where the elements of v are sorted by the first int in the pair:
>
> { {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
>
> I need to do a certain amount of work once for each of the first
> integers in the pair and a certain amount of work for each of the 2nd
> integers in the pair, using some of the data computed for each of the
> first integers.
>
> Graphically, the outer loop is once for each of these chunks of the
> sequence:
>
> { {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
> +------------------+ +------------------+ +----------+ +---+
>
> The inner loop is over each of the elements in the subsequence.
>
> So I end up with a raw loop like this (not tested on a compiler):
>
> void f(const pair_vec &v)
> {
> auto it = v.begin();
> while (it != v.end())
> {
> auto state1 = do_work(it->first);
> int sentinel = it->second;
> for(; it != v.end() && it->second == sentinel; ++it)
> {
> more_work(state1, it);
> }
> }
> }

Unless I am missing something, shouldn't the sentinel above be tied to
it->first ?

>
> What's an alternative for this raw loop using C++11 standard
> algorithms that doesn't involve traversing the pair_vec elements more
> than once?
>
> (I think ranges would make it fairly easy, but I'm constrained to
> using C++11 algorithms in this scenario.)
>

As other have said, probably an ordered map may be more appropriate, but
I think it depends on the requirements of the algorithm.
For example, one advantage of your raw loop is that data is laid out in
a flat array, which makes it quick to traverse.

[Tim Rentsch]

legaliz...@mail.xmission.com (Richard) writes:

> Suppose I have a vector of pairs of integers, e.g.
>
> using pair_vec = std::vector<std::pair<int, int>>;
>
> Where the elements of v are sorted by the first int in the pair:
>
> { {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
>
> I need to do a certain amount of work once for each of the first
> integers in the pair and a certain amount of work for each of the
> 2nd integers in the pair, using some of the data computed for each
> of the first integers.
>
> Graphically, the outer loop is once for each of these chunks of the
> sequence:
>
> { {0,1}, {0,2}, {0,10}, {1,10}, {1,4}, {1,6}, {2,4}, {2,6}, {3,0} }
> +------------------+ +------------------+ +----------+ +---+
>
> The inner loop is over each of the elements in the subsequence.
>
> So I end up with a raw loop like this (not tested on a compiler):
>
> void f(const pair_vec &v)
> {
> auto it = v.begin();
> while (it != v.end())
> {
> auto state1 = do_work(it->first);
> int sentinel = it->second;
> for(; it != v.end() && it->second == sentinel; ++it)
> {
> more_work(state1, it);
> }
> }
> }

I expect you meant 'it->first' rather than 'it->second' for the
initialization of sentinel and the test against sentinel.

> What's an alternative for this raw loop using C++11 standard
> algorithms that doesn't involve traversing the pair_vec elements
> more than once?
>
> (I think ranges would make it fairly easy, but I'm constrained to
> using C++11 algorithms in this scenario.)

Just use for_each and a lambda? In C++11 (disclaimer: kind of
junky code but it does compile):

using Ints = std::pair< int, int >;
using IntsVector = std::vector< Ints >;

void
loopit( IntsVector &iv ){
auto start = iv.begin();
auto end = iv.end();
if( start == end ) return;

int working_on;
State s = do_work( working_on = start->first );
std::for_each( start, end, [&]( const Ints &p ){
int a = p.first;
if( a != working_on ) s = do_work( working_on = a );
more_work( s, p );
} );
}

If the construction/destruction of the State 's' is important,
the code may need to be modified to accommodate that. However
I think it's fairly easy to arrange for that to happen in the
same way as is implied by the explicit loops (if it is needed).

[Richard]

[Please do not mail me a copy of your followup]

Manfred <non...@add.invalid> spake the secret code
<qb3hf0$rb9$1...@gioia.aioe.org> thusly:

>Unless I am missing something, shouldn't the sentinel above be tied to
>it->first ?

Correct; I noticed that myself when reading the responses.

[Juha Nieminen]

Richard <legaliz...@mail.xmission.com> wrote:
> [Please do not mail me a copy of your followup]

Are we living in 1995?