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.

[Daniel T.]

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

"Daniel T." <po********@eat hlink.net> wrote in message
news:po******* *************** ********@news6. west.earthlink. net...

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 asegmented >> 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...

class OverPair {

[snip]

I almost ignored what you wrote because it didn't compile, but then the
light came on. Thank you... I went ahead and wrote it up as a template
and cleaned it up a bit:

template < typename Iter >
class OverPair:
public iterator<forwar d_iterator_tag,
typename Iter::value_typ e::first_type >
{
bool onFirst;
Iter it;
public:
OverPair( Iter i ): onFirst( true ), it( i ) { }

typename Iter::value_typ e::first_type& operator*() {
if ( onFirst )
return it->first;
return it->second;
}

bool onFirstElem() const { return onFirst; }
const Iter& iter() const { return it; }

OverPair& operator++() {
if ( !onFirst ) {
++it;
}
onFirst = !onFirst;
return *this;
}

OverPair operator++(int) {
OverPair temp( *this );
++*this;
return temp;
}
};

template < typename Iter >
bool operator==( const OverPair<Iter>& lhs, const OverPair<Iter>& rhs ) {
return lhs.onFirstElem () == rhs.onFirstElem () &&
lhs.iter() == rhs.iter();
}

template < typename Iter >
bool operator!=( const OverPair<Iter>& lhs, const OverPair<Iter>& rhs )
{ return !( lhs == rhs ); }

template < typename Iter >
OverPair<Iter> over_pair( Iter it ) {
return OverPair<Iter>( it);
}

Then it would be used like this:

binder2nd< bit_and<unsigne d int> > high_8_mask =
bind2nd( bit_and< unsigned >(), 0xFF000000 );
transform( over_pair(v.beg in()), over_pair(v.end ()),
back_inserter(v 2), high_8_mask );

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.

Well there is also the fact that the origional loop wasn't even remotly
reusable. The above code, on the other hand, can be used to load our
vector<pair<uns igned, unsigned> > from a stream, or write it to a stream
(making testing the values within it much easer.) That's three uses
already and I'm not even trying...

[Daniel T.]

In article <po************ *************** ***@news1.west. earthlink.net>,
"Daniel T." <po********@eat hlink.net> wrote:

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

"Daniel T." <po********@eat hlink.net> wrote in message
news:po****** *************** *********@news6 .west.earthlink .net...

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...

class OverPair {

[snip]

I almost ignored what you wrote because it didn't compile, but then the
light came on. Thank you... I went ahead and wrote it up as a template
and cleaned it up a bit

[snipped code]

I'm normally not one to reply to my own posts, but I've been thinking
about the solutions presented so far:

The basic loop, has absolutly no reuse value but expresses itself
clearly to even the most raw beginner.

for_each and a custom functor, also has little to no reuse value and
removes to locality of reference that the loop has, which makes it
harder to understand.

Segmented iterator, has a slightly higher reuse potential and once you
know how the OverPair iterator works, is easy to understand (although
comming up with it wasn't very intuitave for me.)

expanding_trans form algorithm, has the greatest reuse potential while
requiring a better undersanding of how to compose functors.

I think the basic loop is only easer to understand for beginners because
of the way most books teach C++, starting out as a "better C" and going
up from there. I expect that someone who learned C++ from the library
down rather than from pointers up, would find one of the other solutions
more natural.

[Siemel Naran]

"Daniel T." <po********@eat hlink.net> wrote in message news:postmaster-

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote: I almost ignored what you wrote because it didn't compile, but then the
light came on. Thank you... I went ahead and wrote it up as a template
and cleaned it up a bit:
What you have is good, but there were just some minor errors.

class OverPair {
public:
/* the usual 5 typedefs: iterator_catego ry, reference, etc */
The above includes

typedef unsigned& reference;
OverPair(std::v ector<unsigned> ::iterator outer) : d_outer(outer),
d_inner(FIRST) { }
Above line is bullshit. We have a vector of pair<unsigned,u nsigned>. So
change that to

typedef std::pair<unsig ned, unsigned> Pair;
OverPair(std::v ector<Pair>::it erator 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;
}
Mistake above is to make member function const. Remove the const. Also
name the variables lhs and rhs.

friend bool operator==(cons t OverPair& lhs, const OverPair& rhs) {
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();
}
Compiler gives me error that last line should return a lvalue. Of course,
this line is never reached. So change to

reference operator*() {
Pair& pair = *d_outer;
if (d_inner == FIRST) return pair.first;
return pair.second;
}

OverPair operator++() {
++d_inner;
Compiler complains for the above line. Either overload operator++ for the
enum or use

d_inner = Element(d_inner +1);

if (d_inner > SECOND) {
d_inner = FIRST;
++d_outer;
}
return *this;
} private:
typedef std::pair<unsig ned, unsigned> Pair;
Remove the above line as we added it earlier.
enum Element { FIRST, SECOND };
std::vector<Pai r>::iterator d_outer;
Element d_inner;
}; template < typename Iter >
class OverPair:
public iterator<forwar d_iterator_tag,
typename Iter::value_typ e::first_type >
{
bool onFirst;
Iter it;
public:
OverPair( Iter i ): onFirst( true ), it( i ) { }

typename Iter::value_typ e::first_type& operator*() {
if ( onFirst )
return it->first;
return it->second;
}

bool onFirstElem() const { return onFirst; }
const Iter& iter() const { return it; }

OverPair& operator++() {
if ( !onFirst ) {
++it;
}
onFirst = !onFirst;
return *this;
}

OverPair operator++(int) {
OverPair temp( *this );
++*this;
return temp;
}
};

template < typename Iter >
bool operator==( const OverPair<Iter>& lhs, const OverPair<Iter>& rhs ) {
return lhs.onFirstElem () == rhs.onFirstElem () &&
lhs.iter() == rhs.iter();
}

template < typename Iter >
bool operator!=( const OverPair<Iter>& lhs, const OverPair<Iter>& rhs )
{ return !( lhs == rhs ); }

template < typename Iter >
OverPair<Iter> over_pair( Iter it ) {
return OverPair<Iter>( it);
}

Then it would be used like this:

binder2nd< bit_and<unsigne d int> > high_8_mask =
bind2nd( bit_and< unsigned >(), 0xFF000000 );
transform( over_pair(v.beg in()), over_pair(v.end ()),
back_inserter(v 2), high_8_mask );

Yes, it's essentially the same concept.

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.

Well there is also the fact that the origional loop wasn't even remotly
reusable. The above code, on the other hand, can be used to load our
vector<pair<uns igned, unsigned> > from a stream, or write it to a stream
(making testing the values within it much easer.) That's three uses
already and I'm not even trying...

But is it worth the trouble to write such a complex iterator class? It
certainly could be, but I'm not totally convinced as yet. Just keeping an
open mind.

[Siemel Naran]

"Daniel T." <po********@eat hlink.net> wrote in message news:postmaster-

The basic loop, has absolutly no reuse value but expresses itself
clearly to even the most raw beginner.
Which one was the basic loop?
for_each and a custom functor, also has little to no reuse value and
removes to locality of reference that the loop has, which makes it
harder to understand.
Yes, that's the trouble I have with for_each. Though if you can use
existing binders and functors like std::equal and the ones in boost, you can
make the intent clear in the calling code. But on the other hand, there's a
high learning curve to understanding these functors. Sure, std::equal makes
sense as does std::bind2nd, but throw them together and the resulting code
looks a tad intimidating. Also, there's a proposal to enhance the C++
standard to allow local classes to have an external linkage. This would
allow us to define the class inside the function that uses it in a call to
for_each. This could be a nice boost (sorry for the bad pun :) to the use
of for_each, transform, and the others.
Segmented iterator, has a slightly higher reuse potential and once you
know how the OverPair iterator works, is easy to understand (although
comming up with it wasn't very intuitave for me.)
Sure, the segmented iterator is a challenge, but now you know how to write a
std::deque::ite rator.
expanding_trans form algorithm, has the greatest reuse potential while
requiring a better undersanding of how to compose functors.

What is expanding_trans form?

[Daniel T.]

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

"Daniel T." <po********@eat hlink.net> wrote in message news:postmaster-

The basic loop, has absolutly no reuse value but expresses itself
clearly to even the most raw beginner.

Which one was the basic loop?

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

for_each and a custom functor, also has little to no reuse value and
removes to locality of reference that the loop has, which makes it
harder to understand.

Yes, that's the trouble I have with for_each. Though if you can use
existing binders and functors like std::equal and the ones in boost, you can
make the intent clear in the calling code. But on the other hand, there's a
high learning curve to understanding these functors. Sure, std::equal makes
sense as does std::bind2nd, but throw them together and the resulting code
looks a tad intimidating.

Only because we were taught C++ "from the ground up". First as a "better
C", with the libraries coming last. I suspect that someone who was
taught C++ from the libraries down (much like in the book "Accelerate d
C++" this would be much less of an issue.

IMO, proper use of the standard library (especially the algorithms and
functors) is what makes someone a C++ programmer, rather than a
programmer who happens to use C++.

expanding_trans form algorithm, has the greatest reuse potential while
requiring a better understanding of how to compose functors.

What is expanding_trans form?

That was my solution to the problem presented:

Write a new algorithm:

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

Then use a couple of functors that came in STL (but didn't make it into
the standard) to produce:

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

expanding_trans form has more reuse potential than OverPair because it
can be used on input that *isn't* a pair.

[Old Wolf]

"Daniel T." <po********@eat hlink.net> wrote:

(Jerry Coffin) wrote:

[snip lots of complicated crap]

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.

#include <algorithm>
#include <utility>
#include <vector>

typedef std::pair<unsig ned int, unsigned int> upair;

unsigned int head(upair p1, upair p2)
{ return p1.first & p2.second & 0xFF000000; }

// ...
std::vector< upair > vec;
// ...

std::vector< uint > out(vec.size()) ;
std::transform( vec.begin(), vec.end(), vec.begin(), out.begin(), head);

[Daniel T.]

In article <84************ **************@ posting.google. com>,
ol*****@inspire .net.nz (Old Wolf) wrote:

"Daniel T." <po********@eat hlink.net> wrote:

(Jerry Coffin) wrote:

[snip lots of complicated crap]

>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.

#include <algorithm>
#include <utility>
#include <vector>

typedef std::pair<unsig ned int, unsigned int> upair;

unsigned int head(upair p1, upair p2)
{ return p1.first & p2.second & 0xFF000000; }

// ...
std::vector< upair > vec;
// ...

std::vector< uint > out(vec.size()) ;
std::transform( vec.begin(), vec.end(), vec.begin(), out.begin(), head);

Still doesn't work. After the transform is complete, out.size() will
equal vec.size() which is not what the OP wanted. He wanted out.size()
to equal vec.size() * 2.

[Old Wolf]

"Daniel T." <po********@eat hlink.net> wrote:

Old Wolf wrote:

"Daniel T." <po********@eat hlink.net> wrote:

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.

std::vector< uint > out(vec.size()) ;
std::transform( vec.begin(), vec.end(), vec.begin(), out.begin(), head);

Still doesn't work. After the transform is complete, out.size() will
equal vec.size() which is not what the OP wanted. He wanted out.size()
to equal vec.size() * 2.

Ah. I misread the OP's question (several times..) , his input had
2 pairs and 3 outputs (so I guess 2 outputs was as good a guess as 4 :)
In that case, I think std::transform is not appropriate, as the output
list has to be the same size as the input list. I'd stick with for_each.

OTOH, I wonder if he did that on purpose and wants his output vector
to not repeat duplicates..

[Daniel T.]

In article <84************ **************@ posting.google. com>,
ol*****@inspire .net.nz (Old Wolf) wrote:

"Daniel T." <po********@eat hlink.net> wrote:

Old Wolf wrote:

>"Daniel T." <po********@eat hlink.net> wrote:
>> 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.

> std::vector< uint > out(vec.size()) ;
> std::transform( vec.begin(), vec.end(), vec.begin(), out.begin(), head);

Still doesn't work. After the transform is complete, out.size() will
equal vec.size() which is not what the OP wanted. He wanted out.size()
to equal vec.size() * 2.

Ah. I misread the OP's question (several times..) , his input had
2 pairs and 3 outputs (so I guess 2 outputs was as good a guess as 4 :)
In that case, I think std::transform is not appropriate, as the output
list has to be the same size as the input list. I'd stick with for_each.

As has been shown, it *can* be done with transform as long as you have
an iterator that can handle it. But overall, I agree with you. I think
it better to make a new algorithm for this problem, that can also be
used in other related problems...

OTOH, I wonder if he did that on purpose and wants his output vector
to not repeat duplicates..

The simple solution there is to output into a set first, then copy the
set to the output vector (if necessary.) It becomes much harder if the
items need to be kept in the same order though. In that case, one would
be forced to use a custom iterator that keeps track internaly what items
have been added to the output (ie the iterator would contain a set
object.)