C程序设计教学课件：CHAPTER 11 TEMPLATES AND THE STANDARD TEMPLATE LIBRARY

1、C+ Programming CHAPTER 11 TEMPLATES AND THE STANDARD TEMPLATE LIBRARY111.1 Template Basics11.2 The Standard Template Library2This chapter examines template classes, another C+ mechanism for code reuse, and also introduces the Standard Template Library (STL), a powerful C+ library of template classes

2、 and functions.311.1 Template BasicsTemplate ClassTemplate ClassA template class is created with at least one class parameter, a symbol that serves as a placeholder for a specific data type. Syntax:template class TemplateClass /411.1 Template BasicsTemplate Class#include #include #include template c

3、lass array public: array(int size); array()delete a; T get(int i); void set(T t, int i); protected: int len; T * a;template array:array(int size) int i; len=size; a=new Tsize; if(!a) coutcan not allocate for array.n; exit(1); for(i=0;isize;i+) ai=0;511.1 Template BasicsTemplate Classtemplate T array

4、: get(int i) if(i0&ilen) return ai;else return 0;template void array:set(T t, int i) if(i0&ilen) ai = t;611.1 Template BasicsTemplate Classvoid main() array intob(10); array doubleob(5); int i; for(i=0;i10;i+) intob.set(i+1,i); for(i=0;i10;i+) coutintob.get(i),; coutendl; for(i=0;i5;i+) doubleob.set

5、(double)(i+1)*3.14,i); for(i=0;i5;i+) coutdoubleob.get(i) ,; coutendl;711.1 Template BasicsTemplate ClassOutput:0,2,3,4,5,6,7,8,9,10,0 ,6.28 ,9.42 ,12.56 ,15.7 ,811.1 Template BasicsTemplate ClassRemark:A template class may have more than one class parameter, in which case the class parameters are s

6、eparated by commas.911.1 Template BasicsTemplate ClassExample:templateclass Samplepublic:T2 m( T3 p)/private:T1 x ;1011.2 The Standard Template LibraryThe Standard Template Library is part of the standard C+ Library. STLs template classes provide C+ with data structures, that is, high-level data typ

7、es such as stacks, together with appropriate operations on these high-level data types, such as pushes and pops.1111.2 The Standard Template LibraryContainers, Algorithms, and IteratorsContainers, Algorithms, and Iterators STLs three basic components are containers, algorithms, and iterators. An STL

8、 container is a collection of objects. Examples are vectors, stacks, queues, deques, lists, sets, and maps. 1211.2 The Standard Template LibraryContainers, Algorithms, and IteratorsAn STL algorithm is a function for processing a containers contents. Examples are functions that copy, sort, search, me

9、rge, and permute containers. An STL iterator is a mechanism for accessing the objects in a container one at a time.1311.2 The Standard Template LibraryContainer BasicsContainer BasicsSTL has seven basic containers divided into two groups, sequential and associative.Headers:,1411.2 The Standard Templ

10、ate LibraryContainer BasicsContainerTypeDescriptionlistSequentialBidirectional linked list of elementsvectorSequentialArray that grows and shrinks as neededdequeSequentialArray with efficient insertions/deletions at either endsetAssociativeCollecton of nonduplicate keysmultisetAssociativeA set with

11、duplicates allowedmapAssociativeCollection of nonduplicate elements with access by keymultimapAssociativeA map with duplicates allowed1511.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listvector, deque, and listvectorA vector grows and shrinks automatically to meet

12、its own storage needs.Example:vector d(1000);This code segment defines a vector with an initial size of 1000. The size still increases automatically if required.16Example:#include #include using namespace std;int main()int i; vector nums;nums.insert(nums.begin(), -999);nums.insert(nums.begin (),14);

13、 nums.insert(nums.end(), 59);for(i=0; inums.size(); i+) coutnumsi ;coutendl;nums.erase(nums.begin() );nums.erase(nums.begin() );for(i=0; inums.size(); i+) coutnumsi ;return 0;Output:14 -999 5959 1711.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listThe begin method

14、returns an iterator thatPoints to a containers first element, if the container is not empty.Points just beyond the end of the container, if the container is empty. The method end returns an iterator thatPoints just beyond the end of the container.1811.2 The Standard Template LibraryBasic Sequential

15、Containers: vector, deque, and listThe erase method, like the insert method, can access either end of the vector.The size method returns the vectors current size.We can access the object in vector as an array.1911.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listdeq

16、ueA deque seems almost indistinguishable from a vector.20Example:#include #include using namespace std;int main()int i; deque nums;nums.insert(nums.begin(), -999); /-999nums.insert(nums. begin (),14); /14 -999nums.insert(nums.end(), 59); /14 -999 59for(i=0; inums.size(); i+) coutnumsi ; /14 -999 59c

17、outendl;nums.erase(nums.begin() ); /-999 59nums.erase(nums.begin() ); /59for(i=0; inums.size(); i+) coutnumsi ; /59return 0;Output:14 -999 5959 2111.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listRemark:A vector and deque differ in their underlying implementation,

18、 in articular with respect to insertions and deletions.2211.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listListA list is a bidirectional linked list of elements.23Example:#include #include #include using namespace std;void dump( list l)list:const_iterator it;it=l.

19、begin();while( it!= l.end() )cout*itendl;it+;24int main()list names;names.insert(names.begin(), Kamiko);names.insert(names.end(),Andre); names.insert(names.begin(), Chengwen);names.insert(names.begin(), Maria);dump(names);names.reverse();coutendl;dump(names);return 0;Output:MariaChengwenKamikoAndreA

20、ndreKamikoChengwenMaria2511.2 The Standard Template LibraryBasic Sequential Containers: vector, deque, and listRemark:For the containers:The iterator is used to access the containers elements.The const_iterator is used if the iteration does not change any of the containers elements.2611.2 The Standa

21、rd Template LibraryBasic Sequential Containers: vector, deque, and listExample:vector l(10);vector:iterator it;it=l.begin();while( it!=l.end()By this way, we can loop safely without knowing how many elements happen to be in the vector.2711.2 The Standard Template LibraryBasic Sequential Containers:

22、vector, deque, and listOperationVectordequelistInsert/erase at beginningLinearConstantConstantInsert/erase at endConstantConstantConstantInsert/erase at middleLinearLinearConstantAccess first elementConstantConstantConstantAccess last elementConstantConstantConstantAccess middle elementConstantConst

23、antLinear2811.2 The Standard Template LibraryBasic Associative Containers: set, multiset, map, and multimapset, multiset, map, and multimap A set is a collection of zero or more nonduplicate, unordered elements called keys. Example:jobs, gates, ellisonA multiset is a set that allows duplicate keys.2

24、911.2 The Standard Template LibraryBasic Associative Containers: set, multiset, map, and multimapA map is a collection of zero or more nordered pairs; in each pair, one element is a nonduplicate key and the other is a value associated with the key.Example:(jobs, apple), (gates, microsoft), (ellison,

25、 oracle)In each pair, the first element such as gates is the key associated with a value such as microsoft.A multimap is a map that allows duplicate keys.30setExample:#include #include using namespace std;int main() set s; s.insert(-999); s.insert(18); s.insert(321); s.insert(-999);/not inserted set

26、:const_iterator it; it=s.begin(); while( it!=s.end() ) cout*it+endl;/-999 18 321int key;coutkey;it=s.find( key );if( it=s.end() )/not found coutkey is not in set. endl;else coutkey is in set. endl; return 0;3111.2 The Standard Template LibraryBasic Associative Containers: set, multiset, map, and mul

27、timapThe set class overloads the insert method so that it can be invoked in similar fashion to a vectors version.set s;s.insert(s.begin(), 66 );s.insert( s.end(), 99);s.insert( 123 );3211.2 The Standard Template LibraryBasic Associative Containers: set, multiset, map, and multimapmapAn STL map is an

28、 association list, that is, a list that associates a key with a value.33#include #include #include using namespace std;int main() map m; mzero=0; mone=1; mtwo=2; mthree=3; mfour=4; mfive=5; msix=6; mseven=7; meitht=8; mnine=9; cout mthreeendl mfiveendl msevenendl; return 0;Output:357In this code seg

29、mentmap m;string and int are the data types of the key and the value, respectively.3411.2 The Standard Template LibraryAlgorithmsAlgorithmsSTL has a rich assortment of algorithms for processing containers, such as sorting and searching, numerical processing, set operations, copying, and so forth.Hea

30、ders:, 3511.2 The Standard Template LibraryAlgorithmsAlgorithms:reversegeneratereplace_ifsortfor_each3611.2 The Standard Template LibraryAlgorithmsgenerate, repalce_if, sort, and for_eachGiven the definition of vvector v(10);The program uses the generate algorithm to populate v with random integers:

31、generate(v.begin(), v.end(), rand);3711.2 The Standard Template LibraryAlgorithmsreplace_if(v.begin(), v.end(), odd, 0);Every element from v.begin() to v.end() is tested by the function odd, and the function odd is invoked for each item in v. If odd returns true, the item is replaced by 0.3811.2 The

32、 Standard Template LibraryAlgorithmssort(v.begin, v.end(), comp);The function comp is optional. If omitted, the vector would be sorted in ascending order.sort(v.begin(), v.end() );This means the vector v will be sorted by operator .3911.2 The Standard Template LibraryAlgorithmsfor_each(v.begin(), v.

33、end(), dump);This code segment uses for_each instead of a loop.Every element in the vector v will invoke the function dump.40algorithmExample:#include #include #include using namespace std;void dump( int i) coutii2;int main() vector v(5); generate(v.begin(), v.end(), rand); for_each(v.begin(), v.end

34、(), dump); cout-endl; replace_if(v.begin(),v.end(),odd,0); for_each(v.begin(), v.end(), dump); cout-endl; sort(v.begin(), v.end(), comp); for_each(v.begin(), v.end(), dump); return 0;414211.2 The Standard Template LibraryAlgorithmsAlgorithms such as generate, for_each and repalce_if have build_in it

35、eration through their use of iterators. This iterators themselves are intuitive:v.begin() /start at beginning v.end() /go to the end43Summarize Template ClassBasic Sequential Containers: vector, deque, and listBasic Associative Containers: set, multiset, map, and multimapAlgorithms44/ name:example2_1.cpp/ alias:Rubish#include #include int compare(const void *arg1, const void *arg2);void main(void)const int max_size = 10;/ 数组允许元素的最大个数int nummax_size;/ 整型数组 / 比较两个数的大小，/ 如果*(int