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

 

[werasm]

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

 

[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(),to.begin());

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

Michael

 

[StephQ]

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

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:rior( 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:rior( 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]

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

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

Michael

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

Best Regards
StephQ

 

[werasm]

StephQ wrote:

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:rior( cTime ) ) );
target.push_back( bmValue );
}
}

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

 

[StephQ]

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

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

 

[werasm]

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!

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

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

Yes, of course - read my first example.

May a back_insert_iterator 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_iterator 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]

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

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

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.

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.

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