Template meta programming example - how to design a general geometry Library

design principle

Suppose you need to use a c + + program to calculate the distance between two points You might do this:

• First define a struct:

struct mypoint
{
    double x, y;
};

• Then define a function containing the calculation algorithm:

double distance(mypoint const& a, mypoint const& b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

Quite simple and practical, but not universal enough The design of a library needs to consider possible changes in the future
The above design can only be used for 2D points in Cartesian coordinate system
The general library needs to be able to calculate the following distances:

• Applicable to any point struct or point class, not just mypoint
• Not just two-dimensional
• Applicable to other coordinate systems, such as earth or sphere
• Be able to calculate the distance between points and lines or other geometric figures
• Higher accuracy than double
• Avoid using sqrt as much as possible: usually we don't want to call it because it's expensive And it's not necessary to compare distances

Next, we will give a more general implementation step by step

Use template

We can change the distance function into a template function In this way, the distance between other point types except mypoint can be calculated
We add two template parameters that allow you to enter two different point types

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return std::sqrt(dx * dx + dy * dy);
}

The template version is better than the previous implementation, but not enough
Consider that the member variable of c + + class is protected or cannot directly access x,y

Using Traits

We need to use a more general method to allow any point type to be used as the input of the distance function
In addition to direct access to x and y, we will add an indirect layer using the traits system
The distance function can be changed to:

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
    double dx = get<0>(a) - get<0>(b);
    double dy = get<1>(a) - get<1>(b);
    return std::sqrt(dx * dx + dy * dy);
}

The above distance function uses the get function to access the coordinate system of a point, and uses the dimension of the point as the template parameter
get can be implemented as follows:

namespace traits
{
    template <typename P, int D>
    struct access {};
}

Define template exceptions for mypoint:

namespace traits
{
    template <>
    struct access<mypoint, 0>
    {
        static double get(mypoint const& p)
        {
            return p.x;
        }
    };
    // same for 1: p.y
    ...
}

Now call traits:: access < mypoint, 0 >:: get (a) to return x in the coordinate system. We can further simplify the call method by defining get:

template <int D, typename P>
inline double get(P const& p)
{
    return traits::access<P, D>::get(p);
}

Through the above implementation, we can call get < 0 > (a) for any point a that has specialized traits::access
Based on the same principle, we can also get < 1 > (a) for coordinate y

Arbitrary dimension

In order to calculate any dimension, we can cycle through all dimensions However, circular call has performance overhead compared with direct calculation Therefore, we can implement such an algorithm by using templates:

template <typename P1, typename P2, int D>
struct pythagoras
{
    static double apply(P1 const& a, P2 const& b)
    {
        double d = get<D-1>(a) - get<D-1>(b);
        return d * d + pythagoras<P1, P2, D-1>::apply(a, b);
    }
};

template <typename P1, typename P2 >
struct pythagoras<P1, P2, 0>
{
    static double apply(P1 const&, P2 const&)
    {
        return 0;
    }
};

The distance function can then call pythagoras and specify the dimension:

template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
    BOOST_STATIC_ASSERT(( dimension<P1>::value == dimension<P2>::value ));

    return sqrt(pythagoras<P1, P2, dimension<P1>::value>::apply(a, b));
}

Dimensions can be implemented by defining another traits class:

namespace traits
{
    template <typename P>
    struct dimension {};
}

Then make a special case for the corresponding class (such as mypoint), because this traits only publishes a value, so for simplicity, we can inherit boost class boost::mpl::int_5;in MPL:

namespace traits
{
    template <>
    struct dimension<mypoint> : boost::mpl::int_<2>
    {};
}

Now we have realized the algorithm to calculate the distance of any dimension point We also use compile - time assertions to prevent computation of points in two different dimensions

Coordinate type

In the above implementation, we assumed the double type. What if the point is integer?

namespace traits
{
    template <typename P>
    struct coordinate_type{};

    // specialization for our mypoint
    template <>
    struct coordinate_type<mypoint>
    {
        typedef double type;
    };
}

Similar to the access function, we also add a proxy:

template <typename P>
struct coordinate_type :    traits::coordinate_type<P> {};

Then we can modify our distance calculation function Because the two point types of calculation may have different types, we must deal with this situation We need to select one of the types with higher precision as the result type. Let's assume there is a select_ most_ The precise meta function is used to select the best type

In this way, our calculation function can be changed to:

template <typename P1, typename P2, int D>
struct pythagoras
{
    typedef typename select_most_precise
        <
            typename coordinate_type<P1>::type,
            typename coordinate_type<P2>::type
        >::type computation_type;

    static computation_type apply(P1 const& a, P2 const& b)
    {
        computation_type d = get<D-1>(a) - get<D-1>(b);
        return d * d + pythagoras <P1, P2, D-1> ::apply(a, b);
    }
};