how to use for_each to collect some info from a vector into anothervector

[John Black]

Hi,
I am not familiar with for_each very well, suppoase I have a
vector<pair<uns igned int, unsigned int> > vec1 and the contents are

{<0x00000000, 0x000000FF>, <0x10000000, 0x2FFFFFFF>}

what I want is to create another vector, vector<int> vec2, which store
all the first 8 bit heads of the integer in vec1, for the above example,

0x00000000 & 0xFF000000 ==> 0x00000000,
0x000000FF & 0xFF000000 ==> 0x00000000,
0x10000000 & 0xFF000000 ==> 0x10000000,
0x2FFFFFFF & 0xFF000000 ==> 0x2F000000,

then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.

It's easy to specifically write a for loop, just wonder how to do it
use for_each.

Thanks.

[Victor Bazarov]

John Black wrote:

I am not familiar with for_each very well, suppoase I have a
vector<pair<uns igned int, unsigned int> > vec1 and the contents are

{<0x00000000, 0x000000FF>, <0x10000000, 0x2FFFFFFF>}

what I want is to create another vector, vector<int> vec2, which store
all the first 8 bit heads of the integer in vec1, for the above example,

0x00000000 & 0xFF000000 ==> 0x00000000,
0x000000FF & 0xFF000000 ==> 0x00000000,
0x10000000 & 0xFF000000 ==> 0x10000000,
0x2FFFFFFF & 0xFF000000 ==> 0x2F000000,

then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.

It's easy to specifically write a for loop, just wonder how to do it
use for_each.

You will have to implement a functor that will do that. Boost library
has some mechanisms that are not available in the standard library yet.
For example, there is no simple functor to extract 'first' or 'second'
from a pair.

Something like:

struct skim_pairs_to {
vector<int>& collector;
skim_pairs_to(v ector<int>& c) : collector(c) {}
void operator()(cons t std::pair<unsig ned,unsigned>& p) {
collector.push_ back(p.first & 0xff000000);
collector.push_ back(p.second & 0xff000000);
}
};

...
std::for_each(v ec1.begin(), vec1.end(), skim_pairs_to(v ec2));

should do it. I didn't test the code.

Victor

[Daniel T.]

John Black <bl***@eed.co m> wrote:

Hi,
I am not familiar with for_each very well, suppoase I have a
vector< pair< unsigned int, unsigned int > > vec1 and the contents are

{ < 0x00000000, 0x000000FF >, < 0x10000000, 0x2FFFFFFF > }

what I want is to create another vector, vector< int > vec2, which store
all the first 8 bit heads of the integer in vec1, for the above example,

0x00000000 & 0xFF000000 == > 0x00000000,
0x000000FF & 0xFF000000 == > 0x00000000,
0x10000000 & 0xFF000000 == > 0x10000000,
0x2FFFFFFF & 0xFF000000 == > 0x2F000000,

then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.
You only put 3 items in vec2, was that on purpose? IE are repeted values
not supposed to be entered?

If that's the case, I would insert into a set first, then copy from the
set to the vector (see below...)

It's easy to specifically write a for loop, just wonder how to do it
use for_each.

The same way, except the loop body would be in a functor. So you might
start with:

for ( vector< pair< unsigned, unsigned > >::iterator it = v.begin();
it != v.end(); ++it )
{
v2.push_back( it->first & 0xFF000000 );
v2.push_back( it->second & 0xFF000000 );
}

This would become:

struct filler {
vector< unsigned >& v;
filler( vector< unsigned >& v ): v( v ) { }
void operator()( const pair< unsigned, unsigned >& p ) {
v.push_back( p.first & 0xFF000000 );
v.push_back( p.second & 0xFF000000 );
}
};

and:

for_each( v.begin(), v.end(), filler( v2 ) );

Seems like a bit of a waste. We've created a new type, that can only be
used in this one place, and when someone encounters the 'for_each' he
needs to search the code to find out what this new type does.

What if we could make something more resuable, and at the same time do a
better job of expressing what is happening at the place where it is
supposed to happen?

Let's take a look at what we are doing. Basically it's a transform
except each value in the first container is being transformed twice and
placed in the second container. So we can model something off of
std::transform.

template < typename InputIter, typename OutputIter,
typename Op1, typename Op2 >
OutputIter expanding_trans form( InputIter first, InputIter last,
OutputIter result, Op1 op1, Op2 op2 )
{
while ( first != last )
{
*result++ = op1( *first );
*result++ = op2( *first );
++first;
}
return result;
}

Maybe the above isn't all that reusable, but it's certanly more resuable
than the 'filler' type above. For example, we can use this function to
output our vector< pair< unsigned, unsigned > > to cout... The fact that
we can already see two uses for this function argues well for its
reusablity.

Now, what arguments do we need to pass into this function? The first two
are easy 'v.begin()' and 'v.end()' we see this all the time in the
standard algorithms. The third is a little harder, but still often seen:
'back_inserter( v2 )'. Of course 'v' is our vector< pair< unsigned,
unsigned > > and 'v2' is our new vector< unsigned >... For the last two
parameters, we need to do some more work.

First we examine the 'functional' part of the stl. We find a
'logical_and' functor, but no 'bit_and'. Oh well, that's easy to fix:

template < typename T >
struct bit_and : public std::binary_fun ction< T, T, T >
{
T operator()( const T& x, const T& y ) const { return x & y; }
};

So, for each of the Ops in our expanding_trans form, we need to call
'bit_and' were the first argument is the first and second item in the
pair, and the second argument is 0xFF000000. Let's make a functor that
does that:

binder2nd< bit_and< unsigned > > high_8_mask =
bind2nd( bit_and< unsigned >(), 0xFF000000 );

Let's make sure we know what high_8_mask does:

assert( high_8_mask( 0x12345678 ) == 0x12000000 );

Unfortunatly, we can't just pass our pair< unsigned, unsigned > into the
above because it only takes one unsigned value.

Now we have to look in the past. The origional STL had several useful
functors that never made it into the standard. Two of them specifically
dealt with manipulating pair objects so that they could be used in
standard functors: select1st and select2nd. You can find them on SGI's
website and I'm sure other websites have them. They both do exactly what
you would think. You pass in a pair object, and it returns either the
first or second object of the pair.

Another useful functor is 'unary_compose' ; which takes two other
functors and combines them like this: f1( f2( x ) ). There is also a
useful function 'compose1' that helps build a unary_compose objects (
like the way 'make_pair' builds 'pair' objects. ) You can also find this
in boost where it's called 'compose_f_gx'. ..

With these three functors in our arsenal we can build the functors that
will be used by our new algorithm.

I also want to make the pair easer to work with so I'll make a typedef.

Now I'll put all of this together to show how it works:

typedef pair< unsigned, unsigned > two_flags;

binder2nd< bit_and< unsigned > > high_8_mask =
bind2nd( bit_and< unsigned >(), 0xFF000000 );

expanding_trans form( v.begin(), v.end(), back_inserter( v2 ),
compose1( high_8_mask, select1st< two_flags >() ),
compose1( high_8_mask, select2nd< two_flags >() ) );

There you go, we have written the loop using lots of small, highly
reusable components.

Now back to my question above about no repeat values. If that's the case
then insert into a set:

set< unsigned > s;
binder2nd< bit_and<unsigne d int> > high_8_mask =
bind2nd( bit_and< unsigned >(), 0xFF000000 );
expanding_trans form( v.begin(), v.end(),
inserter( s, s.begin() ),
compose1( high_8_mask, select1st< two_flags >() ),
compose1( high_8_mask, select2nd< two_flags >() ) );
copy( s.begin(), s.end(), back_inserter( v2 ) );

[Jerry Coffin]

John Black <bl***@eed.co m> wrote in message news:<40******* ********@eed.co m>...

Hi,
I am not familiar with for_each very well, suppoase I have a
vector<pair<uns igned int, unsigned int> > vec1 and the contents are

{<0x00000000, 0x000000FF>, <0x10000000, 0x2FFFFFFF>}

what I want is to create another vector, vector<int> vec2, which store
all the first 8 bit heads of the integer in vec1, for the above example,

0x00000000 & 0xFF000000 ==> 0x00000000,
0x000000FF & 0xFF000000 ==> 0x00000000,
0x10000000 & 0xFF000000 ==> 0x10000000,
0x2FFFFFFF & 0xFF000000 ==> 0x2F000000,

then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.

It's easy to specifically write a for loop, just wonder how to do it
use for_each.

IMO, you're getting the steps out of order. First you need to pick
the right algorithm, THEN you need to figure out how to use it.

In this case, std::transform is MUCH better suited to the job (at
least IMO).

// warning: this code is incomplete and therefore untested.

// save a little typing:
typedef std::pair<unsig ned int, unsigned int> dt;

// define what we're going to do to each item:
struct top8 {
unsigned int operator()(dt const &d) {
// assumes 32-bit ints.
return d.first & 0xff000000;
}
};

// define vectors for input and output:
std::vector<dt> vec1;
std::vector<uns igned int> vec2;

// code to fill vec1 goes here.

// transform the input into the output:
std::transform( vec1.begin(), vec1.end(), std::back_inser ter(vec2),
top8);

Arrogant prediction: nobody will post a better solution using
for_each. :-)

P.S. Of course, I get to define "better". <G>

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Siemel Naran]

"Jerry Coffin" <jc*****@taeus. com> wrote in message

{<0x00000000, 0x000000FF>, <0x10000000, 0x2FFFFFFF>} then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.

Maybe one element missing?

struct top8 { std::vector<dt> vec1;
std::vector<uns igned int> vec2;

// code to fill vec1 goes here.

// transform the input into the output:
std::transform( vec1.begin(), vec1.end(), std::back_inser ter(vec2),
top8);

But we want tyo iterate over vec1[0].first then vec1[0].second then
vec1[1].first then vec[1].second. For this we need to write a segmented
iterator (ie. a double iterator). Then

std::transform( OverPair(vec1.b egin()), OverPair(vec1.e nd()),
std::back_inser ter(vec2), top8);

[Daniel T.]

In article <b2************ *************@p osting.google.c om>,
jc*****@taeus.c om (Jerry Coffin) wrote:

IMO, you're getting the steps out of order. First you need to pick
the right algorithm, THEN you need to figure out how to use it.
True.

In this case, std::transform is MUCH better suited to the job (at
least IMO).

// warning: this code is incomplete and therefore untested.

// save a little typing:
typedef std::pair<unsig ned int, unsigned int> dt;

// define what we're going to do to each item:
struct top8 {
unsigned int operator()(dt const &d) {
// assumes 32-bit ints.
return d.first & 0xff000000;
}
};

// define vectors for input and output:
std::vector<dt > vec1;
std::vector<un signed int> vec2;

// code to fill vec1 goes here.

// transform the input into the output:
std::transform (vec1.begin(), vec1.end(), std::back_inser ter(vec2),
top8);

Arrogant prediction: nobody will post a better solution using
for_each. :-)

Much too arrogant. Your code fails to do what the OP wanted done. Try
again. But I mean this. Please try again because I couldn't figure out a
solution without writing a new algorithm and I'd love to see if it can
be done using transform.

[Daniel T.]

In article <WH************ *******@bgtnsc0 4-news.ops.worldn et.att.net>,
"Siemel Naran" <Si*********@RE MOVE.att.net> wrote:

std::vector<dt> vec1;
std::vector<uns igned int> vec2;

// code to fill vec1 goes here.

// transform the input into the output:
std::transform( vec1.begin(), vec1.end(), std::back_inser ter(vec2),
top8);

But we want tyo iterate over vec1[0].first then vec1[0].second then
vec1[1].first then vec[1].second. For this we need to write a segmented
iterator (ie. a double iterator). Then

std::transform (OverPair(vec1. begin()), OverPair(vec1.e nd()),
std::back_inse rter(vec2), top8);

I'd love to see what this "OverPair" iterator looks like. Care to post
it?

[Jerry Coffin]

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message news:<WH******* ************@bg tnsc04-news.ops.worldn et.att.net>...

"Jerry Coffin" <jc*****@taeus. com> wrote in message

{<0x00000000, 0x000000FF>, <0x10000000, 0x2FFFFFFF>} then vec2 should be {0x00000000, 0x10000000, 0x2F000000}.

Maybe one element missing?

Probably -- I didn't read it carefully enough, and got confused by the
inconsistency.

[ my incorrect code elided ... ]
But we want tyo iterate over vec1[0].first then vec1[0].second then
vec1[1].first then vec[1].second. For this we need to write a segmented
iterator (ie. a double iterator). Then

std::transform( OverPair(vec1.b egin()), OverPair(vec1.e nd()),
std::back_inser ter(vec2), top8);

That certainly looks a lot better, provided that my reread of the
requirements isn't wrong (again).

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Daniel T.]

jc*****@taeus.c om (Jerry Coffin) wrote:

But we want tyo iterate over vec1[0].first then vec1[0].second then
vec1[1].first then vec[1].second. For this we need to write a segmented
iterator (ie. a double iterator). Then

std::transform( OverPair(vec1.b egin()), OverPair(vec1.e nd()),
std::back_inser ter(vec2), top8);

That certainly looks a lot better, provided that my reread of the
requirements isn't wrong (again).

I've been playing around this this for a bit. At this point, I don't
think the requirements can be met using std::transform. There is simply
no way to write "OverPair" to make this work. I'd love to be proven
wrong though...

[Siemel Naran]

"Daniel T." <po********@eat hlink.net> wrote in message
news:po******** *************** *******@news6.w est.earthlink.n et...

jc*****@taeus.c om (Jerry Coffin) wrote:

But we want tyo iterate over vec1[0].first then vec1[0].second then
vec1[1].first then vec[1].second. For this we need to write a segmented iterator (ie. a double iterator). Then

std::transform( OverPair(vec1.b egin()), OverPair(vec1.e nd()),
std::back_inser ter(vec2), top8);

That certainly looks a lot better, provided that my reread of the
requirements isn't wrong (again).

I've been playing around this this for a bit. At this point, I don't
think the requirements can be met using std::transform. There is simply
no way to write "OverPair" to make this work. I'd love to be proven
wrong though...

Like a std::deque::ite rator, the outer loop loops over the list nodes, and
the inner loops over the the elements of a vector. We want the outer loop
to loop over the elements of a vector, and the inner to loop over the first
and second. Something like:

class OverPair {
public:
/* the usual 5 typedefs: iterator_catego ry, reference, etc */
OverPair(std::v ector<unsigned> ::iterator outer) : d_outer(outer),
d_inner(FIRST) { }
friend bool operator==(cons t OverPair&, const OverPair&) const {
return lhs.d_outer == rhs.d_outer && lhs.d_inner == rhs.d_inner;
}
reference operator*() {
Pair& pair = *d_outer;
switch (d_inner) {
case FIRST: return pair.first;
case SECOND: return pair.second;
}
return Pair();
}
OverPair operator++() {
++d_inner;
if (d_inner > SECOND) {
d_inner = FIRST;
++d_outer;
}
return *this;
}
private:
typedef std::pair<unsig ned, unsigned> Pair;
enum Element { FIRST, SECOND };
std::vector<Pai r>::iterator d_outer;
Element d_inner;
};

Of course, one has to wonder whether the STL functional approach is worth
the trouble as opposed to write an explicit for loop. Sometimes it might
be, as when we want to free ourselves from the logic of segemented
iterators, and use many different algorithms.