值元編程（Value Metaprogramming）
template<int N>
struct Fac {
enum { value = N * Fac<N - 1>::value };
};
template<>
struct Fac<0> {
enum { value = 1 };
};
static_assert(Fac<5>::value == 120);
- C++98 允許在類內(nèi)部初始化 static int 常量
template<int N>
struct Fac {
static const int value = N * Fac<N - 1>::value;
};
template<>
struct Fac<0> {
static const int value = 1;
};
static_assert(Fac<5>::value == 120);
- Modern C++ 中可以使用 constexpr虑粥，且不再局限于int
template<int N>
struct Fac {
static constexpr auto value = N * Fac<N - 1>::value;
};
template<>
struct Fac<0> {
static constexpr auto value = 1;
};
static_assert(Fac<5>::value == 120);
- 但類內(nèi)初始化 static 成員存在一個(gè)問題，如果把結(jié)果按引用傳遞給函數(shù)
void f(const int&) {}
f(Fac<5>::value);
- 由于函數(shù)參數(shù)是引用類型，編譯器必須傳遞
Fac<5>::value 的地址，而調(diào)用 f(Fac<5>::value) 必須類外定義 static 數(shù)據(jù)成員（ODR-use）。enum 沒有地址钙畔，不會(huì)有這個(gè)問題绑莺，因此早期一般偏向使用 enum
- C++17 引入的 inline 成員變量允許多于一次定義蔓姚，解決了上述函數(shù)調(diào)用的地址問題。C++17中幸海，constexpr static 成員默認(rèn) inline
template<int N>
struct Fac {
static inline constexpr auto value = N * Fac<N - 1>::value;
};
template<>
struct Fac<0> {
static inline constexpr auto value = 1;
};
void f(const int&) {}
f(Fac<5>::value); // OK
- C++14 的 constexpr 函數(shù)簡化了元編程的寫法祟身，用二分查找計(jì)算平方根的元編程實(shí)現(xiàn)是
template <int N, int L = 1, int R = N>
struct Sqrt {
static constexpr auto M = L + (R - L) / 2;
static constexpr auto T = N / M;
static constexpr auto value =
(T < M) ? Sqrt<N, L, M>::value : Sqrt<N, M + 1, R>::value;
};
template <int N, int M>
struct Sqrt<N, M, M> { // 終止條件為 L == R
static constexpr auto value = M - 1;
};
static_assert(Sqrt<10000>::value == 100);
- C++14 的 constexpr 函數(shù)對(duì)相同功能的實(shí)現(xiàn)是
constexpr int Sqrt(T x) {
if (x <= 1) return x;
int l = 1;
int r = x;
while (l < r) {
int m = l + (r - l) / 2;
int t = x / m;
if (m == t) {
return m;
} else if (m > t) {
r = m;
} else {
l = m + 1;
}
}
return l - 1;
}
static_assert(Sqrt(10000) == 100);
遞歸實(shí)例化的開銷
- 下面是
Sqrt<10000>::value 的計(jì)算過程
Sqrt<10000, 1, 10000>::value => [M, T] = [5000, 2]
Sqrt<10000, 1, 5000>::value => [M, T] = [2500, 4]
Sqrt<10000, 1, 2500>::value => [M, T] = [1250, 8]
Sqrt<10000, 1, 1250>::value => [M, T] = [625, 16]
Sqrt<10000, 1, 625>::value => [M, T] = [313, 31]
Sqrt<10000, 1, 338>::value => [M, T] = [157, 63]
Sqrt<10000, 1, 157>::value => [M, T] = [79, 126]
Sqrt<10000, 80, 157>::value => [M, T] = [118, 84]
Sqrt<10000, 80, 118>::value => [M, T] = [99, 101]
Sqrt<10000, 100, 118>::value => [M, T] = [109, 91]
Sqrt<10000, 100, 109>::value => [M, T] = [104, 96]
Sqrt<10000, 100, 104>::value => [M, T] = [102, 98]
Sqrt<10000, 100, 102>::value => [M, T] = [101, 99]
Sqrt<10000, 100, 101>::value => [M, T] = [100, 100]
Sqrt<10000, 101, 101>::value => 100
- 但編譯器計(jì)算下列表達(dá)式時(shí)奥务，將實(shí)例化所有分支
Sqrt<10000, 1, 10000>::value => [M, T] = [5000, 2]
(2 < 5000) ? Sqrt<10000, 1, 5000>::value : Sqrt<10000,5001,10000>::value
- 整個(gè)計(jì)算過程產(chǎn)生了大量實(shí)例化，數(shù)量幾乎是 N 的兩倍袜硫。使用 IfThenElse 可以避免此問題氯葬，實(shí)例化數(shù)量級(jí)將降低為
log2(N)
template <bool COND, typename TrueType, typename FalseType>
struct IfThenElseT {
using Type = TrueType;
};
template <typename TrueType, typename FalseType>
struct IfThenElseT<false, TrueType, FalseType> {
using Type = FalseType;
};
template <bool COND, typename TrueType, typename FalseType>
using IfThenElse = typename IfThenElseT<COND, TrueType, FalseType>::Type;
template <int N, int L = 1, int R = N>
struct Sqrt {
static constexpr auto M = L + (R - L) / 2;
static constexpr auto T = N / M;
static constexpr auto value =
IfThenElse<(T < M), Sqrt<N, L, M>, Sqrt<N, M + 1, R>>::value;
};
template <int N, int M>
struct Sqrt<N, M, M> {
static constexpr auto value = M - 1;
};
static_assert(Sqrt<10000>::value == 100);
- 實(shí)際上直接使用 constexpr 函數(shù)是最簡單高效的做法
計(jì)算完整性（Computational Completeness）
- 上述例子說明一個(gè)模板元編程一般包含以下部分
- 狀態(tài)變量：即模板參數(shù)
- 迭代構(gòu)造：通過遞歸
- 路徑選擇：通過條件表達(dá)式或特化
- 整型算法
- 如果對(duì)遞歸實(shí)例化體和狀態(tài)變量的數(shù)量沒有限制，元編程就可以在編譯期對(duì)任何可計(jì)算對(duì)象進(jìn)行高效計(jì)算婉陷。但標(biāo)準(zhǔn)建議最多進(jìn)行 1024 層遞歸實(shí)例化帚称，因此實(shí)際開發(fā)中要有節(jié)制地使用模板元編程。某些情況下模板元編程是一個(gè)重要工具秽澳，尤其是實(shí)現(xiàn)一些對(duì)性能要求嚴(yán)格的算法
遞歸實(shí)例化與遞歸模板實(shí)參
template <typename T, typename U>
struct Doublify {};
template <int N>
struct Trouble {
using LongType = Doublify<typename Trouble<N - 1>::LongType,
typename Trouble<N - 1>::LongType>;
};
template <>
struct Trouble<0> {
using LongType = double;
};
Trouble<10>::LongType ouch;
- 對(duì)于表達(dá)式
Trouble<N>::LongType 的類型描述闯睹，隨著遞歸層次的增加，代碼將越來越長担神，復(fù)雜度與 2^N 成正比
// Trouble<0>::LongType
double
// Trouble<1>::LongType
Doublify<double, double>
// Trouble<2>::LongType
Doublify<Doublify<double, double>, Doublify<double, double>>
- 使用遞歸模板實(shí)參會(huì)強(qiáng)制編譯器生成更多的實(shí)例化體楼吃，編譯器要為每個(gè)類型保存一個(gè) mangled name，早期編譯器中 mangled name 的長度一般等于 template-id 的長度杏瞻，于是
Trouble<10>::LongType 可能產(chǎn)生一個(gè)長度大于 10000 個(gè)字符的 managled name所刀，雖然現(xiàn)在的編譯器使用了智能壓縮技術(shù)，可以將 Trouble<10>::LongType 壓縮到幾百個(gè)字符捞挥，但最好避免在模板實(shí)參中遞歸實(shí)例化
類型元編程（Type Metaprogramming）
- 以前討論過的 traits 只能進(jìn)行簡單的類型計(jì)算，通過元編程可以進(jìn)行更復(fù)雜的類型計(jì)算
template <typename T>
struct sp_element {
using type = T;
};
template <typename T>
struct sp_element<T[]> {
using type = typename sp_element<T>::type;
};
template <typename T, std::size_t N>
struct sp_element<T[N]> {
using type = typename sp_element<T>::type;
};
template<typename T>
using sp_element_t = typename sp_element<T>::type;
static_assert(std::is_same_v<sp_element_t<int[]>, int>);
static_assert(std::is_same_v<sp_element_t<int[5][10]>, int>);
static_assert(std::is_same_v<sp_element_t<int[][10]>, int>);
static_assert(std::is_same_v<sp_element_t<int(*)[5]>, int(*)[5]>);
template <class T, T v>
struct integral_constant {
static constexpr T value = v;
using value_type = T;
using type = integral_constant; // using injected-class-name
constexpr operator value_type() const noexcept { return value; }
constexpr value_type operator()() const noexcept { return value; }
};
template <class T, T v>
struct A {
static constexpr T value = v;
};
template <int N, int... Ns>
struct Max;
template <int N>
struct Max<N> : A<int, N> {};
template <int N1, int N2, int... Ns>
struct Max<N1, N2, Ns...> : A <int,
N1 < N2 ? Max<N2, Ns...>::value : Max<N1, Ns...>::value> {};
template <int... Ns>
constexpr auto max_v = Max<Ns...>::value;
static_assert(max_v<3, 2, 1, 5, 4> == 5);
混合元編程（Hybrid Metaprogramming）
- 在編譯期以編程的方式匯編小片帶運(yùn)行期效率的代碼稱為混合元編程。比如計(jì)算兩個(gè)數(shù)組的點(diǎn)積
template <typename T, std::size_t N>
auto dotProduct(const std::array<T, N>& a, const std::array<T, N>& b) {
T res{};
for (std::size_t i = 0; i < N; ++i) {
res += a[i] * b[i];
}
return res;
}
- 在一些機(jī)器上溜族，for 循環(huán)的匯編將產(chǎn)生分支指令讹俊，可能比直接寫出循環(huán)造成更大的開銷
res += x[0]*y[0];
res += x[1]*y[1];
res += x[2]*y[2];
res += x[3]*y[3];
- 不過現(xiàn)代編譯器將優(yōu)化循環(huán)為目標(biāo)平臺(tái)最高效形式。使用元編程可以展開循環(huán)煌抒，雖然現(xiàn)在已經(jīng)沒有這個(gè)必要仍劈，但出于討論還是給出實(shí)現(xiàn)
template <typename T, std::size_t N>
struct DotProductT {
static inline T value(const T* a, const T* b) {
return *a * *b + DotProductT<T, N - 1>::value(a + 1, b + 1);
}
};
template <typename T>
struct DotProductT<T, 0> {
static inline T value(const T*, const T*) { return T{}; }
};
template <typename T, std::size_t N>
auto dotProduct(const std::array<T, N>& x, const std::array<T, N>& y) {
return DotProductT<T, N>::value(&*begin(x), &*begin(y));
}
std::tuple<int, std::string, bool> t{42, "Answer", true};
- 一些庫用來計(jì)算不同 unit type 值結(jié)果贩疙，也體現(xiàn)了混合元編程的能力
- 以時(shí)間為例，主要的 unit 是秒况既，一毫秒就可以用 1/1000 來表示这溅，一分鐘則用 60/1 表示，為此先定義一個(gè)用于表示 unit 比值的類型 Ratio
#include <iostream>
template <unsigned N, unsigned D = 1>
struct Ratio {
static constexpr unsigned num = N; // 分子
static constexpr unsigned den = D; // 分母
using Type = Ratio<num, den>;
};
template <typename R1, typename R2>
struct RatioAddImpl {
private:
static constexpr unsigned den = R1::den * R2::den;
static constexpr unsigned num = R1::num * R2::den + R2::num * R1::den;
public:
using Type = Ratio<num, den>;
};
template <typename R1, typename R2>
using RatioAdd = typename RatioAddImpl<R1, R2>::Type;
int main() {
using R1 = Ratio<1, 1000>;
using R2 = Ratio<2, 3>;
using RS = RatioAdd<R1, R2>; // Ratio<2003,3000>
std::cout << RS::num << '/' << RS::den << '\n'; // 2003/3000
using RA = RatioAdd<Ratio<2, 3>, Ratio<5, 7>>; // Ratio<29,21>
std::cout << RA::num << '/' << RA::den << '\n'; // 29/21
}
- 基于此模板可以定義一個(gè)表示時(shí)間的類模板
#include <iostream>
template <unsigned N, unsigned D = 1>
struct Ratio {
static constexpr unsigned num = N; // 分子
static constexpr unsigned den = D; // 分母
using Type = Ratio<num, den>;
};
template <typename R1, typename R2>
struct RatioAddImpl {
private:
static constexpr unsigned den = R1::den * R2::den;
static constexpr unsigned num = R1::num * R2::den + R2::num * R1::den;
public:
using Type = Ratio<num, den>;
};
template <typename R1, typename R2>
using RatioAdd = typename RatioAddImpl<R1, R2>::Type;
template <typename T, typename U = Ratio<1>>
class Duration {
public:
using ValueType = T;
using UnitType = typename U::Type; // 時(shí)間的基本單位
private:
ValueType val;
public:
constexpr Duration(ValueType v = 0) : val(v) {}
constexpr ValueType value() const { return val; }
};
template <typename T1, typename U1, typename T2, typename U2>
constexpr auto operator+(const Duration<T1, U1>& a, const Duration<T2, U2>& b) {
using VT = Ratio<1, RatioAdd<U1, U2>::den>; // Ratio<1, U1::den * U2::den>
auto res =
(a.value() * U1::num / U1::den + b.value() * U2::num / U2::den) * VT::den;
return Duration<decltype(res), VT>{res};
}
int main() {
auto a = Duration<int, Ratio<1, 1000>>(10); // 10 毫秒
auto b = Duration<double, Ratio<1, 3>>(7.5); // 2.5 秒
auto c = a + b; // c = 10 * 3 + 7.5 * 1000 = 7530 * 1/3000 秒
using Type = decltype(c)::UnitType;
std::cout << c.value() << "*" << Type::num << '/' << Type::den;
}
#include <iostream>
#include <chrono>
constexpr std::chrono::seconds operator ""s(unsigned long long s) {
return std::chrono::seconds(s);
}
constexpr std::chrono::minutes operator ""min(unsigned long long m) {
return std::chrono::minutes(m);
}
constexpr std::chrono::hours operator ""h(unsigned long long h) {
return std::chrono::hours(h);
}
int main() {
using namespace std::chrono_literals;
std::cout << (1h + 1min + 30s).count(); // 3690
}
反射
- 模板元編程的方案選擇必須從三個(gè)角度考慮：
- Computation（計(jì)算）
- Reflection（反射）：以編程方式檢查程序特征的能力
- Generation（生成）：為程序生成附加代碼的能力
- 前面提到了遞歸實(shí)例化和 constexpr 函數(shù)兩種方案。為了進(jìn)行反射浇揩，type traits 中可以找到部分解決方案仪壮，但遠(yuǎn)不能覆蓋反射所需的全部內(nèi)容。比如給定一個(gè)類類型临燃，許多應(yīng)用程序都希望以編程方式探索該類的成員【Σ担現(xiàn)有的 traits 基于模板實(shí)例化，因此 C++ 可以提供附加的語言能力或內(nèi)在庫組件膜廊，在編譯期生成包含反射信息的類模板實(shí)例乏沸。這是匹配基于遞歸模板實(shí)例化的方案，但類模板實(shí)例會(huì)消耗大量編譯器空間爪瓜，直到編譯結(jié)束時(shí)才能釋放蹬跃。另一種與 constexpr 計(jì)算匹配的方案是引入一種新的標(biāo)準(zhǔn)類型來表示反射信息
- 在 C++ 中創(chuàng)建一個(gè)靈活的、通用的和程序員友好的代碼生成機(jī)制仍是各方正在研究的挑戰(zhàn)铆铆，但模板實(shí)例化也勉強(qiáng)算是一種代碼生成機(jī)制蝶缀，此外，編譯器擴(kuò)展內(nèi)聯(lián)函數(shù)的調(diào)用已經(jīng)足夠可靠薄货，該機(jī)制也可以用作代碼生成的工具翁都。結(jié)合更強(qiáng)大的反射能力，現(xiàn)有技術(shù)已能實(shí)現(xiàn)卓越的元編程效果
