Efficient creation of "refined" list<T>, from old list<T>

[janzon]

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<int> f(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).

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<int> f(int x)
{
list<int> l;
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<int> result = 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<int> l1;
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;
}

 

[janzon]

This is better. But probably there are far cleaner ways of doing it.


void apply(list<int> &l)
{
list<int>::iterator i=l.begin();

while(i != l.end())
{
list<int>::iterator tmp_it = i;
list<int> result = f(*i);
l.insert(i, result.begin(), result.end());
i++;
l.erase(tmp_it);
}
}

 

[Victor Bazarov]

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<int> f(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.

You should probably reformulate this in terms of iterators. It will
be much easier to comprehend and it will essentially become your
algorithm.

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

There is no need for recursion. A simple loop should do. Just as
you have written it, erasing the element and inserting the "refined"
list in its place should be just fine. To speed it up, replace the
'erase + insert_1st' with 'assign'.

I am sure the following contains problems I've not found, it's up to
you to find them and debug it further...

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

template<class C, class F>
void refine(C &what, F how)
{
// assuming that F returns a C
typename C::iterator cb = what.begin(), ce = what.end();
while (cb != ce)
{
typename C::value_type val = *cb;
C c = how(val);
if (!c.empty())
{
typename C::iterator b = c.begin(), e = c.end();
*cb++ = *b++;
while (b != e)
what.insert(cb, *b++);
}
else
{
cb = what.erase(cb);
}
}
}

list<int> f(int i)
{
int ii_iii[] = { i*i, i*i*i };
return list<int>(ii_iii, ii_iii+2);
}

int main()
{
list<int> onetwothree;
onetwothree.push_back(1);
onetwothree.push_back(2);
onetwothree.push_back(3);

refine(onetwothree, f);

std::copy(onetwothree.begin(), onetwothree.end(),

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!

[..code I didn't want to fix redacted..]

V

 

[Daniel T.]

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<int> f(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<int> f( int i ) {
list<int> result;
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<int> interim = 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<int> f(int x)
{
list<int> l;
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<int> result = 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<int> l1;
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.