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

[StephQ]

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<dou ble>::iterator taken
from someVector.begi n().
template<class V, class T>
void bmPathModify( V firstTarget, T firstTime, T lastTime )

// Append version, here V is the container, will use
firstTarget.pus h_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

[werasm]

StephQ wrote:

But then I can't figure out how to invoke the push_back() function to
the target container starting from this iterator.

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<Tra nsformedseq1; //or list...
addItems( seq1 ); //Adds items to be transformed
std::vector<Tra nsformedseq2; //Empty

std::transform( seq1.begin(), seq1.end(), std::back_inser ter( 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

[Michael DOUBEZ]

StephQ a écrit :

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.

[snip]

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?

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(),t o.begin());

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

Michael

[StephQ]

On Aug 1, 1:32 pm, werasm <wer...@gmail.c omwrote:

StephQ wrote:

But then I can't figure out how to invoke the push_back() function to
the target container starting from this iterator.

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<Tra nsformedseq1; //or list...
addItems( seq1 ); //Adds items to be transformed
std::vector<Tra nsformedseq2; //Empty

std::transform( seq1.begin(), seq1.end(), std::back_inser ter( 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

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::g enerateGaussian ( target.back(),
sqrt( *cTime - *boost::prior( cTime ) ) );
target.push_bac k( 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::g enerateGaussian ( *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]

On Aug 1, 1:45 pm, Michael DOUBEZ <michael.dou... @free.frwrote:

StephQ a écrit :

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.

[snip]

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?

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(),t o.begin());

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

Michael

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

Best Regards
StephQ

[werasm]

StephQ wrote:

Thanks for the reply.
However I got an idea.... what if I use a back_insert_ite rator?
This way only one version can cover everything!

Did you not read my first reply (and others). We've mentioned
std::back_inser ter there.

I can pass a normal iterator if I want to overwrite or a
back_insert_ite rator if I want to append...

Yes, of course - read my first example.

May a back_insert_ite rator become invalid if reallocation happens in a
vector?

A back_inserter might cause reallocation if the vector exceeds its
capacity.
This may be prevented by reserving in the destination vector.

Does this means that it's safe to use back_insert_ite rator s only with
lists?

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

[StephQ]

On Aug 1, 6:10 pm, werasm <wer...@gmail.c omwrote:

StephQ wrote:

Thanks for the reply.
However I got an idea.... what if I use a back_insert_ite rator?
This way only one version can cover everything!

Did you not read my first reply (and others). We've mentioned
std::back_inser ter there.

Yes I did. But I was stupid enough not to think of using it outside
the copy/transform algorithms.... :P

>

I can pass a normal iterator if I want to overwrite or a
back_insert_ite rator if I want to append...

Yes, of course - read my first example.

May a back_insert_ite rator become invalid if reallocation happens in a
vector?

A back_inserter might cause reallocation if the vector exceeds its
capacity.
This may be prevented by reserving in the destination vector.

Yes I'm fine with that. I was worried with back_insert_ite rator
becoming invalidated. But an examination of the actual source code
revealed that it's not really an iterator, and the problem does not
exists.

>

Does this means that it's safe to use back_insert_ite rator s only with
lists?

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)

Thank you again. It seems that I finally solved my issue :)

Cheers
StephQ

>
Werner