468,484 Members | 2,075 Online

# Efficient creation of "refined" list<T>, from old list<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<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).

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

Oct 12 '06 #1
3 1849 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<intresult = f(*i);
l.insert(i, result.begin(), result.end());
i++;
l.erase(tmp_it);
}
}

Oct 12 '06 #2
ja****@gmail.com wrote:
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.
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<intf(int i)
{
int ii_iii[] = { i*i, i*i*i };
return list<int>(ii_iii, ii_iii+2);
}

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

refine(onetwothree, f);

std::copy(onetwothree.begin(), onetwothree.end(),
ostream_iterator<int>(std::cout, ","));
}
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Oct 12 '06 #3
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 == 1 );
assert( result == 1 );
assert( result == 4 );
assert( result == 8 );
assert( result == 9 );
assert( result == 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.
Oct 12 '06 #4

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 3 posts views Thread by Chris Tanger | last post: by 12 posts views Thread by Vaca Louca | last post: by 14 posts views Thread by Jim Langston | last post: by 8 posts views Thread by dbamota | last post: by 19 posts views Thread by Materialised | last post: by 6 posts views Thread by m | last post: by 7 posts views Thread by Kay Schluehr | last post: by 44 posts views Thread by petermichaux | last post: by 12 posts views Thread by pedagani | last post: by reply views Thread by ravipankaj | last post: by reply views Thread by ravipankaj | last post: by reply views Thread by slotstar | last post: by 7 posts views Thread by isladogs | last post: by reply views Thread by captainhaddock | last post: by 1 post views Thread by AnjaGlonegger | last post: by 2 posts views Thread by rcsmith0712 | last post: by 1 post views Thread by rhonda6373 | last post: by reply views Thread by theflame83 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.