I'm stuck with the implementation of a generic algorithm.... need some help :P

Discussion in 'C++' started by StephQ, Aug 1, 2007.

  1. StephQ

    StephQ Guest

    I need to implement an algorithm that takes as input a container and
    write some output in another container.
    The containers involved are usually vectors, but I would like not to
    rule out the possibility of using lists.
    The problem is that I need two versions of it, depending if I'm adding
    the generated (by the algorithm) values to the target container or if
    I just modify pre-existing values of the target container.
    Efficiency is important in this part of the software.
    The first solution is to write two versions of the algorithm:
    [firstTime, lastTime) define the input range, and firstTarget define
    the begin of target container.

    // Modify version, here V iterator, will use *firstTarget =
    // More precisely V is usually std::vector<double>::iterator taken
    from someVector.begin().
    template<class V, class T>
    void bmPathModify( V firstTarget, T firstTime, T lastTime )

    // Append version, here V is the container, will use
    firstTarget.push_back()
    template<class V, class T>
    void bmPathAppend( V& firstTarget, T firstTime, T lastTime )

    However this situation is going to repeat itself a lot of times, so I
    would like to use just one function and specify the behaviour using a
    policy defined by an additional template parameter:

    // P is the policy
    template<class V, class T, class P>
    void bmPathModify( V firstTarget, T firstTime, T lastTime )
    {
    ...
    P::Element( target, value );
    ..
    }

    class Modify // Policy class
    {
    public:

    template<class V>
    static void Element( V target, double value)
    {
    *target = value;
    }

    };

    The problem is then:
    I need to pass the iterator to the starting element of the target
    container to cover the Modify case.
    But then I can't figure out how to invoke the push_back() function to
    the target container starting from this iterator. I suspect I can't.
    What would be perfect would be the ability to deference the iterator
    two times to get the actual container but I think you can't do
    this....
    Is there a way to solve this situation using a single function for the
    algorithm?

    Thank you

    StephQ
     
    StephQ, Aug 1, 2007
    #1
    1. Advertisements

  2. StephQ

    werasm Guest

    If I understand your problem correctly, you may be looking for a
    back_inserter used in conjunction with transform. Typically a
    sequence
    can be modified (or transformed) and inserted into a new sequence
    like this:

    #include <algorithm> //for transform
    #include <iterator> //for back_inserter
    #include <vector> //or list...

    Transforming algorithm... Could be functor as well.
    Transformed Transformer( const Transformed& item )
    {
    //... Transform the item and return the result.
    }
    //...
    std::vector<Transformed> seq1; //or list...
    addItems( seq1 ); //Adds items to be transformed
    std::vector<Transformed> seq2; //Empty

    std::transform( seq1.begin(), seq1.end(), std::back_inserter( seq2 ),
    Transformer );

    You could also transform a sequence itself, just by using itself as
    destination.

    std::transform( seq1.begin(), seq1.end(), seq1, Transformer );

    Hope this helps. There are of course other ways to achieve the same
    effect. Note that
    transform assigns the result of transform, causing performance penalty
    depending
    on the cost of the assignment. For builtin types this is
    insignificant.

    Hope this helps

    Werner
     
    werasm, Aug 1, 2007
    #2
    1. Advertisements

  3. StephQ a écrit :
    Yes. You can use the std::copy algorithm of the STL.

    When you want to overwrite, you just use plain iterators; by example:
    copy(from.begin(),from.end(),to.begin());

    When, you want to append, you use a back_inserter:
    copy(from.begin(),from.end(), back_insert_iterator< list<int> >(to));

    Michael
     
    Michael DOUBEZ, Aug 1, 2007
    #3
  4. StephQ

    StephQ Guest

    I think it's better if I expose more details of the problem.
    Here is the code for what I need to accomplish using two functions:

    // Append version. Target is reference to container.
    template<class V, class T>
    void bmPath( V& target, double firstValue, T firstTime, T lastTime )
    {
    assert( target.back() == firstValue ); // Note no insertion of
    firstValue.

    T cTime;
    double bmValue;
    for (cTime = ++firstTime ; cTime != lastTime ; ++cTime)
    {
    bmValue = RandomNumber::generateGaussian( target.back(),
    sqrt( *cTime - *boost::prior( cTime ) ) );
    target.push_back( bmValue );
    }
    }

    // Modify version. Target is iterator to first element of the storage
    of the target container.
    template<class V, class T>
    void bmPath( V target, double firstValue, T firstTime, T lastTime )
    {
    *target = firstValue;

    T cTime;
    double bmValue;
    for (cTime = ++firstTime ; cTime != lastTime ; ++cTime)
    {
    bmValue = RandomNumber::generateGaussian( *target,
    sqrt( *cTime - *boost::prior( cTime ) ) );
    *(++target) = bmValue;
    }
    }

    I see two problems:
    1) I don't act directly on cTime but on square root of differences.
    And I need to avoid the creation of a temporary vector to store the
    square root of adjacent differences because of allocation penalties.
    2) I would need a policy for "firstValue" (different behaviour on the
    two versions of the algorithm).

    This is exactly what I need to accomplish.
    To sum up the goal is:
    1) have a single function with the same interface (where I pass an
    iterator to the first element of the storage of the target container)
    and specify the behaviour using traits.
    2) no (or very low) performance penalty compared to the versions here
    exposed. Creation of temporary containers is not acceptable in this
    part of the code.

    I know here the algorithm is very easy, but I have exactly the same
    problem for a large class of (quite complex) algorithms where the
    only thing that changes is the way I act on the target container.

    Thank you very much for your help!

    Best Regards
    StephQ
     
    StephQ, Aug 1, 2007
    #4
  5. StephQ

    StephQ Guest

    See my reply to werasm.
    Thank you for your help.

    Best Regards
    StephQ
     
    StephQ, Aug 1, 2007
    #5
  6. StephQ

    werasm Guest

    StephQ wrote:

    Ok, use the transform version that has the following signature:

    template <class InputIterator1, class InputIterator2, class
    OutputIterator,
    class BinaryFunction>
    OutputIterator
    transform(
    InputIterator1 first1, InputIterator1 last1,InputIterator2 first2,
    OutputIterator result, BinaryFunction binary_op);

    The key is that binary_op should be able to take as argument:

    ( *InputIterator1, *InputIterator2 ) and return OutputResult.

    Also note that the sequences should have the same amount of items. If
    you
    require to store state during the algorithm, you can use a functor
    that
    overloads operator() which could store state. You could, for instance,
    if you want to use the the result of the previous operation (I gather
    this
    from you call to back) either store the result in the functor, or
    store the
    actual sequence at construction. The sky is the limit. Wrt.
    efficiency,
    I can't help you. If your sequences mostly contain builtin types, or
    are small to copy, then efficiency should not cause concern.

    Unfortunately I can't solve the problem for you :), but it does look
    as if though
    transform is you key (IMHO).

    Regards,

    Werner
     
    werasm, Aug 1, 2007
    #6
  7. StephQ

    StephQ Guest

    Thanks for the reply.
    However I got an idea.... what if I use a back_insert_iterator?
    This way only one version can cover everything!
    I can pass a normal iterator if I want to overwrite or a
    back_insert_iterator if I want to append...
    May a back_insert_iterator become invalid if reallocation happens in a
    vector?
    Does this means that it's safe to use back_insert_iterator s only with
    lists?

    StephQ
     
    StephQ, Aug 1, 2007
    #7
  8. StephQ

    werasm Guest

    Did you not read my first reply (and others). We've mentioned
    std::back_inserter there.
    Yes, of course - read my first example.
    A back_inserter might cause reallocation if the vector exceeds its
    capacity.
    This may be prevented by reserving in the destination vector.
    No, back inserters always does push_back, and should not care whether
    iterators are invalidated or not. On the other hand, if your functor
    stores
    iterators while you traverse and pushback, then those may be
    invalidated.
    (but that is a bad idea anyway)

    Werner
     
    werasm, Aug 1, 2007
    #8
  9. StephQ

    StephQ Guest

    Yes I did. But I was stupid enough not to think of using it outside
    the copy/transform algorithms.... :p
    Yes I'm fine with that. I was worried with back_insert_iterator
    becoming invalidated. But an examination of the actual source code
    revealed that it's not really an iterator, and the problem does not
    exists.
    Thank you again. It seems that I finally solved my issue :)

    Cheers
    StephQ
     
    StephQ, Aug 1, 2007
    #9
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.