代码之家 › 专栏 › 技术社区 › GManNickG

在运行时获取模板元编程编译时常量

metaprogramming runtime templates c++

GManNickG · 技术社区 · 17 年前

template <unsigned N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
};

int main(void)
{
    std::cout << "Fibonacci(15) = ";
    std::cout << Fibonacci<15>::value;
    std::cout << std::endl;
}

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // ensure the table exists up to a certain size
    // (even though the rest of the code won't work)
    static const unsigned fibbMax = 20;
    Fibonacci<fibbMax>::value;

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << Fibonacci<fibb>::value;
    std::cout << std::endl;
}

fibb

在运行时查看此表的最佳方法是什么?最明显的解决方案(应该轻视“解决方案”)是使用一个大的switch语句:

unsigned fibonacci(unsigned index)
{
    switch (index)
    {
    case 0:
        return Fibonacci<0>::value;
    case 1:
        return Fibonacci<1>::value;
    case 2:
        return Fibonacci<2>::value;
    .
    .
    .
    case 20:
        return Fibonacci<20>::value;
    default:
        return fibonacci(index - 1) + fibonacci(index - 2);
    }
}

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    static const unsigned fibbMax = 20;    

    // get index into sequence
    unsigned fibb = std::rand() % fibbMax;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << fibonacci(fibb);
    std::cout << std::endl;
}

template <int TableSize = 40>
class FibonacciTable
{
public:
    enum
    {
        max = TableSize
    };

    static unsigned get(unsigned index)
    {
        if (index == TableSize)
        {
            return Fibonacci<TableSize>::value;
        }
        else
        {
            // too far, pass downwards
            return FibonacciTable<TableSize - 1>::get(index);
        }
    }
};

template <>
class FibonacciTable<0>
{
public:
    enum
    {
        max = 0
    };

    static unsigned get(unsigned)
    {
        // doesn't matter, no where else to go.
        // must be 0, or the original value was
        // not in table
        return 0;
    }
};

int main(void)
{
    std::srand(static_cast<unsigned>(std::time(0)));

    // get index into sequence
    unsigned fibb = std::rand() % FibonacciTable<>::max;

    std::cout << "Fibonacci(" << fibb << ") = ";
    std::cout << FibonacciTable<>::get(fibb);
    std::cout << std::endl;
}

7 回复 | 直到 6 年前

rlbond 16 年前

template <unsigned long N>
struct Fibonacci
{
    enum
    {
        value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<N-1>::add_values(v);
        v.push_back(value);
    }
};

template <>
struct Fibonacci<0>
{
    enum
    {
        value = 0
    };
    static void add_values(vector<unsigned long>& v)
    {
        v.push_back(value);
    }

};

template <>
struct Fibonacci<1>
{
    enum
    {
        value = 1
    };
    static void add_values(vector<unsigned long>& v)
    {
        Fibonacci<0>::add_values(v);
        v.push_back(value);
    }
};



int main()
{
    vector<unsigned long> fibonacci_seq;
    Fibonacci<45>::add_values(fibonacci_seq);
    for (int i = 0; i <= 45; ++i)
        cout << "F" << i << " is " << fibonacci_seq[i] << '\n';
}

顺便说一句,重要的是不要定义 Fibonacci<1> Fibonacci<0> 非常当它解析呼叫时感到困惑 Fibonacci<0>::add_values ,因为 斐波那契<0> 的模板专门化尚未指定。

Louis Go 4 年前

我知道这个问题很古老,但它引起了我的兴趣,我不得不尝试在运行时不填充动态容器:

#ifndef _FIBONACCI_HPP
#define _FIBONACCI_HPP


template <unsigned long N>
struct Fibonacci
{
    static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;
    
    static unsigned long long get_value(unsigned long n)
    {
        switch (n) {
            case N:
                return value;
            default:
                return n < N    ? Fibonacci<N-1>::get_value(n)
                                : get_value(n-2) + get_value(n-1);
        }
    }
};

template <>
struct Fibonacci<0>
{
    static const unsigned long long value = 0;
        
    static unsigned long long get_value(unsigned long n)
    {
        return value;
    }
};

template <>
struct Fibonacci<1>
{
    static const unsigned long long value = 1;

    static unsigned long get_value(unsigned long n)
    {
        if(n == N){
            return value;
        }else{
            return 0; // For `Fibonacci<N>::get(0);`
        }
    }
};

#endif

当这样使用时:

int main()
{
    std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n';
    std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n';
}

fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41)  Line 18 + 0xe bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43)  Line 18 + 0x2c bytes    C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45)  Line 18 + 0xe bytes    C++
fibtest.exe!main()  Line 9 + 0x7 bytes    C++
fibtest.exe!__tmainCRTStartup()  Line 597 + 0x17 bytes    C

即,它不断重复,直到在“表”中找到一个值。(通过逐行在调试器中逐步执行反汇编来验证,也可以通过将测试整数替换为<=45的随机数来验证)

static unsigned long long get_value(unsigned long n)
{
    switch (n) {
        case N:
            return value;    
        default:
            if (n < N) {
                return Fibonacci<N-1>::get_value(n);
            } else {
                // n > N
                unsigned long long i = Fibonacci<N-1>::value, j = value, t;
                for (unsigned long k = N; k < n; k++) {
                    t = i + j;
                    i = j;
                    j = t;
                }
                return j;
            }
    }
}

sigidagi 15 年前

如果你有支持可变模板(C++0x标准)的C++编译器,你可以在编译时将fibonacii序列保存在元组中。在运行时,您可以通过索引访问该元组中的任何元素。

#include <tuple>   
#include <iostream>

template<int N>
struct Fib
{
    enum { value = Fib<N-1>::value + Fib<N-2>::value };
};

template<>
struct Fib<1>
{
    enum { value = 1 };
};

template<>
struct Fib<0>
{
    enum { value = 0 };
};

// ----------------------
template<int N, typename Tuple, typename ... Types>
struct make_fibtuple_impl;

template<int N, typename ... Types>
struct make_fibtuple_impl<N, std::tuple<Types...> >
{
    typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type;
};

template<typename ... Types>
struct make_fibtuple_impl<0, std::tuple<Types...> >
{
    typedef std::tuple<Fib<0>, Types... > type;
};

template<int N>
struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> >
{};

int main()
{
   auto tup = typename make_fibtuple<25>::type();
   std::cout << std::get<20>(tup).value;  
   std::cout << std::endl; 

   return 0;
}

Jarod42 6 年前

使用C++11:你可以创建一个 std::array 以及一个简单的getter: https://ideone.com/F0b4D3

namespace detail
{

template <std::size_t N>
struct Fibo :
    std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value>
{
    static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value,
                  "overflow");
};

template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {};
template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {};

template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>(
        std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n];
}

template <std::size_t N>
constexpr std::size_t fibo(std::size_t n)
{
    return n < N ?
        fibo(n, make_index_sequence<N>()) :
        throw std::runtime_error("out of bound");
}
} // namespace detail

constexpr std::size_t fibo(std::size_t n)
{
    // 48u is the highest
    return detail::fibo<48u>(n);
}

在C++14中,你可以简化一些函数:

template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
    constexpr std::array<std::size_t, sizeof...(Is)> fibos{{Fibo<Is>::value...}};
    return fibos[n];
}

Zap 5 年前

我的想法是递归地将斐波那契序列保存在变量模板中,然后将其转换为数组。所有这些都是在编译时完成的。例如,当n=5时,我们有:

F<5>::array
= F<4, 0>::array
= F<3, 0, 1>::array
= F<2, 0, 1, 1>::array
= F<1, 0, 1, 1, 2>::array
= F<0, 0, 1, 1, 2, 3>::array
= { 0, 1, 1, 2, 3 }

然后我们可以在运行时对数组进行索引。

我的C++14实现:

#include <cstdint>
#include <array>
#include <iostream>


template<uint64_t n>
struct Helper { static constexpr uint64_t value = Helper<n - 1>::value + Helper<n - 2>::value; };

template<>
struct Helper<0> { static constexpr uint64_t value = 0; };

template<>
struct Helper<1> { static constexpr uint64_t value = 1; };


template<u_int64_t x>
class Fib {
private:
    template<u_int64_t n, u_int64_t...rest>
    struct Get {
        static constexpr std::array<u_int64_t, n + sizeof...(rest)> value = Get<n - 1, rest..., Helper<sizeof...(rest)>::value>::value;
    };

    template<u_int64_t...rest>
    struct Get<0, rest...> {
        static constexpr std::array<u_int64_t, sizeof...(rest)> value{rest...};
    };
public:
    static constexpr std::array<u_int64_t, x> sequence = Get<x>::value;
};

template<u_int64_t x>
constexpr std::array<u_int64_t, x> Fib<x>::sequence;


int main() {
    for (int i = 0; i < 45; i++) std::cout << "F" << i << " = " << Fib<45>::sequence[i] << std::endl;
}

James Caccese 17 年前

自动生成查找表并不是编译器需要为您做的事情。即使你需要这个功能,也不是每个人都需要。

jmihalicza 13 年前

您可以使用预处理器元编程技术生成开关或静态数组。如果复杂性不超过该方法的限制,并且您不希望通过生成代码或数据的额外步骤来扩展工具链,那么这是一个很好的决定。