微信号:gh_5f9337df4e69

介绍:讨论和学习C/C++的编程知识

第九十三讲 模板递归

2014-10-06 14:14 零灵柒

昨天给大家提了一个问题,大家都知道,在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++的编程教室 更多文章 写在开篇 第一讲 Hello World 第二讲 printf()(1) 第三讲 printf()(2) 第四讲 scanf()
猜您喜欢 大猫的R语言课堂开课啦+次回预告 『独家干货 』Android应用函数级性能分析方案 网络IP疯狂背后:如何编出一部讨喜作品?┃企鹅智酷 大型企业注意了!某安全公司多个产品线存在严重漏洞 你好,bot!