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

Discussion in 'C++' started by janzon@gmail.com, Oct 12, 2006.

  1. Guest

    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;
    }
     
    , Oct 12, 2006
    #1
    1. Advertising

  2. Guest

    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);
    }
    }
     
    , Oct 12, 2006
    #2
    1. Advertising

  3. 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<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(),
    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
     
    Victor Bazarov, Oct 12, 2006
    #3
  4. Daniel T. Guest

    In article <>,
    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<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.

    --
    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.
     
    Daniel T., Oct 12, 2006
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jeff
    Replies:
    1
    Views:
    315
    Chris Smith
    Dec 27, 2004
  2. Jim Hill
    Replies:
    3
    Views:
    425
    Jim Hill
    Feb 12, 2007
  3. mmoski
    Replies:
    7
    Views:
    372
  4. DZantow
    Replies:
    0
    Views:
    210
    DZantow
    Dec 20, 2011
  5. Hon Guin Lee - Web Producer - SMI Marketing

    LWP::Simple get() refined problem

    Hon Guin Lee - Web Producer - SMI Marketing, Sep 29, 2003, in forum: Perl Misc
    Replies:
    6
    Views:
    159
    Bart Lateur
    Sep 30, 2003
Loading...

Share This Page