C++_STL詳解PPT課件.ppt

1、ACM/ICPC程序設(shè)計(jì),C+ 標(biāo)準(zhǔn)模板庫C+ Standard Template Libarary 計(jì)算機(jī)學(xué)院 萬波,主要內(nèi)容,STL概述：組件、容器、迭代器（iterator）、算法 STL容器： 常用容器：vector、deque、 list、 map/multimap 、set 特殊容器：stack、queue，priority_queue 其他容器：hashtable STL算法：搜尋、排序、拷貝、數(shù)值運(yùn)算,STL概述,STL是C+標(biāo)準(zhǔn)程序庫的核心，深刻影響了標(biāo)準(zhǔn)程序庫的整體結(jié)構(gòu) STL是泛型（generic）程序庫，利用先進(jìn)、高效的算法來管理數(shù)據(jù) STL由一些可適應(yīng)不同需求的集合類

2、（collection class），以及在這些數(shù)據(jù)集合上操作的算法（algorithm）構(gòu)成 STL內(nèi)的所有組件都由模板（template）構(gòu)成，其元素可以是任意類型 STL是所有C+編譯器和所有操作系統(tǒng)平臺(tái)都支持的一種庫,STL概述,/普通C+代碼 #include int main(void) double a = 1, 2, 3, 4, 5; std:coutmean(a, 5); std:coutstd:endl; return 0; ,/使用了STL的代碼 #include #include int main() std:vector a; a.push_back(1); a.pu

3、sh_back(2); a.push_back(3); a.push_back(4); a.push_back(5); for(int i = 0; i a.size(); +i) std:coutaistd:endl; return 0; ,STL概述,/使用了STL的代碼 #include #include int main() std:vector q; q.push_back(10); q.push_back(11); q.push_back(12); std:vector v; for(int i=0; i5; +i) v.push_back(i); ,std:vector:iter

4、ator it = v.begin() + 1; it = v.insert(it, 33); v.insert(it, q.begin(), q.end(); it = v.begin() + 3; v.insert(it, 3, -1); it = v.begin() + 4; v.erase(it); it = v.begin() + 1; v.erase(it, it + 4); v.clear(); return 0;,STL概述,模板（template） 函數(shù)模板,針對(duì)一個(gè)或多個(gè)尚未明確的類型所撰寫的函數(shù)或類,#include #include using namespace st

5、d; /定義函數(shù)模板 template T MAX(T a, T b) return (ab)?a:b; ,int main() int x=2,y=6; double x1=9.123,y1=12.6543; coutMAX(x,y)endl; coutMAX(x1,y1)endl; ,STL概述,模板（template） 類模板,針對(duì)一個(gè)或多個(gè)尚未明確的類型所撰寫的函數(shù)或類,#include using namespace std; /定義名為ex_class的類模板 template class ex_class T value; public: ex_class(T v) value=

6、v; void set_value(T v) value=v; T get_value(void) return value; ;,int main() /測(cè)試char類型數(shù)據(jù) ex_class ch(A); cout d(5.5); cout“d.value:d.get_value()endl; x.set_value(7.5); cout“d.value:x.get_value()endl; ,STL概述,STL組件 容器（Container） 管理某類對(duì)象的集合 迭代器（Iterator） 在對(duì)象集合上進(jìn)行遍歷 算法（Algorithm） 處理集合內(nèi)的元素 容器適配器（container

7、 adaptor） 函數(shù)對(duì)象(functor),STL組件之間的協(xié)作,STL概述,STL容器類別 序列式容器排列次序取決于插入時(shí)機(jī)和位置 關(guān)聯(lián)式容器排列順序取決于特定準(zhǔn)則,STL概述,STL容器的共通能力 所有容器中存放的都是值而非引用，即容器進(jìn)行安插操作時(shí)內(nèi)部實(shí)施的是拷貝操作。因此容器的每個(gè)元素必須能夠被拷貝。如果希望存放的不是副本，容器元素只能是指針。 所有元素都形成一個(gè)次序（order），可以按相同的次序一次或多次遍歷每個(gè)元素 各項(xiàng)操作并非絕對(duì)安全，調(diào)用者必須確保傳給操作函數(shù)的參數(shù)符合需求，否則會(huì)導(dǎo)致未定義的行為,STL概述,STL容器元素的條件 必須能夠通過拷貝構(gòu)造函數(shù)進(jìn)行復(fù)制 必須可

8、以通過賦值運(yùn)算符完成賦值操作 必須可以通過析構(gòu)函數(shù)完稱銷毀動(dòng)作 序列式容器元素的默認(rèn)構(gòu)造函數(shù)必須可用 某些動(dòng)作必須定義operator =，例如搜尋操作 關(guān)聯(lián)式容器必須定義出排序準(zhǔn)則，默認(rèn)情況是重載operator ,對(duì)于基本數(shù)據(jù)類型（int,long,char,double,）而言，以上條件總是滿足,STL概述,STL容器的共通操作 初始化（initialization） 產(chǎn)生一個(gè)空容器 以另一個(gè)容器元素為初值完成初始化 以數(shù)組元素為初值完成初始化,std:list l; std:vector c(l.begin(),l.end();,int array=2,4,6,1345; std:se

9、t c(array,array+sizeof(array)/sizeof(array0);,std:list l;,STL概述,STL容器的共通操作 與大小相關(guān)的操作（size operator） size()返回當(dāng)前容器的元素?cái)?shù)量 empty()判斷容器是否為空 max_size()返回容器能容納的最大元素?cái)?shù)量 比較（comparison） =,!=,= 比較操作兩端的容器必須屬于同一類型 如果兩個(gè)容器內(nèi)的所有元素按序相等，那么這兩個(gè)容器相等 采用字典式順序判斷某個(gè)容器是否小于另一個(gè)容器,STL概述,STL容器的共通操作 賦值（assignment）和交換（swap） swap用于提高賦值操

10、作效率 與迭代器（iterator）相關(guān)的操作 begin()返回一個(gè)迭代器，指向第一個(gè)元素 end()返回一個(gè)迭代器，指向最后一個(gè)元素之后 rbegin()返回一個(gè)逆向迭代器，指向逆向遍歷的第一個(gè)元素 rend()返回一個(gè)逆向迭代器，指向逆向遍歷的最后一個(gè)元素之后,STL概述,容器的共通操作 元素操作 insert(pos,e)將元素e的拷貝安插于迭代器pos所指的位置 erase(beg,end)移除beg，end區(qū)間內(nèi)的所有元素 clear()移除所有元素,STL概述,迭代器（iterator）（示例:iterator） 可遍歷STL容器內(nèi)全部或部分元素的對(duì)象 指出容器中的一個(gè)特定位置

11、迭代器的基本操作,STL概述,迭代器（iterator） 所有容器都提供獲得迭代器的函數(shù),半開區(qū)間beg, end)的好處： 1.為遍歷元素時(shí)循環(huán)的結(jié)束時(shí)機(jī)提供了簡(jiǎn)單的判斷依據(jù)（只要未到達(dá)end()，循環(huán)就可以繼續(xù)） 2.不必對(duì)空區(qū)間采取特殊處理（空區(qū)間的begin()就等于end()）,STL概述,迭代器（iterator） 所有容器都提供兩種迭代器 container:iterator以“讀/寫”模式遍歷元素 container:const_iterator以“只讀”模式遍歷元素 迭代器示例：iterator,STL概述,迭代器（iterator） 迭代器分類 雙向迭代器 可以雙向行進(jìn),以

12、遞增運(yùn)算前進(jìn)或以遞減運(yùn)算后退、可以用=和!=比較。 list、set和map提供雙向迭代器 隨機(jī)存取迭代器 除了具備雙向迭代器的所有屬性，還具備隨機(jī)訪問能力。 可以對(duì)迭代器增加或減少一個(gè)偏移量、處理迭代器之間的距離或者使用之類的關(guān)系運(yùn)算符比較兩個(gè)迭代器。 vector、deque和string提供隨機(jī)存取迭代器,vector v; for(pos=v.begin();posv.end();+pos ,list l; for(pos=l.begin();pos!=l.end();+pos ,STL容器,vector vector模擬動(dòng)態(tài)數(shù)組 vector的元素可以是任意類型T，但必須具備賦值和拷

13、貝能力（具有public拷貝構(gòu)造函數(shù)和重載的賦值操作符） 必須包含的頭文件#include vector支持隨機(jī)存取 vector的大?。╯ize）和容量（capacity） size返回實(shí)際元素個(gè)數(shù)， capacity返回vector能容納的元素最大數(shù)量。如果插入元素時(shí)，元素個(gè)數(shù)超過capacity，需要重新配置內(nèi)部存儲(chǔ)器。,STL容器,vector 構(gòu)造、拷貝和析構(gòu),STL容器,vector 非變動(dòng)操作,STL容器,vector 賦值操作,std:list l; std:vector v; v.assign(l.begin(),l.end();,所有的賦值操作都有可能調(diào)用元素類型的默認(rèn)構(gòu)造

14、函數(shù)，拷貝構(gòu)造函數(shù)，賦值操作符和析構(gòu)函數(shù),STL容器,vector 元素存取,std:vector v;/empty v5= t;/runtime error std:cout v.front();/runtime error,STL容器,vector 迭代器相關(guān)函數(shù),迭代器持續(xù)有效，除非發(fā)生以下兩種情況： （1）刪除或插入元素 （2）容量變化而引起內(nèi)存重新分配,STL容器,vector 安插（insert）元素,STL容器,vector 移除（remove）元素,STL容器,vector vector應(yīng)用實(shí)例：vector,STL容器,deque deque模擬動(dòng)態(tài)數(shù)組 deque的元素可以

15、是任意類型T，但必須具備賦值和拷貝能力（具有public拷貝構(gòu)造函數(shù)和重載的賦值操作符） 必須包含的頭文件#include deque支持隨機(jī)存取 deque支持在頭部和尾部存儲(chǔ)數(shù)據(jù) deque不支持capacity和reserve操作,STL容器,deque 構(gòu)造、拷貝和析構(gòu),STL容器,deque 非變動(dòng)操作,STL容器,deque 賦值操作,std:list l; std:deque v; v.assign(l.begin(),l.end();,所有的賦值操作都有可能調(diào)用元素類型的默認(rèn)構(gòu)造函數(shù)，拷貝構(gòu)造函數(shù)，賦值操作符和析構(gòu)函數(shù),STL容器,deque 元素存取,std:deque dq

16、;/empty dq5= t;/runtime error std:cout dq.front();/runtime error,STL容器,deque 迭代器相關(guān)函數(shù),迭代器持續(xù)有效，除非發(fā)生以下兩種情況： （1）刪除或插入元素 （2）容量變化而引起內(nèi)存重新分配,STL容器,deque 安插（insert）元素,STL容器,deque 移除（remove）元素,STL容器,deque deque應(yīng)用實(shí)例： deque,STL容器,list 使用雙向鏈表管理元素 list的元素可以是任意類型T，但必須具備賦值和拷貝能力 必須包含的頭文件#include list不支持隨機(jī)存取，因此不提供下標(biāo)操

17、作符 在任何位置上執(zhí)行元素的安插和移除都非?？臁?安插和刪除不會(huì)導(dǎo)致指向其他元素的指針、引用、iterator失效。,STL容器,list 構(gòu)造、拷貝和析構(gòu),STL容器,list 非變動(dòng)性操作,STL容器,list 賦值,STL容器,list 元素存取,std:list l;/empty std:cout l.front();/runtime error if(!l.empty() std:coutl.back();/ok ,STL容器,list 迭代器相關(guān)函數(shù),STL容器,list 安插（insert）元素,STL容器,list 移除（remove）元素,STL容器,list 特殊變動(dòng)性操作

18、,STL容器,list 特殊變動(dòng)性操作（續(xù)）,STL容器,list list應(yīng)用實(shí)例：list,STL容器,map/multimap 使用平衡二叉樹管理元素 元素包含兩部分(key,value)，key和value可以是任意類型 必須包含的頭文件#include 根據(jù)元素的key自動(dòng)對(duì)元素排序，因此根據(jù)元素的key進(jìn)行定位很快，但根據(jù)元素的value定位很慢 不能直接改變?cè)氐膋ey，可以通過operator 直接存取元素值 map中不允許key相同的元素，multimap允許key相同的元素,STL容器,map/multimap 內(nèi)部存儲(chǔ)結(jié)構(gòu),STL容器,map/multimap 構(gòu)造、拷貝

19、和析構(gòu),其中map可以是下列形式 map一個(gè)以less（一個(gè)以op為排序準(zhǔn)則的map,STL容器,map/multimap 非變動(dòng)性操作,STL容器,map/multimap 賦值,STL容器,map/multimap 特殊搜尋操作,STL容器,map/multimap 迭代器相關(guān)函數(shù),STL容器,map/multimap 安插（insert）元素,STL容器,map/multimap 移除（remove）元素,STL容器,map/multimap map應(yīng)用實(shí)例：map,STL容器,stack（實(shí)例：stack ） 后進(jìn)先出（LIFO） #include 核心接口 push(value)將元

20、素壓棧 top()返回棧頂元素的引用，但不移除 pop()從棧中移除棧頂元素，但不返回 實(shí)例：stack,STL容器,queue（實(shí)例：queue ） 先進(jìn)先出（FIFO） #include 核心接口 push(e)將元素置入隊(duì)列 front()返回隊(duì)列頭部元素的引用，但不移除 back()返回隊(duì)列尾部元素的引用，但不移除 pop()從隊(duì)列中移除元素，但不返回 實(shí)例：queue,STL容器,priority_queue （實(shí)例：priority_queue ） 以某種排序準(zhǔn)則（默認(rèn)為less）管理隊(duì)列中的元素 #include 核心接口 push(e)根據(jù)元素的優(yōu)先級(jí)將元素置入隊(duì)列 top()

21、返回優(yōu)先隊(duì)列頭部最大的元素的引用，但不移除 pop()從棧中移除最大元素，但不返回 empty() 隊(duì)列是否為空,STL算法,STL提供了一些標(biāo)準(zhǔn)算法來處理容器內(nèi)的元素 搜尋、排序、拷貝、數(shù)值運(yùn)算 STL的算法是全局函數(shù) 明確劃分?jǐn)?shù)據(jù)和操作 泛型函數(shù)式編程模式 所有算法可以對(duì)所有容器適用，甚至可以操作不同類型容器的元素 算法頭文件 #include #include STL算法實(shí)例：algorithm,STL算法,區(qū)間（range） 所有算法都用來處理一個(gè)或多個(gè)區(qū)間內(nèi)的元素。 區(qū)間可以但不一定涵蓋容器內(nèi)所有元素 為了操作元素的某個(gè)子集必須將區(qū)間的首尾（iterator）當(dāng)作兩個(gè)參數(shù)傳遞給算法 調(diào)用時(shí)必須確保區(qū)間有效性