模板和多态性ppt课件

1、CHAPTER 11 Templates and polymorphism 模板与多态性模板与多态性IntroductionIn this chapter, we explore the two major C+ mechanisms for providing polymorphic capabilities. The first method is via class and function templates. The second method is via virtual member functions.本章讨论本章讨论 C+多态性的两种重要机制。第一种方法是类多态性的两种重要机

2、制。第一种方法是类和函数模板；第二种是虚成员函数。和函数模板；第二种是虚成员函数。The core of object-oriented-programming :objects, classes, inheritance and polymorphismSimple polymorphism the choice is made at compile time.function and operator overloading ; templateTrue polymorphism the choice is to delay until run time.virtual function1

3、1.1 GENERIC ACTIONS AND TYPES 通用行为与类型通用行为与类型 Overloaded functions are normally used to perform similar operations on different types of data. If the operations are identical for each type, this may be using function templates. Function template declares the formal parameter for any type. 11.2 FUNCTI

4、ON TEMPLATES 函数模板函数模板 All function templates definitions begin with the keyword template followed by a list of formal parameters to the function template enclosed in angle brackets. 11.2 FUNCTION TEMPLATES 函数模板函数模板 template All function templates definitions begin with the keyword template followed

5、by a list of formal parameters to the function template enclosed in angle brackets. 11.2 FUNCTION TEMPLATES 函数模板函数模板 template Keyword All function templates definitions begin with the keyword template followed by a list of formal parameters to the function template enclosed in angle brackets. 11.2 F

6、UNCTION TEMPLATES 函数模板函数模板 template Template parametersAll function templates definitions begin with the keyword template followed by a list of formal parameters to the function template enclosed in angle brackets. 11.2 FUNCTION TEMPLATES 函数模板函数模板 template KeywordMeansany built-in type or user-defin

7、ed type”New keyword: typename All function templates definitions begin with the keyword template followed by a list of formal parameters to the function template enclosed in angle brackets. 11.2 FUNCTION TEMPLATES 函数模板函数模板 template Each template parameter must be used in the function description./ E

8、xample14-1#include template T max ( const T &a , const T &b ) return a b ? a : b ; void main ( ) cout max ( 3 , 5 ) is max ( 3 , 5 ) endl ; cout max ( y , e ) is max ( y , e ) endl ; cout max ( 9.3 , 0.5 ) is max ( 9.3 , 0.5 ) endl ; function template/ Example14-1#include template T max ( co

9、nst T &a , const T &b ) return a b ? a : b ; void main ( ) cout max ( 3 , 5 ) is max ( 3 , 5 ) endl ; cout max ( y , e ) is max ( y , e ) endl ; cout max ( 9.3 , 0.5 ) is max ( 9.3 , 0.5 ) endl ;The compiler to instantiate template function for which type parameter T is int/ Example14-1#incl

10、ude template T max ( const T &a , const T &b ) return a b ? a : b ; void main ( ) cout max ( 3 , 5 ) is max ( 3 , 5 ) endl ; cout max ( y , e ) is max ( y , e ) endl ; cout max ( 9.3 , 0.5 ) is max ( 9.3 , 0.5 ) endl ;type parameter T is char/ Example14-1#include template T max ( const T &am

11、p;a , const T &b ) return a b ? a : b ; void main ( ) cout max ( 3 , 5 ) is max ( 3 , 5 ) endl ; cout max ( y , e ) is max ( y , e ) endl ; cout max ( 9.3 , 0.5 ) is max ( 9.3 , 0.5 ) endl ;type parameter T is double/ Example14-2template void InsertionSort ( T A , int n ) for ( int i = 1 ; i n ;

12、 i + ) if ( Ai 0 & Aj-1 V ) ;Aj = V ; For exampletemplate T max ( T a , T b ) return a b ? a : b ; void f ( int i , char c ) max ( i , i ) ;/ ok max ( c , c ) ;/ ok max ( i , c ) ;/ error max ( c , i ) ;/ errorOverloading Template Functions Overloading Template Functions template T max ( T a , T

13、 b ) return a b ? a : b ; int max ( int a , int b ) / overload template function return a b ? a : b ; void f ( int i , char c ) max ( i , i ) ; max ( c , c ) ; max ( i , c ) ;/ ok max ( c , i ) ;/ ok The compiler performs a matching process to determine what function to call when a function in invok

14、ed. First, the compiler to find and use a precise match in which the function names and argument types match perfectly with those of the function call. If this fails, the compiler checks if a function template is available that can be used to generate a template function with a perfectly match of fu

15、nction names and argument types. If such a function template is not found, the compiler generates and use the appropriate template function.Class templates are called parameterized types (参数化类型) because they require one or more type parameters to specify how to customize a “generic class” template t

16、o form a specific template class. 11.3 CLASS TEMPLATES 类模板类模板 Any member function is defined except class template by the header:template 11.4 A SIMPLE CLASS USING A CLAS TEMPLATE 使用类模板的一个简单类表使用类模板的一个简单类表/ Example14-3.h template class Array public : Array ( int s ) ; virtual Array ( ) ; virtual cons

17、t T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;template Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete element ; template const T& Array : Entry ( int index ) const retu

18、rn element index ; template void Array : Enter ( int index , const T& value) element index = value ; / Example14-3.h template class Array public : Array ( int s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; priva

19、te: int size ; T * element ; ;template Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete element ; template const T& Array : Entry ( int index ) const return element index ; template void Array : Enter ( int index , const T& value) element index = va

20、lue ; Define class template / Example14-3.h template class Array public : Array ( int s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;template Array : Array ( int s ) size = s ; ele

21、ment = new T size ; template Array : Array ( ) delete element ; template const T& Array : Entry ( int index ) const return element index ; template void Array : Enter ( int index , const T& value) element index = value ; Virtual function/ Example14-3.h template class Array public : Array ( i

22、nt s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;template Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete element ; template const T&am

23、p; Array : Entry ( int index ) const return element index ; template void Array : Enter ( int index , const T& value) element index = value ; Define member function/ Example14-3.h template class Array public : Array ( int s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ;

24、 virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;template Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete element ; template const T& Array : Entry ( int index ) const return element index ; template void Arr

25、ay : Enter ( int index , const T& value) element index = value ; / Example14-3.h template class Array public : Array ( int s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;templa

26、te Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete element ; template const T& Array : Entry ( int index ) const return element index ; template void Array : Enter ( int index , const T& value) element index = value ; / Example14-3.h template class

27、 Array public : Array ( int s ) ; virtual Array ( ) ; virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T & value ) ; private: int size ; T * element ; ;template Array : Array ( int s ) size = s ; element = new T size ; template Array : Array ( ) delete elem

28、ent ; template const T& Array : Entry ( int index ) const return element index ; template void Array : Enter ( int index , const T& value) element index = value ; / Example14-3.cpp # include # include Example14-3.hvoid main ( ) Array a ( 5 ) ; for ( int i = 0 ; i 5 ; i + ) a . Enter ( i , i

29、) ; for ( i = 0 ; i 5 ; i + ) cout a . Entry ( i ) t ;To instantiate template classTemplates and inheritance relate in several ways: A class template can be derived from a template class. 类模板可以从模板类派生类模板可以从模板类派生 A class template can be derived from a non-template class. 类模板可以从非模板类派生类模板可以从非模板类派生 A tem

30、plate class can be derived from a class template. 模板类可以从类模板派生模板类可以从类模板派生 A non-template class can be derived from a class template. 非模板类可以从类模板派生非模板类可以从类模板派生Templates and Inheritance ExampleDerived a new class template from Array class template, it can declare the low-border and length of array.Templ

31、ates and Inheritance / Example14-4.h #include Example14-3.h template class BoundArray : public Array public : BoundArray ( int s , int m = 0 ) ;/ length and low-border virtual const T& Entry ( int index ) const ; virtual void Enter ( int index , const T& value ) ; private: int min ; ;templat

32、e BoundArray : BoundArray ( int s , int m ) : Array ( s ) min = m ; template const T& BoundArray : Entry ( int index ) const return Array : Entry ( index - min ) ; template void BoundArray : Enter ( int index , const T & value ) Array : Enter ( index - min , value ) ; / Example14-4.cpp # inc

33、lude # include Example14-4.h void main ( ) BoundArray b ( 5 , 1 ) ; for ( int i = 1 ; i = 5 ; i + ) b . Enter ( i , i ) ; for ( i = 1 ; i = 5 ; i + ) cout b . Entry ( i ) t ; cout endl ;/ Example14-5 # include # include Example14-3.h template void fun ( const Array & x , int index ) cout x . Ent

34、ry ( index ) endl ; void main ( ) Array a ( 10 ) ; float v ; cin v ; a . Enter ( 5 , v ) ; fun ( a , 5 ) ;Using class templates parameters / Example14-5 # include # include Example14-3.h template void fun ( const Array & x , int index ) cout x . Entry ( index ) endl ; void main ( ) Array a ( 10

35、) ; float v ; cin v ; a . Enter ( 5 , v ) ; fun ( a , 5 ) ;Using class templates parameters Template function/ Example14-5 # include # include Example14-3.h template void fun ( const Array & x , int index ) cout x . Entry ( index ) endl ; void main ( ) Array a ( 10 ) ; float v ; cin v ; a . Ente

36、r ( 5 , v ) ; fun ( a , 5 ) ;Using class templates parameters Class template parameter/ Example14-5 # include # include Example14-3.h template void fun ( const Array & x , int index ) cout x . Entry ( index ) endl ; void main ( ) Array a ( 10 ) ; float v ; cin v ; a . Enter ( 5 , v ) ; fun ( a ,

37、 5 ) ;Using class templates parameters Each template class instantiated from a class template has its own copy of each static data member of the class template; all objects of the template class share that one static data member. 从类模板实例化的每个模板类都有自己的类模板的static数据成员，该模板类 的所有对象共享一个static数据成员。 As with sta

38、tic data member of non-template classes, static data members of template classes must be initialized at file scope. 和非模板类一样，模板类的static数据成员也应在文件范围内初始化。 Each template class gets its own copy of the class templates static data members. 每个模板类有该类模板的static数据成员副本。Templates and Static Members SeqList ADT as

39、 a doubly linked list 11.5 SEQUENTIAL LISTS 顺序表顺序表2864templateclass SeqItem protected: SeqItem(const T &val) : ItemValue(val), Predecessor(0), Successor(0) ; private: T ItemValue;/ element value SeqItem *Predecessor;/ pointer to previous element SeqItem *Successor;/ pointer to next element;The c

40、onstructor of SeqItem classNoteIt is a protected member functionSeqItem : SeqItem(const T &val) : ItemValue(val), Predecessor(0), Successor(0) ;val*this2864templateclass SeqItem protected: SeqItem(const T &val) : ItemValue(val), Predecessor(0), Successor(0) ; private: T ItemValue;/ element v

41、alue SeqItem *Predecessor;/ pointer to previous element SeqItem *Successor;/ pointer to next element;11.5.1 SeqItem class template templateclass SeqList friend class SeqIterator; friend class ConstSeqIterator; public: typedef SeqIterator iterator; typedef ConstSeqIterator const_iterator; SeqList();S

42、eqList(); int size() const;T& front(); const T& front() const; T& back(); const T& back() const; iterator begin(); const_iterator begin() const;iterator end(); const_iterator end() const;void push_back(const T &val); void pop_front();void display(ostream &sout) const; iterato

43、r insert(iterator p, const T &val); iterator erase(iterator p);void clear(); SeqList& operator=(const SeqList &S); SeqList(const SeqList &S); private: SeqItem *Front; / pointer to first element SeqItem *Back; / pointer to last element int ListLength; / number of elements;class SeqLis

44、t/ default SeqList constructortemplateSeqList:SeqList() : ListLength(0), Front(0), Back(0) / no code needed/ SeqList destructor templateSeqList:SeqList() clear();this - Frontthis - ListLength 0this - Back 11.5.2 SeqList member function basics / size(): return size of list templateint SeqList:size()

45、const return ListLength;2864ListLength = 4FrontBack/ size(): return size of list templateint SeqList:size() const return ListLength;2864FrontBack/ front(): return reference to first element in list templateT& SeqList:front() assert(size() != 0);return Front-ItemValue;2864ListLength = 4FrontBack/

46、 front(): return const reference to first element in list templateconst T& SeqList:front() const assert(size() != 0);return Front-ItemValue;864FrontBack/ front(): return reference to first element in list templateT& SeqList:front() assert(size() != 0);return Front-ItemValue;/ front(): return

47、 const reference to first element in list templateconst T& SeqList:front() const assert(size() != 0);return Front-ItemValue;ListLength = 4/ back(): return reference to last element in list templateT& SeqList:back() assert(size() != 0);return Back-ItemValue;2864FrontBack/ back(): return const

48、 reference to last element in list templateconst T& SeqList:back() const assert(size() != 0);return Back-ItemValue;ListLength = 4/ back(): return reference to last element in list templateT& SeqList:back() assert(size() != 0);return Back-ItemValue;2864FrontBack/ back(): return const referenc

49、e to last element in list templateconst T& SeqList:back() const assert(size() != 0);return Back-ItemValue;ListLength = 4/ begin(): create iterator pointing to first elementtemplateSeqIterator SeqList:begin() return SeqIterator (this, Front);2864FrontBackbegin()ListLength = 4/ end(): create itera

50、tor pointing to sentineltemplateSeqIterator SeqList:end() return SeqIterator(this, 0);2864FrontBackend()ListLength = 4/ push_back(): add value to end of listtemplatevoid SeqList:push_back(const T &val) insert(end(), val);2864FrontBackListLength = 4/ push_back(): add value to end of listtemplatev

51、oid SeqList:push_back(const T &val) insert(end(), val);2864FrontBackval/ pop_front(): erase value from front of listtemplatevoid SeqList:pop_front() erase(begin();2864FrontBackListLength = 4/ pop_front(): erase value from front of listtemplatevoid SeqList:pop_front() erase(begin();864FrontBack/

52、display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;2864FrontBackListLength = 4 2 8 6 4 Output11.5.3 Member function display() / display(): display listtemplate void SeqList:display(ostream &

53、;sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;2864FrontBackListLength = 411.5.3 Member function display() / display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout Ite

54、mValue;sout ;2864FrontBackListLength = 4 Output11.5.3 Member function display() / display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;2864FrontBackListLength = 4 Output11.5.3 Member function dis

55、play() / display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;2864FrontBackListLength = 4 Output11.5.3 Member function display() / display(): display listtemplate void SeqList:display(ostream &am

56、p;sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;2864FrontBackListLength = 4 2Output11.5.3 Member function display() 2864FrontBackListLength = 4 2Output/ display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr

57、 = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;11.5.3 Member function display() 2864FrontBackListLength = 4 2 8Output/ display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;11.5.3 Member

58、 function display() 2864FrontBackListLength = 4 2 8 6Output/ display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;11.5.3 Member function display() 2864FrontBackListLength = 4 2 8 6 4Output/ displ

59、ay(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;11.5.3 Member function display() 2864FrontBackListLength = 4 2 8 6 4Output/ display(): display listtemplate void SeqList:display(ostream &sout)

60、 const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;11.5.3 Member function display() 2864FrontBackListLength = 4 2 8 6 4Output/ display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor)

61、sout ItemValue;sout ;11.5.3 Member function display() 2864FrontBackListLength = 4 2 8 6 4 Output/ display(): display listtemplate void SeqList:display(ostream &sout) const sout ;for (SeqItem *Ptr = Front; Ptr; Ptr = Ptr-Successor) sout ItemValue;sout ;/ insert(): add an item to the listtemplateSeqIter