第九十三讲 模板递归

昨天给大家提了一个问题,大家都知道,在C++的世界解决问题之道可以说是五花八门,只要你想得到,就能够做得到,但是不管方法有多少,总有那么几个方法是公认可取的,现在让我们来一个问题,一个求阶乘的问题。

//============================
unsigned fac(unsigned n){

if (n == 0)

return 1;


return n*fac(n – 1);


}
==============================
通常我们会这样来解决这个问题,简单,直接,了当,所以,这通常成为大家计算阶乘的首选,而且,在对效率不吹毛求疵的情况下,这是可以接受的,那么有没有更加高效的办法来解决这个效率问题呢?ok,我们可以将运行期提前到编译器完成计算,不过看上去可能会比较难看一些:

//================================
template<size_t N>
class Fac{
public:

static const size_t value = N*Fac<N – 1>::value;


};

template<>
class Fac<0>{
public:

static const size_t value = 1;


};



=================================

int main(){

cout<<Fac<10>::value<<endl;


return 0;


}

//将会打印3628800
================================
==

其实这看上也很简单,清晰,明了,更重要的是他所有的计算都在编译器完成,所以在效率方面,这是无可匹敌的,ok,我们再来看一个复杂点的:
//================================
template<size_t N,typename Fun>
class Bynary{
public:

static inline
void Func(Fun fun){

Bynary<N/2, Fun>::Func(fun);


fun(N);


}
};

template<typename Fun>
class Bynary<0, Fun>{
public:

static inline
void Func(Fun fun){ };


};


================================
这是一个将十进制数转换为二进制数的程序,他能够执行一个回调函数,这个回调函数只是简单的做些辅助工作:

//==============================


void bynary(size_t n){

cout<<n%2;


}

int main(){

Bynary<10, decltype(bynary)>::Func(bynary);


return 0;


}
//打印1010
================================

ok,现在大家应该看出来了吧,我们这里使用的就是递归技术,所以,大家也看到了我们使用了两个模板,一个特化的是用来作为终止递归使用的,从这两个例子,我们也看出了一些使用递归技巧的端倪,现在我们可以回头去看看昨天给大家留下的问题,首先模板我就不说了,我直接给大家演示使用模板递归来解决问题:

//==============================
template<typename T,size_t N>
class NDimension{

static const size_t kDefaultSize = 10;


public:

NDimension():m_Size(kDefaultSize){

m_Value = new NDimension<T, N – 1>[kDefaultSize];


}

NDimension(size_t size) :m_Size(size){

m_Value = new NDimension<T, N – 1>[size];


for (size_t i = 0;

i <size;

++i){

m_Value[i].resize(size);


}

}

NDimension(const NDimension<T, N>&

src){

copySrc(src);


}

virtual ~NDimension(){

delete[] m_Value;


m_Value = nullptr;


}

NDimension&

operator=(const NDimension<T, N>&

src){

if (*this == src)

return *this;


delete[] m_Value;


m_Value = nullptr;


copySrc(src);


return *this;


}

void resize(size_t newSize){

NDimension<T, N – 1>* newValue = new NDimension<T, N – 1>[newSize];


for (size_t i = 0;

i <newSize &

&

i <m_Size;

++i){

newValue[i] = m_Value[i];


newValue[i].resize(newSize);


}

m_Size = newSize;


delete[] m_Value;


m_Value = newValue;


}

NDimension<T, N – 1>&

operator[](size_t index){

return m_Value[index];


}

const NDimension<T, N – 1>&

operator[](size_t index) const{

return m_Value[index];


}

size_t getSize() const{

return m_Size;


}

friend ostream&

operator<<(ostream&

os, const NDimension<T,N>&

nd){

for (size_t i = 0;

i <nd.m_Size;

++i){

os <<nd.m_Value[i] <<"

"

;


}

return os;


}

private:

void copySrc(const NDimension<T, N>&

src){

m_Size = src.m_Size;


m_Value = new NDimension<T, N – 1>[src.m_Size];


for (size_t i = 0;

i <src.m_Size;

++i){

m_Value[i] = src.m_Value[i];


}

}

NDimension<T, N – 1>* m_Value;



size_t

m_Size;


};



//================================
template<typename T>
class NDimension<T, 1>{

static const size_t kDefaultSize = 10;


public:

NDimension(size_t size = kDefaultSize) :m_Size(size){

m_Value = new T[size];


}

NDimension(const NDimension<T, 1>&

src){

copySrc(src);


}

virtual ~NDimension(){

delete m_Value;


m_Value = nullptr;


}

NDimension&

operator=(const NDimension<T, 1>&

src){

if (*this == src)

return *this;


delete m_Value;


m_Value = nullptr;


copySrc(src);


return *this;


}

void resize(size_t size){

T* newValue = new T[size];


for (size_t i = 0;

i <size &

&

i <m_Size;

++i){

newValue[i] = m_Value[i];


}

delete m_Value;


m_Value = newValue;


}

T&

operator[](size_t index){

return m_Value[index];


}

const T&

operator[](size_t index) const{

return m_Value[index];


}

size_t getSize() const{

return m_Size;


}

friend ostream&

operator<<(ostream&

os, const NDimension<T, 1>&

nd){

for (size_t i = 0;

i <nd.m_Size;

++i){

os <<nd.m_Value[i] <<"

"

;


}

return os;


}
private:

void copySrc(const NDimension<T, 1>&

src){

m_Size = src.m_Size;


m_Value = new T[src.m_Size];


for (size_t i = 0;

i <src.m_Size;

++i){

m_Value[i] = src.m_Value[i];


}

}

size_t
m_Size;



T*

m_Value;


};



=====================================

就这么简单,如果你看懂了的话,其实重要是理解,理解了其中的原理一切就明了了,那么现在带来什么样的便捷呢?当我们使用的时候我们可以简单的用数字指定空间维数,就比如我们想要模拟一个信号在三维空间的分布,那么我们可以这样来定义:

//==========================
NDimension<double,3>signal(1000);


cout<<signal<<endl;


============================

现在看上去是不是清晰了很多了呢?就算是100维空间,我们只需要将N指定为100就好。

这一讲的内容有些新鲜,也有些深度,这是学习模板元的基础,当然,模板元太过高深了些,如果不是搞一些高深的数学研究的话,对于C++模板,我们只要能够理解到上面这般成都也就足够,当然,如果你们有研究精神,可以继续深入,这里推荐大家一本书《C++模板元编程》,因为说实在的,偶尔翻起这本书,总是看得头晕脑胀,还是算了,对于模板编程,我也就直到这种程度,至于模板的模板参数,这也是一个很有用的知识点(大家都知道,C++学到最后其实都是模板编程,所以模板的模板参数是实现泛型的一个重要知识点,如果我们只是像寻常的一样使用C++而不打算尝试去编写一些真正的泛型模板的话,目前我们的知识足够了),接下来可能会有些忙,所以可能接下来的几天无法给大家推送C++了,不过,等有时间了,再来和大家谈谈模板的模板参数。

============================
回复D或者d直接查看目录,回复相应的数字查看对应章节

原文始发于微信公众号(

C/C++的编程教室

):第九十三讲
模板递归

|

发表评论