第十八章標(biāo)準(zhǔn)模板庫(kù)

第十八章標(biāo)準(zhǔn)模板庫(kù)第1頁(yè)，共13頁(yè)，2023年，2月20日，星期三課程內(nèi)容安排標(biāo)準(zhǔn)庫(kù)模板庫(kù)算法容器迭代器綜合練習(xí)思考和習(xí)題第2頁(yè)，共13頁(yè)，2023年，2月20日，星期三標(biāo)準(zhǔn)模板庫(kù)STL是最新的C++標(biāo)準(zhǔn)函數(shù)庫(kù)中的一個(gè)子集，這個(gè)龐大的子集占據(jù)了整個(gè)庫(kù)的大約80%的分量。而作為在實(shí)現(xiàn)STL過(guò)程中扮演關(guān)鍵角色的模板則充斥了幾乎整個(gè)C++標(biāo)準(zhǔn)函數(shù)庫(kù)。STL提供了一系列具有良好結(jié)構(gòu)的通用C++組件，這些組件緊密協(xié)作，提供強(qiáng)大的功能。標(biāo)準(zhǔn)庫(kù)的設(shè)計(jì)必須確保所有的模板算法既能操作庫(kù)中的數(shù)據(jù)類(lèi)型，也能操作C++固有的數(shù)據(jù)類(lèi)型。第3頁(yè)，共13頁(yè)，2023年，2月20日，星期三第一個(gè)STL程序該范例中調(diào)用了STL中的函數(shù)，是第一個(gè)使用STL的程序，其實(shí)現(xiàn)功能如下。第4頁(yè)，共13頁(yè)，2023年，2月20日，星期三代碼清單1 #include<vector> //包含頭文件2 #include<iostream>3 intmain()4 {5 std::vector<double>a; //定義數(shù)據(jù)變量6 std::vector<double>::const_iteratori; //定義變量7 a.push_back(1); //調(diào)用STL中函數(shù)8 a.push_back(2);9 a.push_back(3);10 a.push_back(4);11 a.push_back(5); //調(diào)用STL中函數(shù)12 for(i=a.begin();i!=a.end();++i) //循環(huán)輸出13 {14 std::cout<<(*i)<<std::endl; //輸出該容器內(nèi)所有元素15 }16 return0;17 }第5頁(yè)，共13頁(yè)，2023年，2月20日，星期三STL的組成STL的代碼從廣義上講分為三類(lèi)：algorithm（算法）、container（容器）和iterator（迭代器），幾乎所有的代碼都采用了模板類(lèi)和模版函數(shù)的方式，這相比于傳統(tǒng)的由函數(shù)和類(lèi)組成的庫(kù)來(lái)說(shuō)提供了更好的代碼重用機(jī)會(huì)。簡(jiǎn)單來(lái)說(shuō)，其關(guān)系如圖18-3所示。

第6頁(yè)，共13頁(yè)，2023年，2月20日，星期三算法算法部分主要由頭文件<algorithm>，<numeric>和<functional>組成。<algorithm>是所有STL頭文件中最大的一個(gè)，它是由一大堆模版函數(shù)組成的。一般可以認(rèn)為每個(gè)函數(shù)在很大程度上都是獨(dú)立的，其中常用到的功能范圍涉及到比較、交換、查找、遍歷操作、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等等。頭文件<numeric>體積很小，只包括幾個(gè)在序列上面進(jìn)行簡(jiǎn)單數(shù)學(xué)運(yùn)算的模板函數(shù)，包括加法和乘法在序列上的一些操作。頭文件<functional>中則定義了一些模板類(lèi)，用以聲明函數(shù)對(duì)象。第7頁(yè)，共13頁(yè)，2023年，2月20日，星期三容器容器部分主要由頭文件<vector>，<list>，<deque>，<set>，<map>，<stack>和<queue>組成。對(duì)于常用的一些容器和容器適配器（可以看作由其它容器實(shí)現(xiàn)的容器），可以通過(guò)下表18-1總結(jié)一下它們和相應(yīng)頭文件的對(duì)應(yīng)關(guān)系。第8頁(yè)，共13頁(yè)，2023年，2月20日，星期三數(shù)據(jù)結(jié)構(gòu)描述實(shí)現(xiàn)頭文件向量(vector)連續(xù)存儲(chǔ)的元素<vector>列表(list)由節(jié)點(diǎn)組成的雙向鏈表，每個(gè)結(jié)點(diǎn)包含著一個(gè)元素<list>雙隊(duì)列(deque)連續(xù)存儲(chǔ)的指向不同元素的指針?biāo)M成的數(shù)組<deque>集合(set)由節(jié)點(diǎn)組成的紅黑樹(shù)，每個(gè)節(jié)點(diǎn)都包含著一個(gè)元素，節(jié)點(diǎn)之間以某種作用于元素對(duì)的謂詞排列，沒(méi)有兩個(gè)不同的元素能夠擁有相同的次序<set多重集合(multiset)允許存在兩個(gè)次序相等的元素的集合<set>棧(stack)后進(jìn)先出的值的排列<stack>隊(duì)列(queue)先進(jìn)先出的執(zhí)的排列<queue>優(yōu)先隊(duì)列(priority_queue)元素的次序是由作用于所存儲(chǔ)的值對(duì)上的某種謂詞決定的的一種隊(duì)列<queue>映射(map)由{鍵，值}對(duì)組成的集合，以某種作用于鍵對(duì)上的謂詞排列<map>多重映射(multimap)允許鍵對(duì)有相等的次序的映射<map>第9頁(yè)，共13頁(yè)，2023年，2月20日，星期三迭代器迭代器實(shí)際上是一種泛化指針，如果一個(gè)迭代器指向了容器中的某一成員，那么迭代器將可以通過(guò)自增自減來(lái)遍歷容器中的所有成員。迭代器是聯(lián)系容器和算法的媒介，是算法操作容器的接口，如圖18-10所示。第10頁(yè)，共13頁(yè)，2023年，2月20日，星期三綜合練習(xí)該范例求出范圍在2~N中的所有素?cái)?shù)，其中N在程序運(yùn)行時(shí)由鍵盤(pán)輸入。第11頁(yè)，共13頁(yè)，2023年，2月20日，星期三代碼清單1 #include<iostream>2 #include<iomanip> //包含I/O流控制頭文件3 #include<vector> //包含向量容器頭文件4 usingnamespacestd; //使用存儲(chǔ)過(guò)程5 voidmain() //主函數(shù)6 {7 vector<int>A(10); //定義向量對(duì)象8 intn; //定義整型變量9 intprimecount=0,i,j; //定義變量并初始化10 cout<<"Enteravalue>=2asupperlimit:"; //輸入提示11 cin>>n; //接收n的輸入12 A[primecount++]=2; //賦值13 for(i=3;i<n;i++) //循環(huán)輸出素?cái)?shù)14 {15 if(primecount==A.size()) //到達(dá)向量大小16 A.resize(primecount+10); //調(diào)用函數(shù)重新設(shè)置向量大小17 if(i%2==0) //不是素?cái)?shù)18 continue; //繼續(xù)循環(huán)19 j=3; //賦初值20 while(j<=i/2&&i%j!=0) //循環(huán)判斷是否素?cái)?shù)21 j+=2; //變量遞加222 if(j>i/2) //是素?cái)?shù)23 A[primecount++]=i; //寫(xiě)入向量中24 }25 for(i=0;i<primecount;i++) //輸出素?cái)?shù)26 {27 cout<<setw(5)<<A[i]; //設(shè)置輸出格式并輸出28 f((i+1)%10==0) //每輸出10個(gè)數(shù)換行一次29 cout<<endl; //輸出換行30 }31 cout<<endl; //輸出換行32 }第12頁(yè)，共13頁(yè)，2023年