5
\$\begingroup\$

I have a created small program that prints a sequence of prime numbers. Based on the origin code in here.

How can I improve this code?

#include <iostream>

template <std::size_t p, std::size_t i>
struct Run 
{
    static const bool mValue = ((p % i) && Run<p, i - 1>::mValue);
};

template <std::size_t p>
struct Run<p, 1> 
{
    static const bool mValue = true;
};

template <std::size_t i>
struct Prime 
{      
    Prime<i - 1> mPrime;
    static const bool mResult = Run<i, i - 1>::mValue;

    void print() 
    {
        mPrime.print();

        if (mResult)
        {
            std::cout << "prime number: " << i << '\n';
        }
    }
};

template<>
struct Prime<1> 
{   
    static const bool mResult = false;

    void print() 
    {
    }
};

int main()
{
    Prime<30> PrimeNumbers;
    PrimeNumbers.print();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ A template-based prime number generator? I am not a C++ expert at all, but doesn't that instantiate the template function for each number from 1 to 30? Try to compile this with 300 instead of 30! \$\endgroup\$ – Martin R Dec 3 '14 at 20:30
  • \$\begingroup\$ Doesn't this mean you can't use runtime variables as input? \$\endgroup\$ – raptortech97 Dec 3 '14 at 21:48
  • \$\begingroup\$ So if I understand it correctly, the primality check is done at compile time. \$\endgroup\$ – Martin R Dec 3 '14 at 22:47
  • 4
    \$\begingroup\$ It is a compile time generator, indeed, which means you can only use it with compile time constants. Alternatively, you could do the same thing in C++11 using constexpr, in a much simpler way. \$\endgroup\$ – glampert Dec 4 '14 at 3:28
5
\$\begingroup\$

How can I improve this code?

The code itself isn't particularly useful. You can print the primes up to N, but what if I wanted to sum all the primes up to N? In this model, you'd have to add a sum() member function to Prime<i> and again to Prime<1>. That doesn't make for a very reusable system. So let's go for something reusable, and in C++11 to boot.

Checking primality

Run isn't a particularly good name for a metafunction that determines if something is prime or not. Furthermore it doesn't even have to be a metafunction, it can be a constexpr function:

constexpr bool is_prime(std::size_t N)
{
    if (N < 2) return false;

    for (std::size_t i=2; i*i <= N; ++i) {
        if (N%i == 0) return false;
    }
    return true;
}

Check primality for lots of numbers

Your original example wanted all primes under 30. The standard metaprogramming mechanism for getting all numbers under 30 is:

using Nums = std::make_index_sequence<31>; // std::index_sequence<0, 1, 2, ..., 30>;

Although that gives us numbers and metaprogramming is all about types. Anything that isn't a type is usually a real nuisance to deal with, so let's write something to instead give us a list of types:

template <typename T>
struct type_is { using type = T; };

template <typename...>
struct typelist { };

namespace details {
    template <std::size_t N, typename = std::make_index_sequence<N>>
    struct make_type_index_sequence;

    template <std::size_t N, std::size_t... Is>
    struct make_type_index_sequence<N, std::index_sequence<Is...>> {
        using type = typelist<std::integral_constant<std::size_t, Is>...>;
    };
}

template <std::size_t N>
using make_type_index_sequence = typename details::make_type_index_sequence<N>::type;

// typelist<size_t_<0>, size_t_<1>, ..., size_t_<30>>, where size_t_<N> is integral_constant<size_t, N>
using Nums = make_type_index_sequence<31>; 

Ok, we have a typelist. Now we just need to filter it down based on a condition. To filter, we need to be able to concatenate:

template <typename... Args>
struct concat;

template <typename... Args>
using concat_t = typename concat<Args...>::type;

template <typename... A1, typename... A2, typename... Args>
struct concat<typelist<A1...>, typelist<A2...>, Args...> {
    using type = concat_t<typelist<A1..., A2...>, Args...>;
};

template <typename TL>
struct concat<TL> {
    using type = TL;
};

After which filter comes naturally:

template <typename A, typename F>
using filter_one = std::conditional_t<F::template apply<A>::value,
                                      typelist<A>,
                                      typelist<>>;

template <typename TL, typename F>
struct filter;

template <typename... Args, typename F>
struct filter<typelist<Args...>, F> {
    using type = concat_t<filter_one<Args, F>...>;
};

template <typename TL, typename F>
using filter_t = typename filter<TL, F>::type;

Metafunction classes

Something needs to be mentioned about this construction:

F::template apply<A>::value

Here F is a "metafunction class". That is, it's a type of the form:

struct MetafunctionClass {
    template <typename... Args>
    using apply = ???
};

Metaprogramming is all about convention. If everybody doesn't agree on convention, everybody's metaprograms may as well be written in different languages. The most core convention is that the "return" of a metafunction lives in a type named type. But a fairly common one is that when you need a "metafunctor", you pass something like this. The advantage of something like this is that it's always easy to create a type, but usually not so easy to create a template template (which would be the alternative).

Specifically here, we need:

struct IsPrime {
    template <typename T>
    using apply = std::integral_constant<bool, is_prime(T::value)>;
};

with which getting all the primes under 30 is:

template <size_t N>
using PrimesUnder = filter_t<make_type_index_sequence<N>, IsPrime>;

What can I do with this?

Well, anything really. Now that I made it easy to generate the primes, anything we may want to do with them is easy too. Printing them?

template <typename... Ts, typename F>
void for_each(typelist<Ts...>, F f) {
    using expander = int[];
    expander{0,
        (void(f(type_is<Ts>{})), 0)...
    };
}

for_each(PrimesUnder<30>{}, [](auto t) {
    std::cout << "prime number: " << decltype(t)::type::value << std::endl;
});

Summing them?

template <typename TL, typename F, typename Z>
using foldl_t = ??? // exercise for the reader

struct Add {
    template <typename T, typename U>
    using apply = std::integral_constant<decltype(T::value + U::value),
                      T::value + U::value
                      >;
};

template <size_t N>
using SumOfPrimesUnder = foldl_t<PrimesUnder<N>, Add, std::integral_constant<int, 0>>;

Anything else you may need to do with your primes? You have the typelist - it's all in your hands.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.