0

我有一个班级模板

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

但我收到一个错误：“致命错误：递归模板实例化超出最大深度 256”。

4

1 回答 1

2

由于语言的一个怪癖，Fib()并且make_fibonacci_set()，正如所写的那样，将具有无限递归（具体而言，据我了解，问题是虽然只选择了一个分支，但都会对两个分支进行评估；这会导致编译器实例化所需的模板递归分支，即使选择了另一个，也会产生无限的实例化）。据我了解，constexpr if会很好地解决这个问题；但是，我目前无法访问任何支持它的编译器，因此这个答案将改写前者以依赖帮助器（因此可以执行自省，并帮助制作一个完全编译时的容器类），并使用 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()帮手。

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()，并提供一种方便的自省方式。

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

这可以干净地将序列分配给 astd::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在编译时创建，它必须是 a LiteralType，一种可以在编译时创建的类型。 std::set<T>不是 a 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>();

在此处查看实际操作（此处为原始链接）。

于 2016-11-30T03:50:52.817 回答