In article <11*********************@m7g2000cwm.googlegroups.c om>,

ja****@gmail.com wrote:

Hi!

Sorry for the bad subject line... Here's what I mean. Suppose we deal

with C++ standard integers lists (the type is indifferent). We have a

function f, declared as

list<intf(int);

Now we have an integer list p, say. For each element x in p, we want to

repace x with f(x) to get a new, possibly larger, integer list. Note

that we do not want a list of integer lists.

For instance, if p=[1,2,3] and f(x)=[x*x,x*x*x], we want to run

"apply(p)", after which p=[1,1,4,8,9,27]. In my particular application,

this step is thought of as a "refinement" of the information available

in the list. It's a perfect situation for recursion, but the recursion

becomes too deep (generating a crash).

This is what I started with based on your description (without looking

at your code.)

list<intf( int i ) {

list<intresult;

result.push_back( i * i );

result.push_back( i * i * i );

return result;

}

template < typename InIt, typename OutIt, typename Op >

void apply( InIt first, InIt last, OutIt result, Op fn )

{

}

int main() {

int input[] = { 1, 2, 3 };

vector< int result;

apply( input, input + 3, back_inserter( result ), &f );

cout << "result == " << result.size() << "\n";

assert( result.size() == 6 );

assert( result[0] == 1 );

assert( result[1] == 1 );

assert( result[2] == 4 );

assert( result[3] == 8 );

assert( result[4] == 9 );

assert( result[5] == 27 );

}

Now it's simply a matter of filling in the "apply" function. I have to

run through the first container (from 'first' to 'last') calling 'fn' on

each item. This returns a list of interim results which I must then copy

into the result...

template < typename InIt, typename OutIt, typename Op >

void apply( InIt first, InIt last, OutIt result, Op fn )

{

while ( first != last ) {

list<intinterim = fn( *first++ );

copy( interim.begin(), interim.end(), result );

}

}

Note, this apply can use any sort of input container, output to any sort

of container and perform an operation that produces any number of

results (though it must return a list<int>.) You could, for example,

output directly to cout by providing a ostream_iterator as the third

argument. :-)

The code below does *not* work (it returns [1,1,1,4,8,9,27] -- that is,

one 1 too much). And it probably does more copying than necessary :/

And it's ugly. Any help on how to do this in a cleaner and more

elegant way is much appreciated!

#include <iostream>

#include <list>

#include <iterator>

list<intf(int x)

{

list<intl;

l.push_back(x*x);

l.push_back(x*x*x);

return l;

}

void apply(list<int&l)

{

list<int>::iterator old_i = l.begin();

list<intresult = f(*old_i);

l.insert(old_i, result.begin(), result.end());

for (list<int>::iterator i=++l.begin(); i!=l.end(); i++)

{

l.erase(old_i); // Now it's safe to erase this element

old_i = i; // We need to save i to compute next iterator

i++

result = f(*i);

l.insert(i, result.begin(), result.end());

}

l.erase(old_i);

}

int main()

{

list<intl1;

l1.push_back(1);

l1.push_back(2);

l1.push_back(3);

apply(l1);

for(list<int>::iterator i=l1.begin(); i!=l1.end(); i++)

cout << *i << " ";

cout << endl;

return 0;

}

OK, I see you are trying to replace the items in the list while

iterating over it. I think that is a needless complication. Better would

be to produce a new list and then simply swap them or assign the new

list to the old. Let's say however, that doing so was impossible for

some reason, then what would I do?

template < typename Seq, typename Op >

void apply( Seq& sequence, Op fn )

{

typename Seq::iterator pos = sequence.begin();

while ( pos != sequence.end() ) {

typename Seq::value_type value = *pos;

pos = sequence.erase( pos );

typedef list< typename Seq::value_type InterimType;

InterimType interim = fn( value );

// can't use std::copy with an inserter or range insert here

// because I can't get a valid iterator back out of it.

for ( typename InterimType::iterator it = interim.begin();

it != interim.end(); ++it ) {

pos = sequence.insert( pos, *it );

++pos;

}

}

}

The above will work with most sequences i.e., vector, deque, & list. To

do that, I did have some complications that I wouldn't have had if I

only wanted to support std::list. Then I could simply have used the

range inserter.

template < typename T, typename Op >

void apply( list<T>& sequence, Op fn )

{

typename list<T>::iterator pos = sequence.begin();

while ( pos != sequence.end() ) {

T value = *pos;

pos = sequence.erase( pos );

list< T interim = fn( value );

sequence.insert( pos, interim.begin(), interim.end() );

}

}

The primary difference I see between your code and mine, is that you

tried to do the first iteration outside the loop. Apparently you made a

mistake in that code.

--

There are two things that simply cannot be doubted, logic and perception.

Doubt those, and you no longer*have anyone to discuss your doubts with,

nor any ability to discuss them.