472,779 Members | 2,044 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 2053 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
--
Oct 12 '06 #3
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

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 thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 3 by: Chris Tanger | last post by: I am creating a class that has a method "Write" that I wish to make threadsafe. The method must block calling threads until the task performed in write is complete. Only 1 thread at a time can... 12 by: Vaca Louca | last post by: Hello, I write an ISAPI authentication module which uses Berkeley DB and want it to be as efficient as possible. Both ISAPI and BerkeleyDB use arrays of chars (char *) to pass and receive... 14 by: Jim Langston | last post by: Which is more efficient (if either) MyHugeClass MyObject; for ( int i = 0; i < 1000; ++i ) { MyObject = SomeVal; Use MyObject; } 8 by: dbamota | last post by: What is the syntax in UDB db2, to create an index IX in table TBL "in tablespace TBSP" which is different from the tablespace of TBL ? TIA 19 by: Materialised | last post by: Hi everyone, What I am wanting to do, is to copy, a simple plain text file, to another file, but omitting duplicate items. The way I thought of doing this, involved copying all the items into... 6 by: m | last post by: Hello, I have an application that processes thousands of files each day. The filenames and various related file information is retrieved, related filenames are associate and placed in a linked... 7 by: Kay Schluehr | last post by: I want to manipulate a deeply nested list in a generic way at a determined place. Given a sequence of constant objects a1, a2, ..., aN and a variable x. Now construct a list from them recursively:... 44 by: petermichaux | last post by: Hi, I have been using the following line of code to create an object called "Serious" if it doesn't already exist. if (Serious == null) {var Serious = {};} This works in the scripts I use... 12 by: pedagani | last post by: Dear comp.lang.c++, Could you make this snippet more efficient? As you see I have too many variables introduced in the code. //Read set of integers from a file on line by line basis in a STL... 0 by: Rina0 | last post by: Cybersecurity engineering is a specialized field that focuses on the design, development, and implementation of systems, processes, and technologies that protect against cyber threats and... 3 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 0 by: erikbower65 | last post by: Here's a concise step-by-step guide for manually installing IntelliJ IDEA: 1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on... 0 by: kcodez | last post by: As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it... 0 by: Taofi | last post by: I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ... 5 by: DJRhino | last post by: Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer) If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _ 310030356 Or 310030359 Or 310030362 Or... 0 by: lllomh | last post by: How does React native implement an English player? 0 by: Mushico | last post by: How to calculate date of retirement from date of birth 2 by: DJRhino | last post by: Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...