Jump Out of C++:面向对象编程探索(二)

这次是这一个系列技术分享的第二部分,主要介绍的是C++对象模型。这里所讲的对象模型,是指如何在内存中(空间上)表达对象的性质和特征,以及如何在运行时(时间上)提供完成面向对象系统中的必要操作的能力。

Table of Content


C++并不是天生地庞大而迟缓

—— Stanley B. Lippman

  1. 概述
  2. 对象的内存布局
  3. 运行期环境

1. 概述


对于传统的C语言程序来讲,数据与算法是分离的:

struct Circle  
{ 
int x, y;  
int radius;  
}; 

Circle MakeCircle(int x, int y, int radius) { //.... } void DrawCircle(Circle c) { //.... }  

在C++中,将这样的与传统C语言结构体内存布局兼容的对象叫做Plain Old Data(POD)。

此外,我们还可以将数据和算法整合在一起:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
private:  
    int x, y; 
    int radius; 
};

对于这样的代码,在时空上是否增加了什么负担?同时,C++还支持继承、多重继承等很多机制,它们呢?

class Point {  
public:  
    Point(int x, int y); 
private:  
    int x, y; 
}; 
class Circle : public Point { //... };  

我们先从最朴素的模型开始,看一看如何来安排对象的内存空间:

  • 简单对象模型

在简单对象模型中,对象中只存储指向成员(包括数据成员和方法成员)的指针,所有操作均通过指针索引来完成。

  • (双)表格驱动模型

双表格驱动模型是指在对象中仅存储两个指针:一个指向数据成员table的指针,一个指向方法成员table的指针。这种模型的优点在于所有对象的内存空间占用及内存布局均完全一致。早期的某款C++编译器采用了这一种模型。

以上两种模型都是可以在一定程度上满足需求的,但并未被大多数编译器所采用。目前主流的模型如下:

  • 非静态数据存放于对象内部
  • 静态数据、非virtual函数存放于对象之外
  • 每一个class至少有一张虚函数表
  • 每一个object中包含一个指向该表的指针

1

本文将探讨在单继承、多继承、虚拟继承下C++对象模型是如何应对的。

2. 对象的内存布局


 2.1 类

对于如下的代码来说:

class Circle  
{ 
public:  
    Circle(int x, int y, int radius); 
    void Draw(); 
    static void Print(); 
private:  
    int x, y; 
    int radius; 
    static int count;
};

根据前述的对象模型,其其布局与在C语言中使用结构体时是一致的:

circle

同时C++标准保证,在同一个权限声明块中(即同一个public、protected或private块中),后声明的成员在内存中位于高地址(更靠后)。但并没有规定其一定紧邻,其间可以插入其他编译器所需的数据。

 2.2 不包含虚函数的单继承

而对于单继承来说:

class Point  
{ 
public:  
    Point(int x, int y); 
protected:  
    int x, y; 
}; 
class Circle : public Point { protected: int radius; };  

其内存布局如下:

绘图7

可以看出,其占用内存的成本并没有增加。然而是否一定不会增加呢?如果我们有如下代码:

class Point {  
public:  
    //... 
protected:  
    int x, y; 
    char c1, c2; 
}; 
class Circle : public Point {  
public:  
//... 
protected:  
    char c3, c4; 
    int radius; 
};

此时的内存布局将为:

绘图7_

由于需要对其内存,编译器很可能会插入padding字节。这时,继承的内存占用将会比数据全部在同一个类中的时候大。不过,我们是否可以取消掉padding呢?

答案自然是否定的。取消padding后,Point对象和Circle对象中Point部分在内存中占用的大小将会不同,此时如果存在以下代码:

void some_func(Point* point) { Point a; *point = a; }  

由于Circle和Point存在继承关系,我们不能在编译期确定代码中point的真实类型是什么。如果point一旦为Circle类型,那么在执行到*point=a这一句代码时,将会多覆盖两个字节的内存,即c3和c4将被内容不确定的内存覆盖。

2.3 包含虚函数的单继承

对于包含虚函数的单继承来说,其内存中将会增加一个指向虚表的指针。

class Point {  
public:  
    virtual void Print(); 
protected:  
    int x, y; 
}; 
class Circle {  
public:  
    virtual void Print();
protected:  
   int radius; 
};

circle<em data-recalc-dims=withpoly” title=”” />

需要说明的是,虚表指针_vptr可以在Point中的任意位置。上图中其位于Point对象的末尾,也可以位于最前,甚至在中间也可以。在末尾的好处在于其前面的部分仍然与C语言结构体兼容,在最前的好处是可以省去一步计算过程(对象的地址即为虚表指针的位置,不需要额外的计算)。而一般来讲没有编译器选择在中间位置插入虚表指针。

对于一个Point对象来讲,其vptr将指向Point类的虚表;而对于一个Circle对象来讲,虽然图中标明了vptr在Point部分中,但这仅表明它是由Point继承而来,其仍将指向Circle类的虚表,如下图所示:

circle<em data-recalc-dims=withpoly_2″ title=”” />

2.4 包含虚函数的多重继承

假如有如下代码:

class Point {  
public:  
    virtual void Print();
protected:  
    int x, y; 
}; 
class Text {  
public:  
    virtual void OutputText(); 
protected:  
    char buffer[4]; 
}; 
class Circle : public Point { protected: int radius; };  
class CircleWithText : public Circle, public Text  
{ protected: int text_x, text_y; };

在多重继承中,标准并未要求在内存中多个父类之间的顺序。一种可能的内存布局如下:

绘图1

从上图可以看出,此时CircleWithText中将存在两个虚表指针,分别从两条继承线路中继承而来。也就是说,此时CircleWithText类将包含两张虚表,一张中存放由Circle带来的虚函数,一张存放由Text带来的虚函数。假如CircleWithText自己还有新的虚函数,则可以择一存放。

与单继承相比,多重继承除了内存布局的复杂程度增加了之外,在几种情况下运行时的指针运算同样非常重要:

  • 指针的类型转换
  • 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数
  • 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

让我们逐一观察这几种情况。

1. 指针类型转换

CircleWithText cwt;  
Circle *pCircle = &cwt;  
Point *pPoint = &cwt; 

Text *pText = &cwt;  
//pText = (Text*)((char*)&cwt + sizeof(Circle));

对于前两条赋值语句来说,不需要额外的计算,因为在CircleWithText对象中,Circle部分和Point部分的起始地址与cwt一样。而如果要转换为第二个父类的指针,则需要一定的计算。在计算中应当对NULL进行判断,如果需要转换的指针是空指针的话,转换后的指针也应该为空指针。

2. 通过子类调用由第二个父类(内存中靠后的父类)继承而来的虚函数

CircleWithText cwt;  
CircleWithText *pcwt = &cwt;  
pcwt->OuputText();  

上述代码中,使用了子类指针pcwt调用了由Text父类继承而来的虚函数OutputText。由于我们需要传入this指针,这个指针不应当传入pcwt,而是pcwt中Text部分的起始地址。可是很可惜,这只是一种情况;我们无法在编译期确定究竟需要传入哪个this,因为很有可能存在第三种情况:

 3. 通过指向第二个父类(内存中靠后的父类)的指针调用被子类覆盖的虚函数

class CircleWithText : public Circle, public Text  
{ 
public:  
 virtual void OutputText(); 
}; 

CircleWithText cwt;  
Text *pText = &cwt;  
pText->OutputText();  

我们首先需要注意这一段代码与上段代码的不同。这段代码中CircleWithText覆盖了Text中的OutputText函数。此时在pText->OutputText()这一调用中,传入的应为cwt的起始地址。

关键的问题终于出现了:第一:如何确定应当传入哪一个this指针?第二,假设已经确定应当传入CircleWithText的起始地址,那么如何从pText指针重新找到CircleWithText的起始地址呢?在编译期,我们无法知晓这些问题,就如我们不知道下面代码中p的真实类型是什么:

void some_func(Text* p) { p->OutputText(); }  

因此,我们只能通过一定的运行时机制来解决这个问题。下面介绍两种可以解决这一问题的方法。

方案一:在虚函数表中同时存储函数地址和this指针的偏移

示例图如下:

mb_vftable

此时在虚表中同时存储函数地址和所需的this指针偏移(注意,是偏移而不是地址)。因为this指针的“地址”是跟每个对象相关的,而每一个类只有一张vtable。不过偏移却是对于一个类的所有对象都适用的(比如,在一个CircleWithText对象中,想把Text部分的起始地址转换为CircleWithText对象的起始地址所需的偏移是一定的)。这种方法的弊端在于增加了单继承时虚表的成本。

方案二:为函数添加thunk入口

mb_thunk

这种方法不改变虚表的结构,而是将原本指向成员函数的指针改为指向一段由编译器自动生成的thunk代码的地址。在这一小段代码中,对指针进行调整,然后再跳转到真正的函数中去。

2.5 虚拟继承

虚拟继承所要解决的问题时在继承树中同一个父类出现多次的情况。有时我们仅需要一个基类,这就需要虚拟继承来解决:

class Drawable { public: virtual void Draw(); };  
class Point : virtual public Drawable;  
class Text : virtual public Drawable;  

图片1

实现虚拟继承的难度在于,如何将两个Drawable对象变为一个,同时要解决指针计算的相关问题。下面介绍几种方案:

方案一:虚基类指针

在虚拟继承的子类中,额外存储一个指针用于指向直接虚继承的父类:

绘图2

然而这一方案的问题在于,如果有多层的虚拟继承,其间接访问的时间成本也将增加。如果存在多个虚继承父类,则需要多个指针。

方案二:对象的虚基类指针表

对于方案一的一种改进是将这些指针都存放在一张表里,通过一个指针来访问:

vbtable

这一方案解决了方案一中的问题。然而正如之前所说,“地址”是与对象相关的,如果采用了方案二,就是说每一个CircleWithText对象都需要两张虚基类的指针table。

方案三:在虚函数表的负索引处存放偏移

为了解决方案二中的弊端,可以考虑使用偏移,这样的话就不必为每一个对象都生成几个虚基类表了。同时,鉴于虚函数表的负索引还没有被利用,我们可以在这里存放虚基类的偏移。

vb_vftable

3. 运行时环境


3.1 运行时类型识别

在虚函数表的第0项中,并不存储函数指针,而是运行时类型信息type_info。dynamic_cast和typeid是与运行时类型相关的操作。

一个典型的type_info 类可能定义如下:

图片2

3.2 异常

对于如下代码,我们如何判断应当析构哪些对象?

图片3

一种方法是根据程序计数器PC,然而这可能与特定平台相关。另一种方案是使用一个标识变量step,在每一个对象构建或析构之后将step加1。同时存放一张表,用于查询当step为n时应当析构哪些对象。

2.3 C++与动态链接库

对于某一种C++编译器编译产生的动态链接库,将很难其与其他编译器一同使用。原因在于C++标准并没有规定在二进制上的实现方式,编译器在名称改编、成员布局以及异常等机制上均存在着差异。不过,使用抽象类可以一定程度上解决这个问题,详情可以参考一些面向对象系统的实现,例如COM。

感知器算法

这是我之前在实验室的机器学习讨论会上的分享。


Table of Contents

  • 人脑的启示
  • 感知器算法
  • 双层感知器
  • 反向传播算法
  • 应用

人脑的启示


人的神经是由一个个神经元组成的,包括树突、轴突、胞体等。

Picture1

人脑具有以下特征:

  • 超过100亿个神经元
  • 神经元响应时间:约1毫秒
  • 人脸识别:约0.1secs
  • 平均每个神经元与1000个神经元相连
  • 计算高度并行

人脑擅长于模式识别、联想,并可以容忍噪声;电脑则擅长于计算,罗辑清晰。人脑的操作速度很慢,并且运算的结果不可靠,但其可以大规模地并行计算;而电脑的运算速度相当快,并且结果非常可靠。

模拟神经元的结构和工作方式,是感知器算法的主要机制。例如,刺激程度决定了这个神经元的兴奋程度,并且与其他神经元连接紧密时,信号强度大;连接疏松时,信号强度弱。

感知器算法


感知器算法的原理非常简单:

感知器算法

首先对输入信号的求和,当超过阈值时即使感知器兴奋。算法描述如下(from A Course in Machine Learning):

感知器算法

从算法描述可以看出,学习的意义在于向正确的结果靠拢。两组同样的数据,第一次分错了,第二次将会更加接近正确结果。

MaxIter是需要人工指定的参数,如果MaxItger 过大,容易发生过拟合;过小则容易学不到什么东西 。

同时,整个学习的过程就是在一个平面上寻找判别边界。为了简化问题,假设有一个线性可分问题,b=0,则感知器算法即在寻找分界面B:

snapshot7

B就是虚线,而由wd组成的向量w垂直于B:

snapshot8

由此也可以得出,w的绝对大小并不重要。

感知器算法的特点有:

  1. 在线学习,不需要一次性考虑整个数据集

  2. 错误驱动,当分类正确时,不进行学习操作

  3. 对训练集的输入顺序敏感。例如,有10000条训练数据,前9000条数据在默认的参数上就分类正确,则此次迭代只有最后1000条数据得到了训练。因此,不断地调整训练数据的顺序将有助于加快训练速度:

Picture4

朴素的感知器算法仍然存在一定的缺陷,例如后训练的数据会更加重要。参考上面举得例子,如果有10000条训练数据,前100条数据已经训练出足够好的分类器,一直到最后一条之前全部分类正确。最后一条数据就会掉了一个在99.9%的数据上工作得都非常好的分类器。

从以上的分析也可以看出,单层的感知器算法只能用于解决线性可分的问题。

算法改进

投票感知器算法

投票感知器算法会在训练时记录每一个分类器的存活时间,在最终预测时根据权重进行投票。

Picture5

但是由于需要保存每一个超平面,并且预测时需要使用每一个分类器进行预测,时空开销将非常大。

平均感知器算法

平均感知器算法仅记录加权平均后的分类器:

Picture6

除此之外,还有像信任权感知器、被动主动感知器、权表决感知器等。信任权感知器通过对输入添加信任权重的概率分布,使得信任度大的输入会得到更大幅度的修正;被动主动感知器可以主动修正学习速率;权表决感知器会为每一维输入产生一个分类器,最终由虽有分类器结果汇总投票产生,并对错误的分类器予以惩罚。

双层感知器


 snapshot9

在双层感知器中,将有两层感知器需要训练。除此之外,在单层感知器中,我们使用的是线性函数来计算感知器是否被激活;这种用于判断感知器是否激活的函数叫做激活函数(link function)。双层感知器中,隐含层通常采用非线性的sigmoid(tanh)函数来作激活函数。

对于双层感知器来说,它可以模拟任意连续函数;隐含层节点越多,函数越复杂。如果隐含层层数再增加,则可以模拟任意函数。

反向传播算法


对于感知器计算输出的过程来说,相当于正向传播;而通过计算结果反馈给隐含层和输出层来调整参数,则属于反向传播。例如:

Picture1

我们可以通过输出结果与标准值的误差,来修正向量v和矩阵w。常用的方法是梯度下降法,目标函数为结果误差的几何均值。通过对目标函数f求w和v的偏导,就可以求出v和w的梯度。

目标函数:

Picture5

计算结果:

Picture3

Picture4

总结


优势

  • 数学基础 如果有线性解则可以找到(单层)
  • 可以容忍噪声
  • 可以处理任意连续/非连续函数(多层)
  • 可以学到复杂的输入输出映射关系

劣势

  • 知识表示不易解释
  • 依赖于hidden层激励函数
  • 输入输出的设计对结果具有影响
  • 参数较多(神经元数目、层数、学习速率等)
  • 可能需要使用者的经验
  • 训练时间长
  • 过拟合

东野圭吾《秘密》

前段时间入手了Kindle Paperwhite 2,阅读体验得到了质的飞跃。如果想要读书的话,还是买来一个电纸书看比较好,比用手机电脑一类的好上太多了。

前几天终于把东野圭吾的《秘密》看完了,感觉十分的悲伤和压抑,真的无法深刻体会到网上那些说觉得“温馨”的人的感受。男主平介的妻子和女儿在回娘家的路上发生了车祸,妻子直子受到了严重的外伤,女儿藻奈美在母亲的保护下并没有外伤,却因为呼吸不畅导致深度昏迷。妻子在医院病床上了却了最后一桩心事——得知女儿藻奈美平安,并拉住她的手后,随即闭上了双眼。与此同时女儿却睁开了眼睛,直子的灵魂进入了藻奈美的身体,继续活了下来。

面对妻子的意识、女儿的身体,男主平介一直将她视作他的妻子直子,而妻子在外面只得装作藻奈美,回到家中后才变身为直子。可是,随着时间的流逝,平介和直子之间的鸿沟却越来越深:直子作为藻奈美,经历了平介所无法经历的事情,融入了上一代人所无法完全融入的下一代人中。平介是父亲也不是父亲,是丈夫也不是丈夫。在一开始,平介曾经对藻奈美的小学老师产生了好感,但最后他还是放弃了。他无法抛弃直子。

后来,平介逐渐认识到,他只认识在家的直子,却从来没有见过直子在学校的一面;外加他感觉直子在学校有了心上人,更加地想要窥探直子的隐私。私拆直子的信件,翻阅她房间中的资料,甚至监听家里的电话。最后,他终于发现,在圣诞节的那一天,她将会与学校网球社的学长约会;而他俩的情况在学校也已是公开的秘密了。平介在他俩约会的地方突然出现,直子哑口无言。

故事的另外一条线是肇事司机和他的家人。平介通过调查发现,肇事司机梶川在发现儿子不是亲生的之后,便与前妻离了婚。可是,他却无法不怀念儿子:他在想,把自己作为儿子的父亲,和把自己不作为儿子的父亲,哪一个能够让儿子更加幸福?在决心选择了前者后,便每个月给前妻寄送抚养费,以支持儿子上大学。

平介突然领悟了。造成如此大的压力的原因,在于自己将藻奈美当做直子。如何才能让直子、亦或是藻奈美幸福?只有把她当做女儿藻奈美。当他在家中喊出藻奈美的名字时,直子瞬间就明白了丈夫的心意。

然而意想不到的是,藻奈美却回来了,藻奈美和直子交替出现。直到有一天,直子和平介在他们最初约会的地方再一次约会后,直子就彻底消失了。——九年后,藻奈美结婚的那一天,平介不经意地从钟表金属店发现,藻奈美的婚戒是由直子的婚戒熔了之后再次打造而成的。直子的婚戒藏在藻奈美的玩具熊里,这是平介和直子之间的秘密。平介突然意识到,藻奈美从来没有回来过;而直子一直装作藻奈美,装了九年。

直子

由于小说一直是以平介的第一视角叙述的,我们也只能从平介的视角来观察直子。在直子身上,一直都是矛盾的。这不仅仅是因为她拥有藻奈美的身体、直子的意识,更深的原因是她在外面需要以藻奈美的身份生活。她不仅经历了所有藻奈美同龄人经历的事情,在生理上也重新经历了女生的成长过程,排斥父亲、希望与男生接触、与学长的暧昧关系等等。然而,回到家中又不得不成为平介精神上的的妻子。正如平介一样,直子也既是妻子也不是妻子,是女儿也不是女儿。

平介

小说对人物的描写非常细腻,代入感很强。工作党,对时事漠不关心,不会做饭,等等。但同时,他又是受害者家属中唯一一个关心肇事司机家人的人。他是一个在社会中虽显平庸、但却正直善良的人

当平介对妻子产生了怀疑、通过各种手段妄图窥视她的信息、以及当发现了妻子与学长约会时,那种内心的压迫和愤怒的感觉我甚至能够真切地感受到。我看完这本书的第二天早上,一想到小说的结局,就再也睡不着了。

把直子当作藻奈美是唯一一条解决方案,我也很清楚这一点;但是要做出这个决定,却需要很大的勇气。为此,平介花费了5年的时间。

除了中间一段让我有压迫感之外,故事的结局同样令我感到压抑。直子与学长约会,平介可以生气、可以愤怒,他的痛苦可以爆发,可以让直子知道。然而在故事的结尾、平介知道了真相之后,他的痛苦就只能由一个人来承受了。

Jump Out of C++:面向对象编程探索(一)

这是今年3月29号在IBM俱乐部做的技术分享的文字整理版。


 ppt_cover

这次的系列分享叫做“Jump out of C++:面向对象编程探索”,标题可以分为两部分:一个是关于C++的,一部分是关于面向对象编程的。其实我本来并没有想将太多关于C++的东西,才起名叫“Out of C++”,不过大家一致希望听一些,就把它单独拿出来分享一次。面向对象编程探索的“探索”两个字,其实也有两方面的含义。一个是面向对象编程的发展,另一个就是我自己对它的探索了。

整个讲座大概分为三个部分:第一部分主要介绍C++,以及C++ 11新引进的一些特性。其实C++在语法方面并没有太多想要说的,大家已经都已经很熟悉了;只是有一些不是那么常见、但还比较有用的东西,跟大家分享一下。介绍过了这个之后,我们可以有从两方面继续进行探索:一方面是更加具体:C++的一些运行时机制是如何实现的?另一方面是更加抽象:面向对象编程语言有哪些共同的特性?可以将它们分类吗?这两个方面将分别在第二部分和第三部分中介绍。

Table of Content


  1.  C++是如何诞生的?
  2. 面向过程:C语言兼容性与扩展
  3. 面向对象
  4. 模板与泛型编程
  5. C++ 11 新特性 

1. C++ 是如何诞生的?


  • 具有Simula那样的对程序组织的支持
  • 运行得像BCPL一样快
  • 高度可移植的实现

—— Bjarne Stroustrup

B.Stroustrup在《C++语言的设计和演化》一书中曾提到,上面这三点是他在创造C++时希望这一门语言所拥有的特点。这三点也指导了他整个语言的设计过程。

他是在读博士的时候产生了对C语言进行改进的想法的。他希望编写一个模拟程序,模拟分布式程序的执行。最初使用了Simula进行编写,编写的过程很愉快;可是运行时却不尽人意。Simula的优点在于可以使用类对数据和方法进行管理,同时还支持协程,可以很好地进行并发运算;可是缺点也很明显:编译效率低、运行效率也很低。B.S分析后认为,Simula的垃圾收集机制、运行时类型检查、变量初始化检查是拖慢运行时效率的罪魁祸首之三。

随后他用BCPL语言重新编写了模拟器,运行效率极佳;然而编写的过程却极为痛苦:没有类型检查,运行时的支持也几近为零。

这使他下定决心:如果没有好用的工具,是不会进行下一步工作的。

为什么是C?

C语言有着这些优点:灵活、高效、常用、可移植。灵活高效不必多说,常用是指当时几乎每一台机器上都有较为成熟的C语言编译器和运行环境;可移植更是正中B.S的初衷之一。

然而,C语言也同样有着一些缺点,比如安全性的缺失、以及古怪的声明语法。

比如:

int* v[10];

int (*p)[10];

typedef int DtoI(double);

typedef DtoI *V10[10];

V10* f(char);

我们无法按照正常的习惯从左到右读下去,复杂的声明要借助typedef才能获得一定的可读性。

他曾设想一种新的声明方式,类似如下这种:

v: [10]->int;

p: ->[10];

int f(char)->[10]->(double)->;

可惜的是,貌似是他最开始的时候忘记了;而后又已经无法将其加入语言当中了。

2. 面向过程:C语言兼容性与扩展


隐含的int类型

在C语言中,如果不加类型进行声明,默认即为int。比如

f();

static a;

void f(const T);

由于C++支持了模版机制,对于第三种声明来讲,将对编译器造成极大困惑:T是一种类型,还是类型为const int的变量?

最终废除隐含的int类型终于进入了C++标准。而为了这一结果,花费了整整十年的时间。在最初C++对C语言改革的最大阻力,不是来自B.S,不是来自开发者,不是来自标准委员会,而是C语言的用户。

结构标志与类型名

struct S a;

S a;

在C语言中,只有第一种变量声明是合法的;C++中第二种同样合法。这使得用户自定义类型的地位有所提高。

然而,事情并不是这么简单:

struct

对于C语言来讲,struct S中的符号S与int S中的符号S并不在一个名称空间中;而对于C++来讲,只有一个全局名称空间。这也就意味着,在遇到S时,C++会产生冲突:究竟是类型名还是变量名呢?

最终的选择是当冲突发生时,默认为变量名。原因在于当时有相当多的程序是有着上面左图那样的写法的,而最关键的在于Unix头文件中同样有很多类似的写法。兼容性的需求最终取胜。

全局变量的初始化

在C语言中,全局变量的初始化只能用稍微扩展一点的常量表达式来进行。这使得编译器可以在编译期求值,即不需要在运行时动态初始化。而C++则不同,如果要支持用户自定义类型的全局变量,则动态初始化是不可避免的。也因此支持了内置类型变量的动态初始化。

double p = 10.0 / 3;  //ok in C

double q = sqrt(10.0); //error in C, ok in C++ (Cfront >= 2.0)

class Double;

Double d = sqrt(10.0); //ok in C++

声明语句

支持了任意位置声明,以及在if/for中的声明语句。

其他不兼容的情况

  • 全局名称局部于文件,除非显式引出
  • 默认进行静态类型检查,除非显式抑制
  • 一个类代表一个作用域

在C语言中,void f();表示的是函数f可以接受任意参数。对于调用f(1, 2, 3);来说,C语言中是合法的。同样还有一些隐式类型转换,在C++中都有了更加严格的限制。

同时,在C语言中,结构体对内部的结构体并不起到对作用域的限制:

struct outer{

    struct inner{

        int a;

    };

};

struct inner in = {1};

C++修改了这一特性。

3. 面向对象


说到面向对象,大概就这几个方面:封装、继承、多态、抽象。我们从继承中的多重继承开始说起。

多重继承

多重继承是在Cfront release 2.0引入的。原因大概有这么几点:一个是能够使得设计进一步的推进,而且并不需要太多的扩充即可实现。当然,还有一点“主观因素”:一些人认为实现多重继承比实现参数化类型(即C++模板)更难,甚至有人在自己的书中谈到想要给C++添加多重继承是不可能的。B.S当时也是年少方刚正值气盛,当然要做来给他们看看了。他在之前很早就开始构想了多重继承的实现方式,并且已经想到了一个很好的实现。

对于多重继承,有一些人尚有争论。比如用处不大、增加负担、机制太弱、增加代码复杂程度……

但B.S的态度是:它(实现、运行起来)很便宜,又能解决关键问题,何乐而不为呢?

多重继承带来的典型问题是菱形继承问题。

菱形继承问题

对于多重继承来说,如果父类们有着相同的基类,那么在子类中将有祖父类的多份拷贝。有些时候这并不合理,我们希望子类中只有一个祖父类。C++引入了虚基类来解决这个问题:

虚基类

 事实上,继承也是一种封装:当我们使用父类时,它将子类的信息进行了隐藏。

多态

C++中,多态是利用虚函数实现的。想要表现出多态的效果,需要使用父类的指针或引用。

同时,dynamic_cast动态类型转换也必须对在具有虚函数的类型使用。这是因为他所依赖的运行时类型信息(RunTime Type Information, RTTI)是保存在虚表中的。

抽象类

带有纯虚函数的类叫做抽象类。纯虚函数允许没有函数实体,抽象类不能实例化。

抽象类的作用:

  1. 避免了无意义的对象产生

  2. 抽象类可以用来做界面(接口)

在很多语言中,接口是有单独的关键字来表示的,比如interface之类。C++中,抽象类就可以充当接口的作用:只提供使用方式,而将实现细节完全隐藏。

这样做的好处在于能够使得接口与实现相互分离,用户不需要清楚实现,更不需要显式地依赖具体实现。这也限制了修改后重新编译的范围,降低了耦合度。

4. 模板与泛型编程


 C++的模板支持模板参数的自动推断,以及非类型的参数。比如

template<int b, class T>  
T add(T a) {  
    return a + b;
}
int a = add(1); //a == 3  

同时,C++的模板并没有对类型进行显式限制的功能,例如必须继承自某个类,或是必须有那些方法才可以。C++模板对类型的限制是在使用上,比如 T a; a.print(); 如果类型T没有print方法,则在编译器会报错。

有时候我们需要对模板进行特化。即定义一个特定类型参数的版本,以处理一些特殊的情况。例如

template <class T>  
bool equal(T a, T b) {  
    return a == b;
}

template <>  
bool equal(const char* a, const char*b) {  
    return !strcmp(a, b);
}

同时模板还支持偏特化,即部分特化。例如多个类型参数,只特化其中一部分;或将其不完全特化,例如将普适的类型特化为指针类型。

模板元编程

C++的模板是图灵完备的。也就是说,理论上它可以执行任何计算任务。但由于模板是由编译器在编译期进行计算,受到编译器的限制。

模板元编程与函数式编程语言很像:没有可变变量,所有“函数”都没有副作用。例如下面是在编译期计算斐波那契数列:

template <int n>  
struct Fib {  
    enum {
        Result = Fib<n - 1>::Result + Fib<n - 2>::Result
    };
};

template <>  
struct Fib<1> { enum { Result = 1 }; };

template <>  
struct Fib<0> { enum { Result = 0 }; };

int main() {  
    int i = Fib<5>::Result;
    std::cout << i << std::endl;
    return 0;
}

模板在最初设计的时候只是为了参数化容器而设计的,最终能够用来进行元编程是一种“意外”,因此从语法上来说也并不是很舒服。

5. C++ 11 带来了什么?


  • 更优雅的初始化
  • 更优雅的委托
  • 更优雅的RAII
  • 更高的效率
  • 更强大的模板

更优雅的初始化

更优雅的初始化方式包括初始化列表、新增的类成员初始化方式、代理构造函数以及统一的初始化语法等。例如:

class IntArray {  
public:  
    IntArray(int s) : size(s) { ptr = new int[s]; } 
    IntArray() : IntArray(50){}     
    IntArray(std::initializer_list<int> list) : 
    IntArray(list.size()) { //... } 
private:  
    unsigned size = 0; 
    int* ptr = nullptr; 
}; 
IntArray intArray = { 1, 2, 3 };  

 上例中,使用std::initializer_list将可以接受类似数组方式定义的初始化成员值;在第三个接受初始化列表的构造函数中,其调用了第一个只接受整型长度的构造函数;而在类的内部,则可以直接使用赋值语法对成员进行初始化。如果在构造函数的成员初始化列表(冒号之后的列表,不是initializer_list)中没有对相应成员进行初始化,则使用在类中声明的值用作初始化。

同时,C++ 11还统一了初始化的语法。任何类型均可以使用大括号进行成员的初始化,例如:

class Test {  
public:  
    Test(int a, int b){} 
    virtual ~Test(){} 
}; 

int main() {  
    Test t{1, 2}; 
    Test t2 = {1, 2}; 
    int t3 = {1}; 
    int t4{1}; 
}

 上述代码中,四条初始化语句都是正确的。当存在接受initializer_list作为参数的构造函数时,大括号将会被解释为initializer_list(例如之前的IntArray)。

更优雅的委托

什么是委托?

class A {  
public:  
    void p(); 
}; 

class B {  
    A a; 
public:  
    void p(){ a.p(); } 
};

 当B有一件事情,转交给A去做的情况,就叫做委托。事实上,委托也可以用来实现继承;而在C++的早期,B.S也曾经设想过使用委托来实现继承,但最终放弃了这一想法。对于近几年新出炉的Go语言来说,自动委托是用来实现类似于继承思想的一种方式。

对于稍微复杂一点的委托,例如B希望A能够执行一些自己设定的任务(比如回调),则稍稍有些麻烦。在C语言中,函数指针经常用来承担这种任务:

typedef void (*FUNC)();  
class A {  
public:  
    void q(FUNC func) (func();) 
}; 
void f() {/*...*/}  
int main() {  
    A a; 
    A.q(f); 
    return 0; 
}

 然而,上述代码对于类的成员函数则不适用。对于以下三个f函数来说,他们的类型是不同的:

class B {void f();};  
// void B::(*)(); 

class C {void f();};  
// void C::(*)(); 

void f();  
// void (*)();

底层的原因则在于B和C有着一个不同类型的隐含参数:this指针。因此,这三个f函数,只有最后一个能够传给A.q作为委托的任务。

一个典型面向对象解决方案可以统一B和C参数不同的问题。使用一个Listener纯虚类作为接口,类A接受一个Listener作为参数,而B和C均继承自Listener:

class Listener {  
public:  
    virtual void f() = 0; 
}; 

class A {  
public:  
    void q(Listener *listener){listener->f();} 
};

class B : public Listener {  
public:  
    void f(){} 
}; 

class C : public Listener {  
public:  
    void f(){} 
}; 

int main() {  
    A a; 
    B b; 
    C c; 
    a.q(&b);
    a.q(&c); 
    return 0; 
}

 这种方式在Java中非常常见。然而,这种方法使用了面向对象的方式仅仅解决了面向对象那一部分的问题——A仍然无法接受不属于任何类的f()。

 C++ 11新引入了多态函数对象包装器std::function,可以很好地解决这个问题。

class A {  
public:  
    void q(function<void> f){f();} 
}; 

class B {  
public:  
    void Callback() {} 
}; 

void normalFunc(){} 

int main() {  
    A a; 
    B b; 
    a.q(bind(&B::Callback, &b)); 
    a.q(normalFunc); 
    return 0; 
}

实际上,藉由std::function,C++ 11还提供了闭包的功能,并引入了匿名函数来简化语法:

void someFunc(function<void> q){q();}  
int main() {  
    int a = 2, b = 3; 
    auto f = [=]() -> void { //[&a, &b] 
        cout << a + b << endl;
    };
    someFunc(f);
    return 0;
}; 

 更优雅的RAII

RAII(资源获取即初始化)是C++中对于资源管理比较重要的一个概念,最初由B.S在他的The C++ Programming Language中提到。在C语言中,一个常见的资源管理策略是:谁申请,谁释放。“谁”可以指函数,也可以指模块。

谁申请,谁释放

举例来说,例如一个负责字符串编码转换的函数:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size ) {  
    //Convert charset return true; 
}

显然,根据谁申请、谁释放的原则,这个函数不应该在函数内部申请内存,而应当由外部调用者申请好资源后传入。可是调用者如何知道最终转换后的字符串需要多大的空间呢?

因此,将函数修改如下:

bool Charset1ToCharset2( const char* input, unsigned input_size, char* output, unsigned output_size, unsigned* output_needed ) {  
    *output_needed = calc_output_size(); 
    if (output_size < *output_needed)
        return false;

    //Convert charset
    return true;
}

此时在func1中需要调用两次Charset1ToCharset2,第一次用以查询需要多少空间;第二次真正接收字符串编码转换的结果。这种方式在Windows API中也非常常见。

然而,这种方式在有很多分支、很多资源需要申请时,资源释放是一件相当繁琐的事情。尤其在C++支持了异常之后,很有可能会出现资源没有释放,函数就返回的情况。

RAII就是为了解决这一问题而产生的管理方式。它通过对象的生命周期来管理资源,当对象的生命周期结束时,自动释放所持有的资源:

class FileRAII {  
public:  
    FileRAII(const char* n, const char* m) 
    { /*fp = fopen(n, m); */} 

    FileRAII(FILE* p) { fp = p; }

    ~FileRAII() { fclose(fp); } 

    operator FILE*() { return fp; } 
private:  
    FILE* fp; 
}; 

bool func() {  
    FileRAII fp(fopen("1.txt", "r")); 
    if (fp == NULL) 
        return false; 
    //Use fp... 
    return true; 
}

不论func正常退出,或是在使用fp时触发了C++异常而导致异常退出,fp都会被析构,即fclose(fp)都会被执行。

在C++ 11 之前,实现一个通用的RAII类是比较复杂的。然而,当匿名函数和闭包被引入了之后,它变得十分简单:

class ScopeGuard {  
public:  
    ScopeGuard(function<void> on_exit) : _on_exit(on_exit){} 
    ~ScopeGuard() { _on_exit(); } 
    ScopeGuard(const ScopeGuard&) = delete; 
    ScopeGuard & operator=(const ScopeGuard&) = delete; private: 
    function<void> _on_exit; 
}; 

void func5() {  
    FILE* fp = fopen("1.txt", "r"); 
    ScopeGuard s([=] {fclose(fp); }); 
}

 垃圾收集:为什么不支持?

  1.  不适合低层次的工作
  2. 效率
  3. C语言兼容性
  4. 对象布局、创建的限制
  5. 不确定状态

  6. 很多GC算法在运行时要求暂时中断程序的运行。对于很多程序来讲,这可能并不是太大的问题;但是,这将使得C++不再适用于低层次的工作。在当时,C++已经被广泛地用于各种实时系统、嵌入式系统中,他们对这个问题实在是太过敏感。

  7. 时空开销。对于今天的硬件发展来说,这个问题小了很多,但弊端同上一点。如果真的要支持GC,提供一个开关也是比较合理的考虑。

  8. C语言支持一些底层的功能,比如指针运算、联合、强制类型转换等,还有不加检查的数组、不加检查的函数参数等等对于GC算法的设计非常不利的功能。比如,当用户申请了一块堆内存时,如何判断用户已经不再需要这块内存了呢?由于C语言支持指针运算,用户可以轻易地将指针算走之后再算回来。

  9. 垃圾收集同样将导致与其他语言的接口变得复杂。

  10. 用户难以知道某一块内存是否被释放了,它的状态是不确定的。

更高的效率

C++ 11中引入了右值引用、move语义和常量表达式来实现效率的提升。

“值”是指无法被进一步求值的表达式。对于“值”来说,通常我们分为左值和右值。一开始,左值被定义为“赋值号左面的值”,右值相反。可是,这种定义明显不再适用于C++。C++ 11中,明确定义了3种值类型:

左值:可以取地址的值

临终值:生命期即将结束,但其值尚未被取走。例如返回右值引用的函数的返回值,或是强制转换后的右值。

纯右值:不具有标志,可以移动。

广义的左值是指左值+临终值,他们可以表现多态;广义的右值指纯右值+临终值,他们不能被取地址。

在C++ 11之前,“引用”可以引用左值,“常量引用”可以引用左值+右值,然而缺乏一种方式只能引用右值。例如,在C++ 11之前,当一个函数返回一个对象时,将会有临时对象被创建。此时临时对象的构造将会增加程序运行的成本。

class IntArray  
{
public:  
    IntArray(int s) : size(s)
    {
        ptr = new int[s];
        cout << "constructor" << endl;
    }
    IntArray(const IntArray& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = new int[size];
        memcpy(ptr, a.ptr, sizeof(int) * size);
        cout << "copy constructor" << endl;
    }

    IntArray& operator=(const IntArray& a)
    {
        //......
        cout << "assgin operator" << endl;
        return *this;
    }
private:  
    unsigned size = 0;
    int* ptr = nullptr;
};

在VS中的测试结果是:未优化版本将有一次构造、一次拷贝和一次赋值;优化版本将有一次构造和一次赋值。Move语义在这里就派上了用场,它与Copy不同之处在于:

Move语义Copy语义 

当Object1对象是右值时,通过Move方式得到资源将会省去一次拷贝的过程。反正Object1也即将被释放,倒不如把资源送给Object2。

class IntArray  
{
public:  
    IntArray(const IntArray&& a)
    {
        delete[] ptr;
        size = a.size();
        ptr = a.ptr;
        a.ptr = nullptr;
        cout << "move constructor" << endl;
    }

    IntArray& operator=(const IntArray&& a)
    {
        //......
        cout << "move assign operator" << endl;
        return *this;
    }
};

constexpr关键字代表了新的常量表达式,它将在编译期被求值。例如:

constexpr int GetValue() {  
    return 5;
} 

int main() {  
    int a[GetValue() + 1];
    return 0; 
}

`
 在constexpr出现之前,这是不能编译通过的。带有constexpr修饰的语句将会在编译期被求值,如果无法求值的话将会出现编译错误。

常量表达式可以替代部分宏函数的功能,比如

enum Flags { good=0, fail=1, bad=2, eof=4 }; 

constexpr int operator|(Flags f1, Flags f2) {  
    return Flags(int(f1)|int(f2)); 
} 

void f(Flags x) {  
    switch (x) { 
    case bad: break; 
    case eof: break; 
    case bad|eof: break; 
    default: break; 
    } 
}

还有一些情况,是曾经无法支持的。例如,对于一个字符串常量来说,它其中的每一个字符也应当可以在编译器求值。但在constexpr出现之前,我们必须在运行时计算地址,然后取值;现在则不同:

constexpr char* str = "Hello World";  
int main() {  
    constexpr char a = str[1]; 
    cout << a << endl;
    return 0;
}

a将在编译期被取值。同样,我们也可以在编译期求值很多东西,它可以替代一部分模板的功能:

constexpr int exp(int a, int b) {  
    return (b == 0) ? 1 : a * exp(a, b - 1); 
} 
constexpr int a = exp(2, 10);  

 一个函数能否在编译期被求值是有要求的,例如不能有循环语句等。

更强大的模板

C++ 11 加强了模板的功能:模板不定参数、完美转发、编译期Assert、模板别名、返回类型后置(用来进行类型推导)等。

其他常见C++ 11特性

  • Range-based for
  • 强类型枚举
  • 新字符串字面值
  • thread
  • long long int
  • STL:tuple/unordered_map/regex/….

C语言中模拟/GS编译选项实现栈溢出检测

这其实是我在大二的时候给微软俱乐部捉虫大赛出的题目之一。代码基本上是写好了的,故意留出了一些bug,只可惜没人尝试来做。

关于/GS编译选项

VS在某一个版本之后添加了/GS编译选项,增强了对溢出检测的能力。随后对Windows XP进行了全面的重新编译,发布了SP2,安全性大大提高。

/GS的原理其实比较简单:

  1. 程序开始时,在堆的某个位置初始化一个security cookie。cookie的位置是不固定的。
  2. 存放cookie地址的指针大概在PEB之后的某个位置,地址也不固定,但是有一定的范围。对于这一点的记忆有点模糊了,手头也没有当时看的资料,网上也没搜到……确切查到了如果不对再来更新。
  3. 构建栈帧时,在所有的局部变量之前压入一个security cookie的副本。
  4. 函数返回时,检查栈中的security cookie副本与全局的security cookie是否一致,如果不一致则判定为栈溢出,执行相应的动作。

这些步骤之中很多自然需要由编译器来做,不过我们同样可以在源代码的层面模拟此类动作。当然,实际应用的价值也许并不大。

 在C语言中模拟/GS编译选项

下面的模拟与VS的/GS编译选项稍有不同。我们在栈中并不保存security cookie,而是保存cookie与当前栈帧中的ebp(即上一个栈帧的栈底)的异或值。由于当前ebp寄存器中保存的是当前栈帧栈底的地址,因此需要间访一次。在函数退出的时候,检查异或值即可。

采用这种机制的原因是,我们没有办法保证security cookie在所有临时变量之下,因此只好变通一下,跟ebp取个异或。

代码中对return做了define,因此所有函数的返回都必须以return的形式显示返回。没想到C语言里面怎么实现ScopeGuard,只能在return上下手了。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <string.h> 
/*
* A SIMPLE Security Cookie Example
* To Examine the Stack Overflow
*/
#define DEFALUT_SECURITY_COOKIE 0xE8CFF7E8 
int __security_cookie = DEFALUT_SECURITY_COOKIE;  
int __assistant_flag = 0;  
int cookie = 0, *ebp = 0;  
void __security_init_cookie()  
{
    __security_cookie ^= time(NULL);
}
void __security_check_fail()  
{
    printf("Stack Overflow!!n");
    exit(0);
}
#define __mainStartup (main) 
#define main() _main(int argc, char** argv) 
#define ENABLE_SECURITY_CHECK \
int cookie, *ebp, __assistant_flag;   \
__asm__("movl %%ebp, %0;":"=g"(ebp));   \
cookie = __security_cookie ^ *ebp;   \
__assistant_flag = 1; 

#define return if(__assistant_flag){ \
__asm__(" movl %%ebp, %0;":"=g"(ebp));   \
if((cookie ^ (*ebp)) != __security_cookie)   \
__security_check_fail(); }   \
return 

/**
* =======================================
* DO NOT CHANGE THE CODE FROM HERE
*/
int main();  
int __mainStartup(int argc, char** argv)  
{
    __security_init_cookie();
    return _main(argc, argv);
}
/* End of Security Cookie Example */

/* ---------------------------------------------
* User Code Begin
* Now Let's See How to Use Our Security Check
* Functions with ENABLE_SECURITY_CHECK MUST use return-statement to return
* DO NOT CHANGE THE CODE
*/
int main()  
{
    char s[5];
    ENABLE_SECURITY_CHECK
    strcpy(s, "Welcome to 5th Debug Contest!n");
    /* What a Stupid Overflow Example */
    return 0;
}

`

上面的代码中main和mainStartup的宏定义只是为了替换掉入口函数。

在不希望使用栈溢出检测的函数中,不添加ENABLE_SECURITY_CHECK即可。为了保证能够正常编译运行,定义了三个同样名称的全局变量。

不足之处

上面的代码如果在溢出时恰好将__assistant_flag设置为0了,也可以绕过后面的检测。这是不足之一;

security cookie的地址固定,不足之二;

重新定义了return,因此所有函数返回的地方需要显示return,不足之三。

C++面向对象基础

这篇文章是我去年3月份发在哈工大微软俱乐部邮件列表中的科普帖。


这个帖子将会和大家一起讨论一下面向对象编程的一些基础知识,旨在为大家深入学习提供基础。大二同学正好在做软设一,需要对面向对象与泛型有一些了解,大一同学也学过了python,时机正宜。欢迎大家积极回复讨论。

一、关于面向对象编程


一般来讲,对于面向过程的编程手法,一个程序是:

程序 = 数据结构 + 算法

整个过程就是解决相关问题的过程,使用合适的数据结构存储信息,合适的算法解决问题。 比如,对于一个采用面向过程的方式编写的学打酱油系统v0.1,大致如下:

struct 酱油瓶 {  
    string 酱油牌子
    integer 酱油量
}

void 打酱油(){  
    打开车门()
    上车()
    开车到粮油店()
    打开车门()
    下车()
    酱油瓶1.酱油牌子 = 康师傅
    酱油瓶1.酱油量 = 100
    //……
}

我们使用酱油瓶数据结构保存数据,打酱油函数实现打酱油的算法,最后成功地解决了打酱油这一历史性问题!

然而,这种面向过程式的编程方式随着软件架构越来越庞大,变得更加难以满足需求。进而,为了使软件结构易于设计、易于维护、方便扩展,越来越多的人选择了面向对象的方式来设计和实现比较庞大的系统。对于面向对象编程思想来讲,一个程序是:

程序 = 对象 + 对象 + 对象 + ……

所以面向对象编程的前提是要有妹子,然后你就可以面对着他编程了!

在详细讨论之前,首先要区分两个概念:类和对象。

类是一种类型、类别,它是一种抽象。而对象是这种抽象的实例。比如说我是人,他是人,她也是人。这里“人”就是一个类,我、她、他就是“人”这个类的实例。例如下面的C++<代码定义了人类:

class Human{  
    //xxxxxxxxx
};

而如果要定义Human这个类的对象,则是:

Human lishengqiu;

二、面向对象编程语言的特征


支持面向对象的编程语言普遍拥有以下三(四)个特征:

  1. 封装
  2. 继承
  3. 多态
  4. (抽象)

对于不同的编程语言,其实现机制可能不同,但思想应基本相似。下面我们就分别谈谈各个特征的具体内容。

1. 封装

封装其实是比较容易理解的。比如:CPU把内部复杂的实现全部封装在一块小芯片上,只留出诸多引脚提供给外部硬件进行访问;微波炉、电冰箱都把内部复杂的控制电路封装起来,只留下几个按钮提供傻瓜式的服务……

从上面两个例子我们总结出封装的特点:

  1. 对象的数据和操作都是这个对象的提供的。 – 也就是说,编程语言要提供数据和操作捆绑的能力。
  2. 提供操作接口给用户使用,而不是用户直接控制内部数据。 – 我们并不控制微波炉内部的任何结构与属性,而是通过操作面板对属性(比如每次加热多长时间,光波还是微波加热)进行控制;查看这些属性,也只能通过面板来查看。也就是说,编程语言要提供对成员的访问权限的控制。一般不会将对象的数据直接暴露给用户,而是让使用者通过我们提供的共有操作来对对象的属性进行改变。
  3. 封装的目的在于隐藏实现细节,提高安全性。对于用户的每一次操作,我们都可以有足够的能力自动对输入进行检查,以防止不合法的数据或操作。 在C++、Java、C#等这一大家子语言中,使用public/private关键字来对访问权限进行控制。以C++为例:
class Car{  
 public:
    int GetCarNo(){return carNo;}
    void SetCarNo(int number){if(carNo 

上面这段代码首先定义了一个叫做Car的类, 它拥有一个属性叫做carNo(车牌号?车型号?随便啦╮(╯▽╰)╭)。这个属性是私有的(private),不允许外部代码对其进行访问。同时提供了GetCarNo和SetCarNo公有成员函数来提供对carNo的修改。

在SetCarNo中,我们还对号码的合法性进行了判断。如果小于零,我们就认为输入有误,抛出错误(throw);无误的话就就将number赋值给carNo。

再考虑以下代码:

class Time{  
 public:
    int GetTimeBySec(){return hour*3600+minute*60+second;}
    double GetTimeByMinute(){return hour*60 + minute + second / 60.0;}
private:  
int hour, minute, second;  
};

当我们使用这个Time类时,我们不需要知道它内部数据的存储方式(是以小时、分钟、秒数分开存储,还是以只秒的总数存储,还是以分钟?毫秒?微秒?……);同时,Time类还提供了两种获得时间的方法:以秒为单位,以分钟为单位。调用者只需要按需调用接口函数就可以了,而不必关心内部的实现方式。

封装隐藏了内部的实现细节,这些是类的编写者所需要考虑的问题,而不是使用者。使用者不应该拥有涉及类的内部实现的能力,因为这将提高耦合,降低软件的可维护性。

不过,依然有人对封装的必要性持相反意见,有兴趣的同学可以搜索一看。

2. 继承

很多时候我们需要继承来表示对象之间的关系,有点类似父母与孩子。 在继承中,被继承的类(父亲)叫做父类、基类,而孩子类就叫做子类、派生类。C++中使用如下方式进行类之间的继承:

class Base{  
public:  
    int BaseMethod(){return 1;}
};
class Sub : public Base{  
public:  
    int SubMethod(){return 0;}
};

上述代码定义了一个基类Base,和一个方法BaseMethod;子类Sub采用公有继承方式继承Base,以及自己的SubMethod。这时对于子类来说,他将同时拥有BaseMethod和SubMethod两个方法,这就是继承最基本的作用。比如:

Sub sub;  
sub.BaseMethod();  //将返回1  
sub.SubMethod();    //将返回2  

继承提高了代码的复用程度,我们可以将一些公共的操作或属性抽象到父类中,以减少代码量。比如:

class Actor{  
protected:  
    string name;
    unsigned int hp;
    unsigend int mp;
};
class Luna : public Actor{  
};
class Kael : public Actor{  
};

上述代码中的protected关键字表示其数据与操作对外部不可访问,而对子类可以访问。

但是,继承也可能造成可读性的降低。如果继承的深度过高,很多属性和方法将很难确定究竟是由那一层子类提供的。

3. 多态
1. 没有多态的继承

考虑以下代码:

class Actor{  
public:  
    void attack(){}
protected:  
    string name;
    unsigned int hp;
    unsigend int mp;
};

class Luna : public Actor{  
public:  
    void attack(){
        cout << "Luna attack!" <<endl;
    }
};

class Kael : public Actor{  
public:  
    void attack(){
        cout << "Kael attack!" <<endl;
    }
};

基类Actor和子类Luna、Kael的attack函数实现并不相同。

同时,由于Luna和Kael是两个不同的类型,此时如果我们有一个函数希望调用luna和kael的attack方法,不得不这么做:

void letKaelAttack(Kael* kael){  
    //do something...
    kael->attack();
    //do something...
}

void letLunaAttack(Luna* luna){  
    //do something...
    luna->attack();
    //do something...
}


Luna luna;  
Kael kael;  
letLunaAttack(&luna);  
letKaelAttack(&kael);  

也就是说,我们无法写出一个通用的函数来调用不同子类的attack。如果我们有上百个英雄,就必须要写上百个letXXXAttack函数——即使他们都是Actor,有着相同的方法定义,而且也许函数中除了XXX->attack()之外所有语句都一样!

我们期望的解决方式也许是这样的,使用一个统一的函数来实现这种统一的功能。一个自然而然的想法是使用父类的指针作为形参。然而,直接使用actor->attack()将调用Actor类的attack函数(就是什么也不做的版本),因此我们需要对父类的指针做出一些转换。如果能够判断一个父类指针所指向的是哪一个子类对象就好了,这样我们就可以写出如下代码:

void letActorAttack(Actor* actor){  
    //do something...
    if(actor is Luna)
        ((Luna*)actor)->attack();
    else if(actor is Kael)
        ((Kael*)actor)->attack();
    //do something...
}

在C++中,actor is Luna这样的功能使用dynamic_cast关键字实现。即:

if(dynamic_cast<luna>(actor))

如果actor不是Luna, dynamic_castLuna*>(actor)将返回NULL。

然而,这样的解决方案仍然不完美。且不说依然要为每一个英雄写一个判断语句,如果我们需要新添加一个英雄的话,也需要修改letActorAttack函数。

2. 多态

继承使得子类可以表现的像父类一样,而多态则让父类表现的像子类。在C++中要使用多态,需要使用virtual关键字,将父类中的函数定义为虚函数。一旦声明虚函数,这个函数将一直是虚函数,不论子类中是否再有virtual关键字。

class Actor{  
public:  
    virtual void attack(){}
protected:  
    string name;
    unsigned int hp;
    unsigend int mp;
};

class Luna : public Actor{  
public:  
    void attack(){
        cout << "Luna attack!" <<endl;
    }
};

class Kael : public Actor{  
public:  
    void attack(){
        cout << "Kael attack!" <<endl;
    }
};

此时,我们的letActorAttack函数将非常简单:

void letActorAttack(Actor* actor){  
    //do something...
    actor->attack();
    //do something...
}

Luna luna;  
Kael kael;  
letActorAttack(&luna);  
letActorAttack(&kael);  

如果我们有一位新的英雄,只要它继承了Actor,实现了attack(),就可以把它的地址传给letActorAttack,而letActorAttack不需要任何改动。

另外需要特别说明的是,父类的析构函数应声明为虚函数,否则当使用父类指针delete子类时,子类的析构函数将不会被调用。这并不特殊,因为所有没有声明为虚函数的函数都如此;只是这个函数的地位有些特殊罢了。

4. 抽象
抽象类

还用我们上一个例子。对于Actor这个类来讲,它其实并没有实际意义,因此下面这句话其实是没有任何意义的:

Actor actor

而且,actor中的attack函数并没有实际意义,如果一个英雄继承了Actor但是却没有实现自己的attack,依旧不是我们想要的。

为了解决上述问题,C++采用纯虚函数的方式来解决。而当一个类中包含了纯虚函数,他将成为一个抽象类,并无法实例化。

我们将代码修改如下:

class Actor{  
public:  
    virtual void attack() = 0; //Note Here!
protected:  
    string name;
    unsigned int hp;
    unsigend int mp;
};

class Luna : public Actor{  
public:  
    void attack(){
        cout << "Luna attack!" <<endl;
    }
};

class Kael : public Actor{  
public:  
    void attack(){
        cout << "Kael attack!" <<endl;
    }
};

virtual void attack() = 0;这段代码声明了一纯虚函数,他将Actor这个类变成了一个抽象类。此时的Actor将无法实例化,仅可以作为指针使用。如果Sniper继承自Actor,但是没有实现attack函数,那么他将也无法实例化,即无法创建出Sniper实例。

抽象类做接口

我们现在希望做一个音乐播放器。播放部分比较重要的就是解码器了,但是每个不同的音频解码库的使用方法都不一样。目前已经准备好APE、MP3和OGG的解码器了(MACLib, mpg123, OggVorbis),如何才能有效地使用这些解码器呢?

利用我们目前已经了解的继承、多态、抽象类,可以很容易想到解决方案:

  • 我们可以为每一个解码器做一层封装,将每一个解码器的使用方式封装起来。这样上层使用者不需要知道我们内部的具体实现,只需要调用我们的公开函数即可。
  • 我们对每一个封装好的类进行抽象,提取出公共的接口,使用一个抽象类作为基类,不同的解码器封装继承自抽象基类。
  • 得益于多态,我们使用抽象基类指针即可操作不同的子类对象。

下面的代码取自我曾经实际做过的项目,适当做了省略和修改:

class Decoder{  
public:  
    virtual int CheckSupport(const char*) = 0;
    virtual int Open(const char*) = 0;
    virtual int Seek(double) = 0;
    virtual void GetFileExt(char* ,char*) = 0;
    virtual int GetFormat(long*,int*) = 0;
    virtual int GetFileInfo(Info*) = 0;
    virtual int GetFileInfo(const char*, Info*) = 0;
    virtual int ReadAndDecode(unsigned char*,int,unsigned int*) = 0;
    virtual double GetPosition(int buffered = 0) = 0;
    virtual double GetLength() = 0;
    virtual int Close() = 0;
    virtual ~Decoder(){}
};

class ApeDecoder : public Decoder{  
private:  
    //省略数据成员
public:  
    ApeDecoder();
    ~ApeDecoder();
    int CheckSupport(const char* fname);
    int Open(const char* fname);
    int Seek(double sec);
    void GetFileExt(char* Description, char* FileExt);
    int GetFormat(long* rate,int* channel);
    int GetFileInfo(Info* info);
    int GetFileInfo(const char* filename, Info* info);
    int ReadAndDecode(unsigned char* buf,int size,unsigned int* read);
    double GetPosition(int buffer_size = 0);
    double GetLength();
    int Close();
};

class MP3Decoder : public Decoder{//...}  
class OggDecoder : public Decoder{//...}  

Decoder是一个抽象类,他甚至什么数据都没有,只有成员函数。我们使用这个类作为接口,来操作子类:

Decoder* decoder = new MP3Decoder();

不过很多时候,我们并不像让用户知道子类的名字,因为这意味着需要提供子类的声明。例如,我们想把我们写的这些代码封装成库,提供给其他用户调用,尽量隐藏细节。这时我们通常会采用一些合适的设计模式,例如简单工厂模式,将子类的制造过程也抽象出来:

Decoder* CreateDecoder(string name){  
    if(name == "mp3")
        return new MP3Decoder();
    else if(name == "ape")
        return new APEDecoder();
    else if(name == "ogg")
        return new OggeDcoder();
    else 
        return NULL;
}

此时,用户只需要Decoder的声明和CreateDecoder的声明就可以了,以及我们提供的库文件。调用时也非常简单:

Decoder* decoder = CreateDecoder("mp3");

所有的操作都被隐藏在抽象之下。而Decoder类的作用,仅仅是提供接口;由于具有多态性,decoder变量将表现的像他的孩子一样,而用户完全不需要知道任何细节,例如我们的MP3子类究竟是叫MP3Decoder还是叫Decoder_MP3?或是我们的MP3Decoder究竟使用的是哪一种mp3解码库(是mpg123还是ffmpeg)?同时,只要接口不做改变,我们所有的类的实现方式都可以随意更改,而用户不需要修改他们的任何代码就可以直接使用我们修改过的库。

在一些其他语言中,使用独立的关键字(例如interface)来提供对接口的定义。

三、尾声

这篇帖子简单介绍了面向对象编程语言的几大特征,很多支持面向对象方式编程的编程语言基本上会都在不同程度上支持这些特性。有一些语言会有所缺失,我们也可以认为他们是面向对象编程语言;而有一些语言则支持更加广义的特性。对于这些特性多多地加以合理利用,往往会使代码更加易于组织和构造,也更加易于编写和维护。

编写3dsmax骨骼动画导出插件

上一篇文章中我们讨论了蒙皮骨骼动画的基本原理,本文我们将继续编写3dsmax的骨骼动画导出插件。目前网上我找到的使用IGAME导出骨骼动画的文章只有那么几篇,而且讲得并不详细,自己还是踩了很多坑。之前也并没有相关经验,只能自己摸索着来并在此总结,希望能够让读者们绕坑而行。

1. 安装3dsmax sdk

在3dsmax的安装程序中会有一项“安装工具和实用程序”一项,选择其安装即可。

1

安装好后将maxsdk/howto/3dsmaxPluginWizard目录中的3dsmaxPluginWizard.ico、3dsmaxPluginWizard.vcz、3dsmaxPluginWizard.vsdir拷贝至vs目录中的vc/vcprojects中即可。我是用的是express 2013,目录名称叫做vcprojects_WDExpress。

2.配置Visual Studio

在vs的新建工程中将可以看到3dsmax导出插件的工程项目,新建后将自动生成程序入口代码。不过在开始之前还需要再做一些小动作:由于每次max加载插件后,一直到关闭3dsmax才会将句柄释放。也就是说当我们想测试插件时,每次都必须重启3dsmax才能重新加载插件,非常不方便。为了解决这个问题,我们可以再新建一个普通的DLL项目,所有的主体代码均在此DLL中实现。每次调用完毕后,立刻释放句柄。[1]

1

3.骨骼动画导出插件的编写

之后就可以开始导出插件的编写了。3dsmax sdk提供了一个叫做IGame的工具,具备很多实用的功能,可以方便我们收集场景信息。首先需要引入IGame的头文件,以及igame.lib。

导出模型、材质等过程这里就省略了,网上的教程应该有很多,可以搜索一下。

3.1 IGame初始化

我们首先需要做一点初始化的工作:获得IGame的相关接口,设置坐标系等等。坐标系设置好后,3dsmax会自动为我们计算矩阵变换。

bool exportSelected = (options & SCENEEXPORTSELECTED) ? true : false; IGameScene* scene = GetIGameInterface(); IGameConversionManager * cm = GetConversionManager(); UserCoord rightHandCoord = { 1, 1, 2, 5, 1, 0 }; cm->SetUserCoordSystem(rightHandCoord); scene->InitialiseIGame(exportSelected);

第一行首先确定用户是否是选择了“导出选择的物体”。IGame会根据此选项来创建场景树。

第四行设置了导出的坐标系,sdk的头文件中有详细的注释解释了UserCoord结构体各项的作用:

struct UserCoord{ //! Handedness /! 0 specifies Left Handed, 1 specifies Right Handed. */ int rotation; //! The X axis /! It can be one of the following values 0 = left, 1 = right, 2 = Up, 3 = Down, 4 = in, 5 = out. / int xAxis; //! The Y axis /! It can be one of the following values 0 = left, 1 = right, 2 = Up, 3 = Down, 4 = in, 5 = out. / int yAxis; //! The Z axis /! It can be one of the following values 0 = left, 1 = right, 2 = Up, 3 = Down, 4 = in, 5 = out. / int zAxis; //! The U Texture axis /! It can be one of the following values 0 = left, 1 = right / int uAxis; //! The V Texture axis /! It can be one of the following values 0 = Up, 1 = down */ int vAxis; };

下面首先先收集一下各个结点的信息。我们通过遍历整棵场景森林的方式,收集模型结点和骨骼结点的信息。导出模型、材质等内容本文就省略了,网上的教程应该有很多,搜索一下就可以了。我们来关注骨骼结点的统计:

map bones; void GetMeshNode(IGameNode* node, vector& nodes, int& totalVertexNum) { switch (node->GetIGameObject()->GetIGameType()) { case IGameObject::IGAMEMESH: /*此处省略*/ break; case IGameObject::IGAMEBONE: bones.insert(make_pair(node->GetNodeID(), node)); break; default: break; } int childNum = node->GetChildCount(); for (int i = 0; i < childNum; i++) { GetMeshNode(node->GetNodeChild(i), nodes, totalVertexNum); } }

 对所有根节点都调用此函数就可以收集到所有的骨骼结点信息。bones中存储的就是我们所有的骨骼结点,之后再导出骨骼和骨骼动画就非常简单了:

int startTime = staticcast(GetCOREInterface()->GetAnimRange().Start() / GetTicksPerFrame()); int endTime = staticcast(GetCOREInterface()->GetAnimRange().End() / GetTicksPerFrame()); boneHeader.FrameNum = (endTime – startTime) + 1; fwrite(&boneHeader, sizeof(boneHeader), 1, filp); for (int i = 0; i < boneHeader.FrameNum; i++) { for (map::iterator it = ::bones.begin(); it != ::bones.end(); it++) { float t = i * GetTicksPerFrame(); GMatrix gm = it->second->GetWorldTM(t); t /= 4.8; fwrite(&t, sizeof(t), 1, filp); Point4 p1 = gm.GetColumn(0); Point4 p2 = gm.GetColumn(1); Point4 p3 = gm.GetColumn(2); Point4 p4 = gm.GetColumn(3); fwrite(&p1.x, sizeof(p1.x), 1, filp); fwrite(&p2.x, sizeof(p1.x), 1, filp); fwrite(&p3.x, sizeof(p1.x), 1, filp); fwrite(&p4.x, sizeof(p1.x), 1, filp); fwrite(&p1.y, sizeof(p1.x), 1, filp); fwrite(&p2.y, sizeof(p1.x), 1, filp); fwrite(&p3.y, sizeof(p1.x), 1, filp); fwrite(&p4.y, sizeof(p1.x), 1, filp); fwrite(&p1.z, sizeof(p1.x), 1, filp); fwrite(&p2.z, sizeof(p1.x), 1, filp); fwrite(&p3.z, sizeof(p1.x), 1, filp); fwrite(&p4.z, sizeof(p1.x), 1, filp); fwrite(&p1.w, sizeof(p1.x), 1, filp); fwrite(&p2.w, sizeof(p1.x), 1, filp); fwrite(&p3.w, sizeof(p1.x), 1, filp); fwrite(&p4.w, sizeof(p1.x), 1, filp); } } fclose(filp);

上面的代码有几处需要解释一下:

首先我们存储的是模型坐标系中的矩阵(GetWorldTM),而不是相对于父节点的矩阵信息。在上一篇文章中我们曾提到,如果想要进行动画插值,需要计算出相对于父骨骼的变换矩阵。

其次,Tick是3dsmax中的一个时间单位,一秒钟有4800个Tick。我们导出时的时间以毫秒为单位,因此时间就是当前的Tick数除以4.8。

最后,一长串的fwrite实在是迫不得已。使用其他方式(比如)GetRow返回行时将会产生奇怪的编译错误;之前在用到Point4时也出现过问题。这有可能是由于我使用的是vs2013,而3dsmax 2012的sdk的目标工具集是vs2010导致的。

下一篇文章中我们将介绍如何在程序中计算骨骼动画并使用OpenGL显示。

参考

[1] 3dsmax模型导出插件调试技巧, http://blog.csdn.net/zhengkangchen/article/details/6424806

[2] 3DsMax导出插件编写(三)——使用IGame收集模型信息, http://blog.163.com/liweizhaolili/blog/static/16230744201311219926255/

蒙皮骨骼动画技术原理

1.前言

骨骼动画技术在计算机图形创作以及游戏开发中都占据了非常重要的位置。在骨骼动画技术出现之前,顶点动画和刚体分层动画是主要的3d动画实现手段。然而在肢体运动方面,他们都有或多或少的不足。骨骼动画则提供了较好的解决方案,因此自从《超级马里奥64》等第一批使用了骨骼动画技术的游戏诞生后,它就一直被广泛使用。

2.预备知识

在骨骼动画中,每个需要运动的顶点都被关联至某一个或多个骨骼。当骨骼的位置、方向等参数发生变化时,相关联的顶点也一同跟随其运动。而骨骼与骨骼之间的关系就像人体骨骼一样:当父骨骼发生变化时,子骨骼会发生同样的变化。因此在每一组骨骼中,除了根(Root)骨骼之外,每根骨骼都会有一个父骨骼。

骨骼与骨骼之间的节点称为Joint,或者说骨骼(Bone)是Joint之间的连接。他们在骨骼动画中可以看作是等价的概念。

这是因为所谓“骨骼”,无非是一系列的变换矩阵。从这一观点来看,Joint更适合描述骨骼动画中的“骨骼”。

接下来我们要讨论一些数学色彩稍多一点的内容,不过只要基本的线性代数的知识就足以应付了。

模型坐标系

我们在建模的时候,一般都在模型自身的坐标系中完成。在导出模型时,模型中顶点的坐标一般也以此为参考系导出;而当游戏引擎加载模型后,会使用场景管理器将其挂在场景图(Scene Graph)中合适的节点上。而在渲染时需要使用世界坐标,从模型坐标转换到世界坐标的过程将由游戏引擎来完成。

局部坐标系

大空间可能会由小的局部空间组成,如果我们为局部空间定义一个坐标系,就可以称其为局部坐标系,这是一个比较宽泛的、相对的概念。例如,在整个世界中,模型坐标系就是一种局部坐标系。如果在一个模型中,我们为更小的部分定义了一个坐标系(比如骨骼),那么它相对于模型坐标系来说,就是一个局部坐标系。

父坐标系

如果一个局部空间具有父节点,它的父坐标系就是指父节点的坐标系。

坐标变换

通常我们需要在不同的坐标系之间进行坐标变换。当一个点的坐标乘以一个变换矩阵时,我们可以认为这一个点在当前坐标系中移动了;也可以认为“点”本身没有动,是参考的坐标系移动了。也就是说,如果我们想要获得同一个点在不同坐标系下的变换矩阵,使用矩阵乘法即可获得结果。

3.骨骼动画原理

上文曾提到,模型的每一个需要移动的顶点,都通过与相应的骨骼绑定来实现。也就是说,只要我们记录下在每一帧中所有骨骼的位置、方向等信息,就可以计算出顶点的位置;如果我们在程序中每一帧都用这些信息更新顶点位置,就可以让模型动起来了。但是在此之前,我们还需要得到骨骼的“初始信息”。下面我们先暂时只考虑每个顶点仅绑定至一根骨骼的情况。

这是一种比较简单的实现方式,代价是很难进行合适的插值。下文将提供改进的方法。

Bind Pose

美工人员在绑定骨骼时,往往都在一种方便绑定的姿态下操作,这个姿态叫做Bind Pose。下图是一个比较典型的Bind Pose姿态(From cally):

bindpose

我们在导出模型时,顶点位置也往往使用模型处于Bind Pose姿态时的位置,而此时每根骨骼的姿态就是上文提到的“初始信息”。设BindPose姿态下某一根骨骼相对于模型坐标系的变换矩阵为Mb。当骨骼运动时,虽然顶点的坐标在变,但该顶点相对于所绑定的骨骼的位置并不改变(当仅绑定至一个骨骼时)。因此,对于每一个顶点,我们需要进行以下变换:

BindPose姿态下的坐标(模型坐标系)→局部坐标(骨骼局部坐标系)→当前帧坐标(模型坐标系)

首先我们先来解决第一步转换。我们曾记录了Bind Pose姿态时骨骼的姿态Mb,利用Mb,我们可以将局部坐标转换为BindPose坐标,即:

vL * Mb = vb

其中vL为局部坐标,vb为Bind Pose坐标。

如果读者不理解为何使用Mb可以将局部坐标转换为BindPose坐标,可以做以下的推理:

上文中曾提到,“当一个点的坐标乘以一个变换矩阵时,可以认为这一个点在当前坐标系中移动了;也可以认为‘点’本身没有动,是参考的坐标系移动了”。设想一个点从模型空间原点p(0, 0, 0),移动到BindPose姿态时骨骼所在的位置p’:

p * Mb = p’

那么如果另一点q处于骨骼的局部坐标系中,其坐标为q(0, 0, 0),希望将其变换为模型坐标系中的坐标q’,实质上就是将骨骼局部坐标系移动至模型坐标系,即

q * Mb = q’

因此如果我们想将Bind Pose坐标转换为骨骼局部坐标,需要以下公式:

vb * Mb-1 = vL

也就是说,我们只需要记录Mb-1即可。在第二步转换中,变换矩阵就是骨骼在当前第i帧的位置Mi(模型坐标系),即

vL * Mi = v

因此我们所需要的信息只有两个:1.每根骨骼的BindPose矩阵的逆。2.每根骨骼在每一帧的矩阵。(它们都是相对于模型坐标系的。)只要有这两个信息,我们就可以计算出每个顶点在每一帧的位置了。

在这一小节结束之前,还有一点需要补充:所谓Bind Pose姿态,不过是一个“基准”。其实任何一帧的姿态都可以成为“基准”,即只要在导出时模型的顶点位置与骨骼的变换矩阵在同一姿态下即可。

4.骨骼动画的插值

上述方法很难对动画进行合理插值,这就失去了骨骼动画的一大优势。其原因在于我们所使用的M矩阵是相对于模型空间的。如果仅依此对矩阵进行插值,有时很难的到合理的结果,容易出现错位、交叠等现象。

解决这个问题的办法是使用相对于父骨骼的矩阵Mr(即相对于父坐标系)。当前骨骼通过Mr得到父坐标系下的坐标,其父骨骼再通过它的Mr得到父亲的父坐标系下的坐标……直到计算到相对于模型坐标系的坐标。如下图(From* Game Engine Archtecture*):

matrix

即上文中的公式将变成:

vL * Min * Mi(n-1) … * Mi0 = v

由于此时每个骨骼将相对于父骨骼进行运动,因此插值结果将更加合理。不过变换矩阵的插值算法超出了本文的范围。

5.将顶点绑定至多个骨骼

当需要将顶点绑定至多个骨骼时,需要为每个骨骼设置一个权重,代表该骨骼对该顶点的影响程度。计算时每个绑定的骨骼的都按照上述计算方式进行计算,最后根据权重计算最终的顶点坐标即可。

6.总结

本文简要介绍了蒙皮骨骼动画的基本技术原理。下一篇文章将介绍如何编写3dsmax插件导出骨骼动画,并使用OpenGL在我们的程序中加载。