第十八章標準模板庫

第十八章標準模板庫第一頁，共十三頁，編輯于2023年，星期五課程內(nèi)容安排標準庫模板庫算法容器迭代器綜合練習(xí)思考和習(xí)題第二頁，共十三頁，編輯于2023年，星期五標準模板庫STL是最新的C++標準函數(shù)庫中的一個子集，這個龐大的子集占據(jù)了整個庫的大約80%的分量。而作為在實現(xiàn)STL過程中扮演關(guān)鍵角色的模板則充斥了幾乎整個C++標準函數(shù)庫。STL提供了一系列具有良好結(jié)構(gòu)的通用C++組件，這些組件緊密協(xié)作，提供強大的功能。標準庫的設(shè)計必須確保所有的模板算法既能操作庫中的數(shù)據(jù)類型，也能操作C++固有的數(shù)據(jù)類型。第三頁，共十三頁，編輯于2023年，星期五第一個STL程序該范例中調(diào)用了STL中的函數(shù)，是第一個使用STL的程序，其實現(xiàn)功能如下。第四頁，共十三頁，編輯于2023年，星期五代碼清單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 }第五頁，共十三頁，編輯于2023年，星期五STL的組成STL的代碼從廣義上講分為三類：algorithm（算法）、container（容器）和iterator（迭代器），幾乎所有的代碼都采用了模板類和模版函數(shù)的方式，這相比于傳統(tǒng)的由函數(shù)和類組成的庫來說提供了更好的代碼重用機會。簡單來說，其關(guān)系如圖18-3所示。

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