c++ - 如何使用模板创建带有斐波那契数的编译时模板化集/数组/vector ？

Question

我有一个类模板

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”必须是一个结构，在编译时创建，包含所有 U 类型的斐波那契数，从 1 到小于 max_U 的最大可能斐波那契数。因为我不知道 U 是什么类型(我只知道它是算术)，所以我必须以某种方式检查我可以生成多少个数字。我尝试了很多不同的方法，但都没有奏效。

例如，我尝试做这样的事情:

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);

但我得到一个错误:“ fatal error :递归模板实例化超过最大深度 256”。

Answer 1

由于语言的怪癖，Fib()和 make_fibonacci_set() ，如所写，将具有无限递归(具体来说，据我了解，问题是虽然只选择了一个分支，但都被评估；这导致编译器实例化递归分支所需的模板，即使选择了另一个分支，生成无限实例化)。据我了解，constexpr if会很好地解决这个问题；但是，我目前无法访问任何支持它的编译器，因此这个答案将改写前者以依赖帮助程序(因此可以执行内省(introspection)，并帮助制作一个完全编译时的容器类)，并使用 SFINAE 将后者分解为两个不同的函数(以隐藏每个函数的 return 语句)。

首先，在我们开始实际代码之前，如果需要 MSVC 兼容性，我们需要一个辅助宏，因为它(截至 2016 年 11 月 29 日)不完全支持表达式 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

现在，代码本身。一、Fib()的 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

这允许我们定义 Fib()平凡，并提供一种方便的自省(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>();
};

现在，对于 make_fibonacci_set() .我稍微改变了这个的工作方式；具体来说，我将它作为另一个名为 make_fibonacci_seq() 的函数的包装器，这是适用于任何有效容器的更通用的版本。

// 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>();
}

这可以干净地将序列分配给 std::set ，或其他类型(例如 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>();
};

---

如果你想要fibonacci要在编译时创建，但是，它必须是 LiteralType ，一种可以在编译时创建的类型。 std::set<T>不是 LiteralType ，因此它不能用于编译时斐波那契数列。因此，如果你想保证它会在编译时构造，你会希望你的类使用编译时可构造的容器，例如 std::array。 .方便，make_fibonacci_seq()那里让你指定容器，所以......

// 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>();

---

查看实际效果 here (原文链接here)。