C_的动态多态和静态多态

C_的动态多态和静态多态200510JLI3120OOctober2005ComputerEngineeringVol.31NQ20A1000—3428(2005)20—0072—02TP311I1Ij??的动态多态和静态多态C++赵红超，方金云，唐志敏(中国科学院计算技术研究所，北京100080)摘要:多态是C++中面向对象技术的核心机制之一，包含静态多态和动态多态，它们之间有一定的相似性，但是应用范围不同。该文论述了这种相似性，并重点论述了以实现的静态多态的应用范围。关键词:动态多态,静态多态,模板多态,概念,模型,模板库StaticandDynamicPolymorphisminC++ZHAOHongchao,FANGJinyun,TANGZhimin(InstituteofComputerTechnology,ChineseAcademyofSciences,Beijing100080)【Abstract】Polymorphismisoneofkeymechanismsforobject-orientedtechnologyinC++,whichisclassifiedintostaticpolymorphismanddynamicpolymorphism.Therearemanysimilaritiesbetweenthesetwopolymorphisms,buttheydifferinappliedscopes.Thisarticlediscussesthesimilaritiesandemphasizesonthescopesofstaticpolymorphism.【Keywords】Dynamicpolymorphism;Staticpolymorphism;Templatepolymorphism;Concept;Model;Standardtemplatelibrary(STL)classTPoint2D1C++语言的多态{//实现访问x，y，z的函数};C++支持多种风格的编程模式，称之为编程范C++型。classTPoint3D支持的编程范型包括面向过程的、基于对象的、面向对象的{/实现访问x，y，z的函数};和泛型编程。也提供一个求两个点距离的函数对象:通过指针和引用来支持多态，是面向对象的编程范型区template<typenamepoint_t>别于基于对象的编程范型的本质所在。所谓多态，是指通过classDistance_op::publicbinary_function<constpoint_ct&on,st单一的标识支持不同的特定行为的能力。C++支持多种形式point_t&,double>的多态，从绑定时间来看，可以分成静态多态和动态多态，{public:doubleoperator()(constpoint_tpt1&,constpoint_t&pt2)也称为编译期多态和运行期多态,从现的形式来看，有虚[1]{doubledx=pt1.x()-pt2.x();函数、模板、重载和转换。doubledy=pt1.y()-pt2.y();由于静态多态在时间和空间上都比动态多态表现得好，doubledz=pt1.z()-pt2.z();因此在其他的条件相同的情况下，应该更多地使用静态多态。returnsqrt(dx*dx+dy*dy+dz*dz);}2模板多态的应用范围};2.1代码实例在上面的两种结构当中，二维结构都是三维结构的一种在类型需要参数化的时候使用模板多态。为了说得更明退化情况(二维结构在z坐标的取得值返回0，设置值是空函白，使用一个具体的代码例子，具体要求是:提供一个空间数)。目前看来这两个的结构都很优雅,虽然模板的效率会点的结构，可能是二维或者三维的,同时提供一些算法，例高一些，但是不足以让我们舍弃虚函数结构而选择模板如两点之间距离，点序列总长度。结构。(1)使用虚函数支持的动态多态2.2对象本身的集合求一个点系列的总长度的算法，使用模板的结构如下:classPoint//虚基类{//提供访问x，y，z的纯虚函数};template<typenameFrowardIterator,typenameBinaryOpera>tionclassPoint2D:publicPoint//二维子类doubleadjacent_op(FrowardIteratorfirst,FrowardIteratorlast,{//实现访问x，y，z的纯虚函数};BinaryOperationop)classPoint3D:publicPoint//三维子类{doubleresult(0.);{//实现访问x，y，z的纯虚函数};FrowardIteratornext=first;提供一个求两个点距离的函数:while(++next!=last){doubleDistance(constPoint&pt1,constPoint&pt2)result+=op(*first,*next);基金项目:国家“863”基金资助项目(2002AA114020，2001A{doubledx=pt1.x()-pt2.x();A135210),中国科学院知识创新基金资助项目(20036020)作者简doubledy=pt1.y()-pt2.y();介:赵红超(1976—)，男，博士生，主研方向:计算机应用，编程语doubledz=pt1.z()-pt2.z();言，并行处理,方金云，博士、副研究员,唐志敏，研究员、博导returnsqrt(dx*dx+dy*dy+dz*dz);}(2)使用模板多态，提供两个POD类收稿日期:2004-09-08E-mail:zhaohc@ict.ac.cn—72—first=next;}这些行为是可以在编译期决定的，可以考虑使用模板多态。returnresult;}用这一点来考察标准模板库STL，STL提供的容器类和针对voidtest()//测试容器类的算法都属于这个范畴。虽然这些容器可以存放不同{vector<TPoint2D>tpts(20);类型的对象，但是这些对象的类型和大小是编译前决定的，doubletlen=adjacent_op(tpts.begin(),tpts.end(),Distance_op<不会在运行期改变。TPoint2D>());}2.4policy-based的程序采用模板的结构实现点的结如果使用虚函数结构，也可以这样:构，可以应用于二维和三维doubleLength(constPoint*first,constPoinlat*st)的情况，我们的算法只要在使用的时候配置不同的参数就可{doubleresult(0.);以了。为了具有更大的通用性，可以把维数推广到N维:constPoint*next=first;while(++next!=last){template<intN>classCoordresult+=Distance(*first,*next);{doublecoords_[N];first=next;}public:returnresult;}doubleget(intindexcon)st但这是错误的,原因是:sizeof(Point)不等于sizeof{//返回在index纬度上的值}voidset(intindex,doublevalue)(Point2D，)++next指针的位置不是指向下一个位置Po的int2D{//设置在index纬度上的值}};对象，程序也许会崩溃。更深的原因是:向vec量tor里面放template<intN>doubleDistanceN(constCoord<N>&pt1,const的是Point2D对象本身，而不是对象的指针，所以我们期待Coord<N>&pt2)的对象的多态行为不会发生。{//求得距离}纠正这个错误可以有两个方法(1):改变Length函数的参N的大小由使用这个泛型算法或构件的用户在编译期选数类型，改成Length(constPoint2D*first,constPoint2D*定。用户可能还有其他的选择，例如在不同的线程的环境下last)。这个方法显然不能令人满意，因为求得三维点序列的面，数据是否加锁。但是除了这种加锁的操作，其他的代码总长度，要写一个几乎完全一样的函数。(2)我们的模板辅助没有改变,应该复用这些代码，并且把加锁的选择交到用户函数adjacent_op，使用如下:的手中。用户的不同选择体现为用户的一种策略，编程者应voidtest()该充分的考虑这些策略，体现在代码当中。这种基于策略{vector<Point2D>pts(20);考虑的程序设计称为policy-based的程序doubletlen=adjacent_op(pts.begin(),pts.end(),Distance});设计，这样的设计方法在AndriAlexandresc的著作中有过充u在这里需要使用模板来达到目的，说明使用虚函数来解[4]分的论述，并且展示了这种方法的巨大威力。policy-决这个问题是有缺陷的。based程序设计利用多重继承和模板机制，把各种要考虑正如前面所说的，向量vector里面放的是Point2D对象的策略设本身，而不是对象指针，虚函数多态行为不能发生。反过计成为高度可组装化的基本单位。用户可以灵活地选择、配[4]来置自己的应用程序。一般来说，这样的策略应该是正交。的也给出了模板的一个适用范围，即:当我们的程序使用了对policy-based的设计方法在很多的情况下首先考虑复杂象本身的集合，而不是对象指针的集合，而这些对象的行为的情况，然后把简单的情况看成是复杂情况的一种退化。考表现出共同性的时候，可以考虑使用模板多态。虑不同的线程环境，多线程环境下的加锁是确实的行为，而当然，把多态和数组混合使用本身就有问题，这一点在单线程则是空函数。这种技术在微软A的TL中有大量的应用。[5]ScottMeyers的著作的条款3中有过详细的论述。如果我们的代码需要表现出某种策略的选择，这种策略2.3编译期多态从另外一个角度看问题，即为什么要把二维依赖于客户端代码的编译前配置,而如果不考虑这些策略，和三维的点代码表现出很大的共同性，在这种情况下可以考虑使用模板结构放在一起编码。从实际的应用来看，很少把二维和三维多态。的点混合在一起使用，即要么我们的程序使用的是二维的点2.5效率结构，要么使用三维的点结构,而这一点是在编译以前就可相对于其他的语言,例如Java,，效率是C++的一个重要以确定。之所以把这两种结构放在一起考虑，主要是因为我们的算法对这两种结构表现出共同性。我们的求距离的的优势。模板多态是静态的多态，相对于虚函数的多态，当Distance算法、求总长度的Length算法，并不依赖于点结构然更有效率，这一点在某些对效率要求很高的程序,例如数的维数。所以目的是要复用这些算法，而不在每种点结构下学库,中，显得尤为重要。有时候用模板来实现一些数学运重写这些算法。算，也是为了减少读写次数，避免临时变量的产生,因为有考虑一个使用面向对象技术的典型应用，即绘制点、线的时候临时变量的产生是一个严重的性能障碍，尤其是对于和面等几何体的跟客户交互的应用程序。虽然点线面几何体高维的向量和矩阵,。在文献[3]中，针对这一专题作了专门的存储结构差别很大，但是它们在某些行为上表现出共同性，例如这些几何体的绘制、偏移等，可以把这些共同的行为抽的论述，并且提出了表达式模板(ExpressionTemplate)的概象出来，以公有函数接口的形式放在一个虚基类里面，让子念，使得浮点数组向量的运算既能保持优雅的结构，又能够类继承并实现这些接口。在这种情况下，相对于模板技术，[3]获得高效率。总而言之，当我们的程序对效率要求很高虚函数是合适的。原因是，我们的程序响应用户的输入，操的情况下，可纵几何体的时候，这些几何体的具体类型完全是在程序运行以考虑使用模板多态。期决定的，而不是在编译期决定的。3结论所以，如果我们的算法或者构件表现出共同的行为，而在C++中，模板多态和虚函数多态是可以共存的，因为(下转第87页)提示生成后的替换策略LRU+Hint与LRU相比，失效率的降到的LRU+Hint替换，与LRU替换相比在全相联Cache中低比率。Cache失效率最高降低12.98%，平均降低5.69%,在4-组相联Cache中，Cache失效率最高降低13.31%，平均降低5.77%。LRU5结论LRU+HintOPTEPIC体系结构中Cache提示机制使编译器可以直接控制1412Cache替换，从而改善Cache行为。本文提出了一个适用于108所有程序的基于OPTCache替换Profiling的静态Cache提示64生成方法，本方法使程序中产C生ache污染的大部分存储引2missrate(%)0用能尽早地被替换出Cache，从而有效改善Cache行为，降vprgccmcfenogapgzip低Cache失效率。bzip2twolfcraftyparserperlbmkvortex为了对LRU+HintCache替换进行仿真，我们对benchmarksSimpleScalar工具集进行了扩展，然后对SPEC2000Int测试图2全相联Cache中各替换策略的失效率程序进行了Cache行为仿真。结果显示，与LRU替换策略相比，我们的LRU+Hint替换对于全相联、4-组相联Cache分LRULRU+Hint别能降低Cache失效率最大到12.98%、13.31%。OPT参考文献161McKinleyKS,TemamO.QuantifyingLoopNestLocalityUsing1412Spec’95andthePerfectBenchmarks.ACMTransactionson108ComputerSystems(TOCS),1999,17(4):288-336642KathailV,SchlanskerMS,RauBR.HPL-PDArchitecture2missrate(%)Specification:Version1.1.TechnicalReportHPL-93-80(R.1),0Hewlett-packard,2000-02gzip3BeladyLA.AStudyofReplacementAlgorithmsforVirtualStoragevprComputers.IBMSystemsJournal,1966,5(2):78-101banchmarksgcc4GhoshS,MartonosiM,MalikS.CacheMissEquations:AnAnalytical图3一组相联Cache中各替换策略的失效率mcfRepresentationofCacheMisses.In:Proc.ofInt’lConf.oncraftyFullass.Supercomputing,1997-07parser4-wayass.5FraguelaBB,DoalloR,ZapataEL.AutomaticAnalyticalModelingenofortheEstimationofCacheMisses.In:InternationalConferenceon14.00%perlbmk12.00%ParallelArchitecturesandCompilationTechniques(PACT’99),199910.00%gap8.00%6ChatterjeeS,ParkerE,HanlonPJ,etal.ExactAnalysisoftheCache6.00%vortexBehaviorofNestedLoops.In:ACMSIGPLAN’01Conferenceon4.00%bzip22.00%ProgrammingLanguageDesignandImplementation(PLDI’01),2001:0.00%missesreductiontwolf286-297vprgccmcfeno7BurgerD,Doug,AustinTM.TheSimpleScalarToolSet,Version2.gzipbzip2twolfcraftyparservortexperlbmkComputerScienceDepartment,UniversityofWisconsin-MadisonbenchmarksgapTN-1342.In:ProceedingsofMICRO-28,1995-11:93-103图4LRU+Hint与LRU失效率的比较图4显示，基于OPT替换Profiling的Cache提示生成得~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(上接第73页)使用模板多态,(4)该文的程序对效率要求很高的情况下，可考虑使用模板多态。C++同时支持这两种编程范型的代码程序。它们的本质不同点在于:模板是静态的技术，在编译期决定,虚函数更侧重参考文献于运行期，适合描述动态的行为。虚函数通过间接层增加编1SutterH.於春景译.MoreExceptionalC++中文版.武汉:华中科技译器防火墙,模板取消间接层增加效率。模板有自己的使用大学出版社,20022AusternMH.侯捷译.泛型编程与STL.北京:中国电力出版社,范围，一般来说，在下面的情况下，更适合于使用模板，而2003不是虚函数:(1)当该文的程序使用了对象本身的集合，而不3VandevoordeD,JosuttisNM.C++Templates.北京:中国电力出版是对象指针的集合，而这些对象的行为表现出共同性的时候，社,2004可考虑使用模板多态,(2)如果该文的算法或者构件表现出共4AlexandrescuA.侯捷,於春景译.C++设计新思维—泛型编程与同的行为，而这些行为是可以在编译期决定，可以考虑使用设计模式之应用.武汉:华中科技大学出版社,2003模板多态,(3)如果该文的代码需要表现出某种策略的选择，5MeyersS.侯捷译.MoreEffectiveC++.北京:中国电力出版社,这种策略依赖于客户端代码的编译前配置,而如果不考虑这2003些策略，代码表现出很大的共同性，在这种情况下可以考虑—87—