国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

C++模板元編程技術(shù)研究

2019-11-17 05:35:00
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

  摘要

  本文描述了模板元編程技術(shù)的起源、概念和機(jī)制,并介紹了模板元編程技術(shù)在Blitz++和Loki程序庫(kù)中的應(yīng)用。

  要害字

  編譯期計(jì)算 模板元編程 Blitz++ Loki

  導(dǎo)言

  1994年,C++標(biāo)準(zhǔn)委員會(huì)在圣迭哥舉行的一次會(huì)議期間Erwin Unruh展示了一段可以產(chǎn)生質(zhì)數(shù)的代碼。這段代碼的非凡之處在于質(zhì)數(shù)產(chǎn)生于編譯期而非運(yùn)行期,在編譯器產(chǎn)生的一系列錯(cuò)誤信息中間夾雜著從2到某個(gè)設(shè)定值之間的所有質(zhì)數(shù):

// PRime number computation by Erwin Unruh
template <int i> strUCt D { D(void*); Operator int(); };

template <int p, int i> struct is_prime {
enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
};

template < int i > struct Prime_print {
Prime_print<i-1> a;
enum { prim = is_prime<i, i-1>::prim };
void f() { D<i> d = prim; }
};

struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
Prime_print<LAST> a;
}
  類模板D只有一個(gè)參數(shù)為void*的構(gòu)造器,而只有0才能被合法轉(zhuǎn)換為void*。1994年,Erwin Unruh采用Metaware 編譯器編譯出錯(cuò)信息如下(以及其它一些信息,簡(jiǎn)短起見(jiàn),它們被刪除了):

Type `enum{}′ can′t be converted to tXPe `D<2>′ ("primes.cpp",L2/C25).
Type `enum{}′ can′t be converted to txpe `D<3>′ ("primes.cpp",L2/C25).
Type `enum{}′ can′t be converted to txpe `D<5>′ ("primes.cpp",L2/C25).
Type `enum{}′ can′t be converted to txpe `D<7>′ ("primes.cpp",L2/C25).
  如今,上面的代碼已經(jīng)不再是合法的C++程序了。以下是Erwin Unruh親手給出的修訂版,可以在今天符合標(biāo)準(zhǔn)的C++編譯器上進(jìn)行編譯:

// Prime number computation by Erwin Unruh

template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
enum { prim = (p==2) (p%i) && is_prime<(i>2?p:0), i-1> :: prim };
};

template <int i> struct Prime_print {
Prime_print<i-1> a;
enum { prim = is_prime<i, i-1>::prim };
void f() { D<i> d = prim ? 1 : 0; a.f();}
};

template<> struct is_prime<0,0> { enum {prim=1}; };
template<> struct is_prime<0,1> { enum {prim=1}; };

template<> struct Prime_print<1> {
enum {prim=0};
void f() { D<1> d = prim ? 1 : 0; };
};

#ifndef LAST
#define LAST 18
#endif

main() {
Prime_print<LAST> a;
a.f();
}
  在GNU C++ (MinGW Special) 3.2中編譯這段程序時(shí),編譯器將會(huì)給出如下出錯(cuò)信息(以及其它一些信息,簡(jiǎn)短起見(jiàn),它們被刪除了):

Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 17]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 13]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 11]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 7]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 5]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 3]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 2]'
  這個(gè)例子展示了可以利用模板實(shí)例化機(jī)制于編譯期執(zhí)行一些計(jì)算。這種通過(guò)模板實(shí)例化而執(zhí)行的非凡的編譯期計(jì)算技術(shù)即被稱為模板元編程。

  順便說(shuō)一句,因?yàn)榫幾g器的出錯(cuò)信息并未被標(biāo)準(zhǔn)化,所以,假如你在Visual C++、Borland C++等編譯器上看不到這么具體的出錯(cuò)信息,請(qǐng)不必訝異。
一個(gè)可以運(yùn)行的模板元編程例子

  模板元編程(Template Metaprogramming)更準(zhǔn)確的含義應(yīng)該是“編‘可以編程序的’程序”,而模板元程序(Template Metaprogram)則是“‘可以編程序的’程序”。也就是說(shuō),我們給出代碼的產(chǎn)生規(guī)則,編譯器在編譯期解釋這些規(guī)則并生成新代碼來(lái)實(shí)現(xiàn)我們預(yù)期的功能。

  Erwin Unruh的那段經(jīng)典代碼并沒(méi)有執(zhí)行,它只是以編譯出錯(cuò)信息的方式輸出中間計(jì)算結(jié)果。讓我們來(lái)看一個(gè)可以運(yùn)行的模板元編程例子 — 計(jì)算給定整數(shù)的指定次方:

// xy.h

//原始摸板
template<int Base, int Exponent>
class XY
{
public:
enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};

//用于終結(jié)遞歸的局部特化版
template<int Base>
class XY<Base, 0>
{
public:
enum { result_ = 1 };
};
  模板元編程技術(shù)之根本在于遞歸模板實(shí)例化。第一個(gè)模板實(shí)現(xiàn)了一般情況下的遞歸規(guī)則。當(dāng)用一對(duì)整數(shù)<X, Y>來(lái)實(shí)例化模板時(shí),模板XY<X, Y>需要計(jì)算其result_的值,將同一模板中針對(duì)<X, Y-1>實(shí)例化所得結(jié)果乘以X即可。第二個(gè)模板是一個(gè)局部特化版本,用于終結(jié)遞歸。

  讓我們看看使用此模板來(lái)計(jì)算5^4 (通過(guò)實(shí)例化XY<5, 4>)時(shí)發(fā)生了什么:

// xytest.cpp

#include <iostream>
#include "xy.h"

int main()
{
std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}
  首先,編譯器實(shí)例化XY<5, 4>,它的result_為5 * XY<5, 3>::result_,如此一來(lái),又需要針對(duì)<5, 3>實(shí)例化同樣的模板,后者又實(shí)例化XY<5, 2>…… 當(dāng)實(shí)例化到XY<5, 0>的時(shí)候,result_的值被計(jì)算為1,至此遞歸結(jié)束。

  遞歸模板實(shí)例化的深度和終結(jié)條件

  可以想象,假如我們以非常大的Y值來(lái)實(shí)例化類模板XY,那肯定會(huì)占用大量的編譯器資源甚至?xí)杆俸谋M可用資源(在計(jì)算結(jié)果溢出之前),因此,在實(shí)踐中我們應(yīng)該有節(jié)制地使用模板元編程技術(shù)。

  雖然 C++標(biāo)準(zhǔn)建議的最小實(shí)例化深度只有17層,然而大多數(shù)編譯器都能夠處理至少幾十層,有些編譯器答應(yīng)實(shí)例化至數(shù)百層,更有一些可達(dá)數(shù)千層,直至資源耗盡。

  假如我們拿掉XY模板局部特化版本,情況會(huì)如何?

// xy2.h

//原始摸板
template<int Base, int Exponent>
class XY
{
public:
enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};
  測(cè)試程序不變:

// xytest2.cpp

#include <iostream>
#include "xy2.h"

int main()
{
std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}
  執(zhí)行如下編譯命令:

C:/>g++ -c xytest2.cpp

  你將會(huì)看到遞歸實(shí)例化將一直進(jìn)行下去,直到達(dá)到編譯器的極限。

  GNU C++ (MinGW Special) 3.2的默認(rèn)實(shí)例化極限深度為500層,你也可以手工調(diào)整實(shí)例化深度:

C:/>g++ -ftemplate-depth-3400 -c xytest2.cpp

  事實(shí)上,就本例而言,g++ 3.2答應(yīng)的實(shí)例化極限深度還可以再大一些(我的測(cè)試結(jié)果是不超過(guò)3450層)。

  因此,在使用模板元編程技術(shù)時(shí),我們總是要給出原始模板的特化版(局部特化版或完全特化版或兼而有之),以作為遞歸模板實(shí)例化的終結(jié)準(zhǔn)則。 利用模板元編程技術(shù)解開循環(huán)

  模板元編程技術(shù)最早的實(shí)際應(yīng)用之一是用于數(shù)值計(jì)算中的解循環(huán)。舉個(gè)例子,對(duì)一個(gè)數(shù)組進(jìn)行求和的常見(jiàn)方法是:

// sumarray.h

template <typename T>
inline T sum_array(int Dim, T* a)
{
T result = T();
for (int i = 0; i < Dim; ++i)
{
result += a[i];
}
return result;
}
  這當(dāng)然可行,但我們也可以利用模板元編程技術(shù)來(lái)解開循環(huán):

// sumarray2.h

// 原始模板
template <int Dim, typename T>
class Sumarray
{
public:
static T result(T* a)
{
return a[0] + Sumarray<Dim-1, T>::result(a+1);
}
};

// 作為終結(jié)準(zhǔn)則的局部特化版
template <typename T>
class Sumarray<1, T>
{
public:
static T result(T* a)
{
return a[0];
}
};
  用法如下:


// sumarraytest2.cpp

#include <iostream>
#include "sumarray2.h"

int main()
{
int a[6] = {1, 2, 3, 4, 5, 6};
std::cout << " Sumarray<6>(a) = " << Sumarray<6, int>::result(a);
}
  當(dāng)我們計(jì)算Sumarray<6, int>::result(a)時(shí),實(shí)例化過(guò)程如下:

Sumarray<6, int>::result(a)
= a[0] + Sumvector<5, int>::result(a+1)
= a[0] + a[1] + Sumvector<4, int>::result(a+2)
= a[0] + a[1] + a[2] + Sumvector<3, int>::result(a+3)
= a[0] + a[1] + a[2] + a[3] + Sumvector<2, int>::result(a+4)
= a[0] + a[1] + a[2] + a[3] + a[4] + Sumvector<1, int>::result(a+5)
= a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
  可見(jiàn),循環(huán)被展開為a[0] + a[1] + a[2] + a[3] + a[4] + a[5]。這種直截了當(dāng)?shù)恼归_運(yùn)算幾乎總是比循環(huán)來(lái)得更有效率。

  也許拿一個(gè)有著600萬(wàn)個(gè)元素的數(shù)組來(lái)例證循環(huán)開解的優(yōu)勢(shì)可能更有說(shuō)服力。生成這樣的數(shù)組很輕易,有愛(ài)好,你不妨測(cè)試、對(duì)比一下。

  (感謝一位不知名的朋友的測(cè)試。他說(shuō):“據(jù)在Visual C++ 2003上實(shí)測(cè)編譯器應(yīng)當(dāng)進(jìn)行了尾遞歸優(yōu)化,可以不受上面說(shuō)的遞歸層次的限制,然而連加的結(jié)果在數(shù)組個(gè)數(shù)達(dá)到4796之后就不再正確了,程序輸出了空行,已經(jīng)出錯(cuò)” — 2003年12月30日補(bǔ)充) 模板元編程在數(shù)值計(jì)算程序庫(kù)中的應(yīng)用

  Blitz++之所以“快如閃電”(這正是blitz的字面含義),離不開模板元程序的功勞。Blitz++淋漓盡致地使用了元編程技術(shù),你可以到這些文件源代碼中窺探究竟:

dot.h

matassign.h

matmat.h

matvec.h

metaprog.h

product.h

sum.h

vecassign.h

  讓我們看看Blitz++程序庫(kù)dot.h文件中的模板元程序:

template<int N, int I>
class _bz_meta_vectorDot {
public:
enum { loopFlag = (I < N-1) ? 1 : 0 };

template<class T_expr1, class T_expr2>
static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
f(const T_expr1& a, const T_expr2& b)
{
return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
}

template<class T_expr1, class T_expr2>
static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
f_value_ref(T_expr1 a, const T_expr2& b)
{
return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
}

template<class T_expr1, class T_expr2>
static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
f_ref_value(const T_expr1& a, T_expr2 b)
{
return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
}

template<class T_expr1, class P_numtype2>
static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, P_numtype2)
dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
{
return a[I] * i1 + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::dotWithArgs
(a, i2, i3, i4, i5, i6, i7, i8, i9);
}
};

template<>
class _bz_meta_vectorDot<0,0> {
public:
template<class T_expr1, class T_expr2>
static inline _bz_meta_nullOperand f(const T_expr1&, const T_expr2&)
{ return _bz_meta_nullOperand(); }

template<class T_expr1, class P_numtype2>
static inline _bz_meta_nullOperand
dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
{
return _bz_meta_nullOperand();
}
};
  這段代碼遠(yuǎn)比它乍看上去的簡(jiǎn)單。_bz_meta_vectorDot類模板使用了一個(gè)臨時(shí)變量loopFlag來(lái)存放每一步循環(huán)條件的評(píng)估結(jié)果,并使用了一個(gè)完全特化版作為遞歸終結(jié)的條件。需要說(shuō)明的是,和幾乎所有元程序一樣,這個(gè)臨時(shí)變量作用發(fā)揮于編譯期,并將從運(yùn)行代碼中優(yōu)化掉。

  Todd是在Blitz++數(shù)值數(shù)組庫(kù)的主要作者。這個(gè)程序庫(kù)(以及MTL和POOMA等程序庫(kù))例證了模板元程序可以為我們帶來(lái)更加高效的數(shù)值計(jì)算性能。Todd宣稱Blitz++的性能可以和對(duì)應(yīng)的Fortran程序庫(kù)媲美。
Loki程序庫(kù):活用模板元編程技術(shù)的典范

  模板元編程的價(jià)值僅僅在于高性能數(shù)值計(jì)算嗎?不僅如此。Loki程序庫(kù)以對(duì)泛型模式的開創(chuàng)性工作聞名于C++社群。它很巧妙地利用了模板元編程技術(shù)實(shí)現(xiàn)了Typelist組件。Typelist是實(shí)現(xiàn)Abstract Factory、Visitor等泛型模式不可或缺的基礎(chǔ)設(shè)施。

  就像C++標(biāo)準(zhǔn)庫(kù)組件std::list提供對(duì)一組數(shù)值的操作一樣,Typelist可以用來(lái)操縱一組類型,其定義非常簡(jiǎn)單(摘自Loki程序庫(kù)Typelist.h單元):

template <class T, class U>
struct Typelist
{
typedef T Head;
typedef U Tail;
};
  顯然,Typelist沒(méi)有任何狀態(tài),也未定義任何操作,其作用只在于攜帶類型信息,它并未打算被實(shí)例化,因此,對(duì)于Typelist的任何處理都必然發(fā)生于編譯期而非運(yùn)行期。

  Typelist可以被無(wú)限擴(kuò)展,因?yàn)槟0鍏?shù)可以是任何類型(包括該模板的其他具現(xiàn)體)。例如:

  Typelist<char, Typelist<int, Typelist<float, NullType> > >

  就是一個(gè)包含有char、int、float三種類型的Typelist。

  按照Loki的約定,每一個(gè)Typelist都必須以NullType結(jié)尾。NullType的作用類似于傳統(tǒng)C字符串的“/0”,它被聲明于Loki程序庫(kù)的NullType.h文件中:

class NullType;

  NullType只有聲明,沒(méi)有定義,因?yàn)長(zhǎng)oki程序庫(kù)永遠(yuǎn)都不需要?jiǎng)?chuàng)建一個(gè)NullType對(duì)象。

  讓我們看看IndexOf模板元程序,它可以在一個(gè)Typelist中查找給定類型的位置(摘自Loki程序庫(kù)的Typelist.h單元):

template <class TList, class T>
struct IndexOf;

template <class T>
struct IndexOf<NullType, T>
{
enum { value = -1 };
};

template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
enum { value = 0 };
};

template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
enum { temp = IndexOf<Tail, T>::value };
public:
enum { value = (temp == -1 ? -1 : 1 + temp) };
};

  IndexOf提供了一個(gè)原始模板和三個(gè)局部特化版。算法非常簡(jiǎn)單:假如TList(就是一個(gè)Typelist)是一個(gè)NullType,則value為-1。假如TList的頭部就是T,則value為0。否則將IndexOf施行于TList的尾部和T,并將評(píng)估結(jié)果置于一個(gè)臨時(shí)變量temp中。假如temp為-1,則value為-1,否則value為1 + temp。

  為了加深你對(duì)Typelist采用的模板元編程技術(shù)的熟悉,我從Loki程序庫(kù)剝離出如下代碼,放入一個(gè)typelistlite.h文件中:

// typelistlite.h

// 聲明Nulltype
class NullType;

// Typelist的定義
template <class T, class U>
struct Typelist
{
typedef T Head;
typedef U Tail;
};

// IndexOf的定義

// IndexOf原始模板
template <class TList, class T> struct IndexOf;

// 針對(duì)NullType的局部特化版
template <class T>
struct IndexOf<NullType, T>
{
enum { value = -1 };
};

// 針對(duì)“Tlist頭部就是我們要查找的T”的局部特化版
template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
enum { value = 0 };
};

// 處理Tlist尾部的局部特化版
template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
enum { temp = IndexOf<Tail, T>::value };
public:
enum { value = (temp == -1 ? -1 : 1 + temp) };
};

  測(cè)試程序如下:

// typelistlite_test.cpp

#include <iostream>
#include "typelistlite.h"

// 自定義類型Royal
class Royal {};

// 定義一個(gè)包含有char、int、Royal和float的Typelist
typedef Typelist<char, Typelist<int, Typelist<Royal, Typelist<float, NullType> > > > CIRF;

int main()
{
std::cout << "IndexOf<CIRF, int>::value = " << IndexOf<CIRF, int>::value << "/n";
std::cout << "IndexOf<CIRF, Royal>::value = " << IndexOf<CIRF, Royal>::value << "/n";
std::cout << "IndexOf<CIRF, double>::value = " << IndexOf<CIRF, double>::value << "/n";
}

  程序輸出如下:


IndexOf<CIRF, int>::value = 1
IndexOf<CIRF, Royal>::value = 2
IndexOf<CIRF, double>::value = -1
  結(jié)束語(yǔ)

  模板元編程技術(shù)并非都是優(yōu)點(diǎn),比方說(shuō),模板元程序編譯耗時(shí),帶有模板元程序的程序生成的代碼尺寸要比普通程序的大,而且通常這種程序調(diào)試起來(lái)也比常規(guī)程序困難得多。另外,對(duì)于一些程序員來(lái)說(shuō),以類模板的方式描述算法也許有點(diǎn)抽象。

  編譯耗時(shí)的代價(jià)換來(lái)的是卓越的運(yùn)行期性能。通常來(lái)說(shuō),一個(gè)有意義的程序的運(yùn)行次數(shù)(或服役時(shí)間)總是遠(yuǎn)遠(yuǎn)超過(guò)編譯次數(shù)(或編譯時(shí)間)。為程序的用戶帶來(lái)更好的體驗(yàn),或者為性能要求嚴(yán)格的數(shù)值計(jì)算換取更高的性能,值得程序員付出這樣的代價(jià)。

  很難想象模板元編程技術(shù)會(huì)成為每一個(gè)普通程序員的日常工具,相反,就像Blitz++和Loki那樣,模板元程序幾乎總是應(yīng)該被封裝在一個(gè)程序庫(kù)的內(nèi)部。對(duì)于庫(kù)的用戶來(lái)說(shuō),它應(yīng)該是透明的。模板元程序可以(也應(yīng)該)用作常規(guī)模板代碼的內(nèi)核,為要害的算法實(shí)現(xiàn)更好的性能,或者為非凡的目的實(shí)現(xiàn)非凡的效果。

  模板元編程技術(shù)首次正式亮相于Todd Veldhuizen的Using C++ Template Metaprograms論文之中。這篇文章首先發(fā)表于1995年5月的C++ Report期刊上,后來(lái)Stanley Lippman編輯C++ Gems一書時(shí)又收錄了它。參考文獻(xiàn)中給出了這篇文章的鏈接,它還描述了許多本文沒(méi)有描述到的內(nèi)容。

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 盈江县| 三门峡市| 武汉市| 新安县| 油尖旺区| 治县。| 崇礼县| 遂溪县| 达拉特旗| 资兴市| 西峡县| 和静县| 文水县| 铁岭市| 上虞市| 安泽县| 蛟河市| 新丰县| 西华县| 遵化市| 中江县| 基隆市| 正蓝旗| 桑植县| 隆安县| 黔西| 河南省| 当阳市| 吉水县| 留坝县| 左云县| 灌南县| 成武县| 武乡县| 夹江县| 清流县| 新丰县| 开阳县| 汉中市| 伊通| 宝清县|