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.
