替換爲模板元編程中的三元運算符

我正在C++中實現二項係數（n選擇k）函數。除了使用「正常」功能（其在運行時計算），這也可以實現使用模板元編程（當參數是在編譯時已知的）：替換爲模板元編程中的三元運算符

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = Binomialkoeffizient<n, k-1>::value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
};

這種實現的缺陷在於，它不使用定理n在k> n/2的情況下選擇k = n選擇nk。因此可能發生不必要的算術溢出49選43確實溢出，而49選6不。

我曾嘗試以下，以改善這一點：

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = (2*k > n) ? Binomialkoeffizient<n, n-k>::value : Binomialkoeffizient<n, k-1>::value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
};

不幸的是，我得到fatal error: template instantiation depth exceeds maximum of 900。

這似乎是由遞歸模板實例化過程中未評估三元運算符的事實引起的。

什麼是使用?:的可能替代方案？

我對pre-C++ 11解決方案和更新的解決方案很感興趣（也許std::enable_if有幫助，但我對此不太瞭解）。

來源

2017-07-28 Fabian

您是否嘗試過使用['std :: conditional']（http://en.cppreference.com/w/cpp/types/conditional）？ – NathanOliver

請您詳細說明一下嗎？我不確定如何正確使用它。它似乎也只適用於C++ 11以上。 – Fabian

@Fabian是的，它是C++ 11。第1步：使用'std :: conditional'在C++ 11中解決它。第2步：在C++ 03中編寫'my :: conditional'。第3步：利潤。 – Yakk

C++ 11引入的constexpr說明符，

...（這）聲明，它能夠評價在編譯時函數或變量的值。如果只允許編譯時間常量表達式（前提是給出了適當的函數參數），那麼可以使用這些變量和函數。在對象聲明中使用的constexpr 說明符暗示const。

（從http://en.cppreference.com/w/cpp/language/constexpr報價）

在實際應用中，可以實現這樣的功能：

template<class T> 
constexpr T binomial_coefficient(const T n, const T k) 
{ 
    if (2 * k > n) 
    { 
     return binomial_coefficient(n, n - k); 
    } 
    else 
    { 
     return k ? binomial_coefficient(n, k - 1) * (n - k + 1)/k : 1; 
    } 
}

，可以在編譯時進行評估。作爲一個例子，看看https://godbolt.org/g/b1MgFd其中該片段是由不同的編譯器和線路

constexpr auto value = binomial_coefficient(49, 43);

成爲

mov  eax, 13983816

來源

2017-07-28 23:04:37

我認爲'constexpr'函數中的多個語句正式添加到C++ 14中。 – Phil1970

@ Phil1970你是對的。在這種特殊情況下，通過使用單個返回與另一個條件操作符（而不是我使用的「if」）很容易解決。 –

感謝您的建議。我通過用'objdump'分解目標代碼來驗證它，並且實際上計算的值在文件中。有趣的是，立即使用該值而不事先賦值給變量，例如'std :: cout << binomial_coefficient（49,43）;'導致值不在編譯時計算。 – Fabian

與constexpr答案是做假設你使用的是最好的方式編譯現代C++編譯器。

但是，下面的代碼基本上是對代碼的改進，可以避免實例化太多的模板。實際上，據我所知，在你的例子中使用模板時，編譯器會生成所有處於三元表達式的模板，而不僅僅是所選的一面。

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient 
{ 
    static const unsigned int k2 = (2 * k > n) ? n - k : k; 
    static const unsigned int value = Binomialkoeffizient<n, k2 - 1>::value * (n - k2 + 1)/k2 ; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
};

通過定義k2我可以刪除一個額外的水平時2 * k > n是真實的。

如果您使用的是C++ 11編譯器，則可以用constexpr替換const。否則，使用未命名的enum可能更好，否則，編譯器仍可能爲每個實例級別的value成員保留內存。

來源

2017-07-29 14:11:57 Phil1970

感謝k2的好主意。正好在n = k的情況下，例如'Binomialkoeffizient <49, 49> :: value'你的程序不起作用，因爲它永遠實例化新模板直到達到極限。添加進一步spezialization'模板 struct Binomialkoeffizient { static const unsigned int value = 1; };'幫助。 – Fabian

經過一個晚上的睡眠，我想我得到了與std::conditional點。

編輯：正如@Yakk所提出的，我自己也實施了conditional。

此實現適用於所有C++標準：如何使代碼更簡潔或優雅

#if __cplusplus >= 201103L 
    // in C++11 and above we can use std::conditional which is defined in <type_traits> 
    #include <type_traits> 
    namespace my { 
     using std::conditional; 
    } 
#else 
    // in older C++ we have to use our own implementation of conditional 
    namespace my { 
     template <bool b, typename T, typename F> 
     struct conditional { 
      typedef T type; 
     }; 

     template <typename T, typename F> 
     struct conditional<false, T, F> { 
      typedef F type; 
     }; 
    } 
#endif 

template <unsigned int n, unsigned int k> 
struct Binomialkoeffizient { 
    static const unsigned int value = my::conditional< (2*k > n), Binomialkoeffizient<n, n-k>, Binomialkoeffizient<n, k> >::type::_value; 
    static const unsigned int _value = Binomialkoeffizient<n, k-1>::_value * (n-k+1)/k; 
}; 

template <unsigned int n> 
struct Binomialkoeffizient<n, 0> { 
    static const unsigned int value = 1; 
    static const unsigned int _value = 1; 
};

建議（？是不是真的需要使用第二靜態成員_value）的熱烈歡迎。

來源

2017-07-29 23:22:07 Fabian

替換爲模板元編程中的三元運算符

回答

相關問題