How to create compile-time templatized set/array/vector with fibonacci numbers using templates?

Question

I have a class template

template<typename U, ...more specialization... > class A {

    static_assert(std::is_arithmetic<U>::value, "U type must be arithmetic");

    public:
        const std::set<U> fibonacci = ???; //May be any structure with iterators, not necessarily set

    ...more code...    

};

"fibonacci" has to be a structure, created in compile-time, containing all fibonacci numbers of type U, from 1 to maximal possible fibonacci number smaller than max_U. Since I don't know what the type U is (I only know that it's arithmetic), I have to somehow check how many numbers I can generate. I tried many different approaches, but none of them worked.

For example, I tried doing something like this:

template <typename U, size_t N>
constexpr U Fib() {
    if (N <= 1) return 1; //was N < 1 (incorrect)
    return Fib<U, N-1>() + Fib<U, N-2>();
}

template <typename U, size_t n, typename ... Args>
constexpr std::set<U> make_fibonacci_set(Args ...Fn) {
    if (Fib<U, n>() <= Fib<U, n-1>()) {
        return std::set<U> {{Fn...}};
    }
    else {
        return make_fibonacci_set<U, n+1>(Fn..., Fib<U, n>());
    }
}

at class A...: const std::set<U> fibonacci = make_fibonacci_set<U, 2>(1);

But I get an error: "fatal error: recursive template instantiation exceeded maximum depth of 256".

Answer 1

Due to a quirk of the language, Fib() and make_fibonacci_set(), as written, will have infinite recursion (specifically, to my understanding, the problem is that while only one branch is chosen, both are evaluated; this causes the compiler to instantiate the templates required by the recursive branch, even when the other is chosen, generating infinite instantiations). To my understanding, constexpr if would resolve this nicely; however, I don't currently have access to any compilers that support it, so this answer will instead rework the former to rely on a helper (so introspection can be performed, and to aid in making a fully compile-time container class), and use SFINAE to break the latter into two distinct functions (to hide each one's return statement from the other).

First, before we get to the actual code, we'll want a helper macro if MSVC compatibility is desired, due to its (as of Nov.29, 2016) incomplete support of expression SFINAE.

// Check for MSVC, enable dummy parameter if we're using it.
#ifdef    _MSC_VER
    #define MSVC_DUMMY int MSVCDummy = 0
#else  // _MSC_VER
    #define MSVC_DUMMY
#endif // _MSC_VER

And now, the code itself. First, Fib()'s helper.

namespace detail {
    // Error indicating.
    // Use 4 to indicate overflow, since it's not a Fibonacci number.
    // Can safely be replaced with any number that isn't in the Fibonacci sequence.
    template<typename U>
    constexpr U FibOverflowIndicator = 4;

    // -----

    // Fibonacci sequence.

    template<typename U, size_t N>
    struct Fib {
      private:
        static constexpr U getFib();

      public:
        // Initialised by helper function, so we can indicate when we overflow U's bounds.
        static constexpr U val = getFib();
    };

    // Special cases: 0 and 1.
    template<typename U>
    struct Fib<U, 0> {
        static constexpr U val = 1;
    };

    template<typename U>
    struct Fib<U, 1> {
        static constexpr U val = 1;
    };

    // Initialiser.
    template<typename U, size_t N>
    constexpr U Fib<U, N>::getFib() {
        // Calculate number as largest unsigned type available, to catch potential overflow.
        // May emit warnings if type actually is largest_unsigned_t, and the value overflows.

        // Check for existence of 128-bit unsigned types, or fall back to uintmax_t if none are available.
        // Update with any other platform- or compiler-specific checks and type names as necessary.
        // Note: GCC will emit warnings about use of __int128, if -Wpedantic is specified.
        #ifdef    __SIZEOF_INT128__
            using largest_unsigned_t = unsigned __int128;
        #else  // __SIZEOF_INT128__
            using largest_unsigned_t = std::uintmax_t;
        #endif // __SIZEOF_INT128__

        largest_unsigned_t temp = static_cast<largest_unsigned_t>(Fib<U, N-1>::val) +
                                  Fib<U, N-2>::val;

        // Cast number back to actual type, and make sure that:
        //  1. It's larger than the previous number.
        //  2. We didn't already overflow.
        // If we're good, return the number.  Otherwise, return overflow indicator.
        return ((static_cast<U>(temp) <= Fib<U, N-1>::val) ||
                Fib<U, N-1>::val == FibOverflowIndicator<U>
                  ? FibOverflowIndicator<U>
                  : static_cast<U>(temp));
    }

    // -----

    // Introspection.

    template<typename U, size_t N>
    constexpr bool isValidFibIndex() {
        return Fib<U, N>::val != FibOverflowIndicator<U>;
    }

    template<typename U, size_t N = 0>
    constexpr std::enable_if_t<!isValidFibIndex<U, N + 1>(), U>
    greatestStoreableFib(MSVC_DUMMY) {
        return Fib<U, N>::val;
    }

    template<typename U, size_t N = 0>
    constexpr std::enable_if_t<isValidFibIndex<U, N + 1>(), U>
    greatestStoreableFib() {
        return greatestStoreableFib<U, N + 1>();
    }

    template<typename U, size_t N = 0>
    constexpr std::enable_if_t<!isValidFibIndex<U, N + 1>(), size_t>
    greatestStoreableFibIndex(MSVC_DUMMY) {
        return N;
    }

    template<typename U, size_t N = 0>
    constexpr std::enable_if_t<isValidFibIndex<U, N + 1>(), size_t>
    greatestStoreableFibIndex() {
        return greatestStoreableFibIndex<U, N + 1>();
    }
} // namespace detail

This allows us to define Fib() trivially, and provide a convenient means of introspection.

template<typename U, size_t N>
constexpr U Fib() {
    return detail::Fib<U, N>::val;
}

template<typename U>
struct FibLimits {
    // The largest Fibonacci number that can be stored in a U.
    static constexpr U GreatestStoreableFib = detail::greatestStoreableFib<U>();

    // The position, in the Fibonacci sequence, of the largest Fibonacci number that U can store.
    //  Position is zero-indexed.
    static constexpr size_t GreatestStoreableFibIndex = detail::greatestStoreableFibIndex<U>();

    // The number of distinct Fibonacci numbers U can store.
    static constexpr size_t StoreableFibNumbers = GreatestStoreableFibIndex + 1;

    // True if U can store the number at position N in the Fibonacci sequence.
    //  Starts with 0, as with GreatestStoreableFibIndex.
    template<size_t N>
    static constexpr bool IsValidIndex = detail::isValidFibIndex<U, N>();
};

And now, for make_fibonacci_set(). I changed the way this one works a bit; specifically, I made it a wrapper for another function called make_fibonacci_seq(), which is a more generic version that works for any valid container.

// Fibonacci number n is too large to fit in U, let's return the sequence.
template<typename U, typename Container, size_t n, U... us>
constexpr std::enable_if_t<Fib<U, n>() == detail::FibOverflowIndicator<U>, Container>
make_fibonacci_seq(MSVC_DUMMY) {
    return {{us...}};
}

// Fibonacci number n can fit inside a U, continue.
template<typename U, typename Container, size_t n, U... us>
constexpr std::enable_if_t<Fib<U, n>() != detail::FibOverflowIndicator<U>, Container>
make_fibonacci_seq() {
    return make_fibonacci_seq<U, Container, n+1, us..., Fib<U, n>()>();
}

// Wrapper for std::set<U>.
template<typename U, size_t n>
constexpr auto make_fibonacci_set() {
    return make_fibonacci_seq<U, std::set<U>, n>();
}

This can cleanly assign the sequence to a std::set, or to other types (such as std::vector.

template<typename U> class A {
    static_assert(std::is_arithmetic<U>::value, "U type must be arithmetic");

    public:
        // Assign to std::set.
        const std::set<U> fibonacci = make_fibonacci_set<U, 0>();

        // Assign to any container.
        const std::vector<U> fibonacci_v = make_fibonacci_seq<U, std::vector<U>, 0>();
};

---

If you want fibonacci to be created at compile time, however, it has to be a LiteralType, a type that can be created at compile time. std::set<T> is not a LiteralType, hence it can't be used for a compile-time Fibonacci sequence. Therefore, if you want to guarantee that it'll be constructed at compile time, you'll want your class to use a compile-time constructible container, such as std::array. Conveniently, make_fibonacci_seq() there lets you specify the container, so...

// Use FibLimits to determine bounds for default container.
template<typename U, typename Container = std::array<U, FibLimits<U>::StoreableFibNumbers>>
class Fibonacci {
    static_assert(std::is_arithmetic<U>::value, "U type must be arithmetic.");
    static_assert(std::is_literal_type<Container>::value, "Container type must be a LiteralType.");

  public:
    using container_type = Container;

    static constexpr Container fibonacci = make_fibonacci_seq<U, Container, 0>();
};
template<typename U, typename Container>
constexpr Container Fibonacci<U, Container>::fibonacci;

// -----

// Alternative, more robust version.

// Conditionally constexpr Fibonacci container wrapper; Fibonacci will be constexpr if LiteralType container is supplied.
// Use FibLimits to determine bounds for default container.
template<typename U,
         typename Container = std::array<U, FibLimits<U>::StoreableFibNumbers>,
         bool = std::is_literal_type<Container>::value>
class Fibonacci;

// Container is constexpr.
template<typename U, typename Container>
class Fibonacci<U, Container, true> {
    static_assert(std::is_arithmetic<U>::value, "U type must be arithmetic.");
    static_assert(std::is_literal_type<Container>::value, "Container type must be a LiteralType.");

  public:
    using container_type = Container;

    static constexpr Container fibonacci = make_fibonacci_seq<U, Container, 0>();
    static constexpr bool is_constexpr = true;
};
template<typename U, typename Container>
constexpr Container Fibonacci<U, Container, true>::fibonacci;

// Container isn't constexpr.
template<typename U, typename Container>
class Fibonacci<U, Container, false> {
    static_assert(std::is_arithmetic<U>::value, "U type must be arithmetic.");

  public:
    using container_type = Container;

    static const Container fibonacci;
    static constexpr bool is_constexpr = false;
};
template<typename U, typename Container>
const Container Fibonacci<U, Container, false>::fibonacci = make_fibonacci_seq<U, Container, 0>();

---

See it in action here (original link here).