Recursive template definition

Question

I have a recursive template definition (I just made up that term). I think code explains it better.

template<typename X>
class Domain
{
    public:
        X begin;
        X end;

        Domain(
            X _begin, 
            X _end)
            : begin(_begin)
            , end(_end)
        {
            // ...
        }

        bool Contains(
           const X& t) const
        {
            // ...
        }
};

template<typename X, typename Y>
class IFunction
{
    public:
        Domain<X> myDomain;

    public:
        IFunction(
            const Domain<X>& dom)
            : myDomain(dom)
        {

        }

        virtual Y
        Calc(
            const X& IV) const = 0;

        virtual IFunction<X, Y>*
        GetDerivative() const = 0;
};

template<typename X, typename Y, int n>
class NthOrderFunction
    : public IFunction<X, Y>
{
    public:
        double coeffs[n+1];

    public:
        NthOrderFunction(
            const Domain<X>& dom,
            ... )
            : IFunction(dom)
        {

        }

        virtual Y
        Calc(
            const X& IV) const
        {
            // temporary compile solution
            return Y();
        }

        virtual IFunction<X, Y>*
        GetDerivative() const
        {
            if ( n > 1 )
            {
                return new NthOrderFunction<X, Y, n-1>(dom, ...);
            }
            return new FlatLine<X, Y>(dom);
        }
};

I took out a lot of inheritance and other relations to keep it readable, simple and mysterious. So a new typo might have snuck in while editing the code, but please ignore it. The code has worked fine for years, the only problem I have is the one I'm going to point out.

I recently added a "GetDerivative" function, and it's implementation in the NthOrderFunction class is giving me problems. I know that template classes are defined before compilation but after the preprocessing. As such, I can't see how to bring this functionality ever to work. Every NthOrderFunction with template parameter n, requires a NthOrderFunction with template parameter n-1. You can see that this is a problem. The thing is, even though n will never be negative in use, no amount of coding I do, will convince the "template definition engine" to not bother with instances of n < 1;

has anyone ever had any problems with this? And what solutions did you come up with?

Answer 1

Add something like:

template<typename X, typename Y>
class NthOrderFunction<X, Y, 1>
    : public IFunction<X, Y>
{
    public:
        double coeffs[n+1];

    public:
        NthOrderFunction(
            const Domain<X>& dom,
            ... )
            : IFunction(dom)
        {

        }

        virtual Y
        Calc(
            const X& IV) const
        {
            // temporary compile solution
            return Y();
        }

        virtual IFunction<X, Y>*
        GetDerivative() const
        {
            return new FlatLine<X, Y>(dom);
        }
};

and remove the n==1 case from your recursion case.

As an advice, get some book or tutorial or such on template metaprogramming. One of the base techniques is using recursion in templates in this fashion. This strictly speaking isn't metaprogramming yet, it's just recursive templates. The book/tutorial will explain how more advanced tricks work which you can use to your benefit when expanding on this.

The reason this works is that the original would still expand the compile-time "if" to runtime code (that would just never be executed). This code replaces the one case where it could be compiled out with one where it isn't present, so there's no option for infinite recursion.

Answer 2

This is the same as the template metaprogramming 101 example- factorial, just the content is somewhat more complex.

template<int N> struct factorial { enum { value = N * factorial<N-1>::value }; };

And you need the same solution- a specialization for the base case.

template<> struct factorial<1> { enum { value = 1 }; };

Yours would be partial rather than full, but it would still work.