Konrad Hinsen asked:
> Suppose I have an algorithm for a specific problem, and an
> implementation that works. Now I want to tackle a similar problem that
> can be solved by a similar algorithm. All it takes is perhaps the
> modification of one step, or the addition of one. I would like to be
> able to "inherit" the working implementation while just replacing or
> adding small parts of it. And of course I do not want to modify the
> existing (supposedly well tested) code.
In C++, there are four approaches to this problem that I know of
which don't require the use of external tools: polymorphism,
template functors, function template parameters, and expression
templates. Of these, function template parameters are probably
the least well known.
1. Use a polymorphic class to encapsulate the algorithm (as Steve
Karmesin described). Portions of the algorithm which need to be
modified can be made virtual functions. This is very similar
to the C-style approach of passing pointers-to-functions.
Example:
// This class integrates a function f(x) on the domain [a,b] using
// naive summation.
class Integrator {
public:
double integrate(double a, double b, int numSamplePoints)
{
PRECONDITION(numSamplePoints > 1);
double delta = (b-a) / (numSamplePoints-1);
double sum = 0.;
for (int i=0; i < numSamplePoints; ++i)
sum += functionToIntegrate(a + i*delta);
return sum * (b-a) / numSamplePoints;
}
virtual double functionToIntegrate(double x) = 0;
};
class MyFunction : public Integrator {
public:
virtual double functionToIntegrate(double x)
{ return 1 / (1 + x); }
};
Disadvantage: the bodies of the virtual functions are not inlined
into the algorithm. If the virtual function calls are made in
inner loops and the functions contain only a small amount of code,
the performance loss is substantial due to virtual function
overhead and pipeline stalls.
2. Functors a la STL
Put the code which needs to be modifiable in a separate "functor"
class as inline methods, and give the algorithm a template parameter
for the functor class.
Example:
template<class T_function>
double integrate(T_function functionToIntegrate, double a, double b,
int numSamplePoints)
{
PRECONDITION(numSamplePoints > 1);
double delta = (b-a) / (numSamplePoints-1);
double sum = 0.;
for (int i=0; i < numSamplePoints; ++i)
sum += functionToIntegrate(a + i*delta);
return sum * (b-a) / numSamplePoints;
}
class MyFunction {
public:
double operator()(double x) const
{
return 1 / (1 + x);
}
};
double z = integrate(MyFunction(), 0, 1, 50);
Advantage: code gets inlined into the algorithm.
Disadvantage: not a very nice interface to the end user, since
all the "plug-n-play" code has to be wrapped in classes.
3. Function template parameters
The C++ standard permits functions to be used as template parameters.
This example pushes the limits of what most compilers will currently
accept, but to my knowledge it's standard compliant.
template<double functionToIntegrate(double)>
double integrate(double a, double b, int numSamplePoints)
{
PRECONDITION(numSamplePoints > 1);
double delta = (b-a) / (numSamplePoints-1);
double sum = 0.;
for (int i=0; i < numSamplePoints; ++i)
sum += functionToIntegrate(a + i*delta);
return sum * (b-a) / numSamplePoints;
}
inline double myFunction(double x)
{
return 1 / (1 + x);
}
// Example use
double z = integrate<myFunction>(0.0, 1.0, 50);
Using KAI C++, I've been able to get a similar bit of code working
(although with a class template, not a function template). KAI
will inline the body of myFunction() into the integrate() function.
This provides a somewhat nicer interface to the end user.
4. Expression templates
This will only work if you need to inline small arithmetic
expressions (e.g. little equations). Using expression templates,
you can write code like this:
template<class T_expression>
double integrate(T_expression expression, double a, double b,
int numSamplePoints)
{
PRECONDITION(numSamplePoints > 1);
double delta = (b-a) / (numSamplePoints-1);
double sum = 0.;
for (int i=0; i < numSamplePoints; ++i)
sum += expression(a + i*delta);
return sum * (b-a) / numSamplePoints;
}
// Example usage
DoublePlaceholder x;
double z = integrate(1 / (1 + x), 0, 1, 50);
Cheers,
Todd
This archive was generated by hypermail 2b29 : Wed Feb 20 2002 - 03:20:05 EST