程序設(shè)計實習(xí)第二十講標(biāo)準(zhǔn)模板庫stli

1、程序設(shè)計實習(xí)第二十講 標(biāo)準(zhǔn)模板庫 STL I,主講教師：田永鴻yhtian@pku.edu.cnhttp://ai.pku.edu.cn/cpp2008/tyh/tyh.htmhttp://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年5月19日,2,課堂問題,下列代碼是否存在錯誤，若存在，該如何改正？template class CTemp{friend void myClas

2、s::func();private:T elements[size];public:CTemp(T arg);};template void myClass ::func(){CTemp a(10);int i;for(i=0; i obj;obj.func();,3,課堂問題,有如下類模板定義 template class CTemp{friend myCla

3、ssA;friend myClassB;private:T1 elements[size];public:CTemp(T arg){};};則myClassA、myClassB、myClassA、myClassA都是CTemp的友員類,4,課堂問題,找出下列代碼中的錯誤之處，并解釋a(10)（或b(8.9)、…的含義）template class CTemp{friend void func(int)

4、;private:T elements[size];public:CTemp(T arg){};};void func(int size){CTemp a(10);CTemp b(8.9);CTemp c(10);CTemp d(10);int i;for(i=0; i<50; i++) { cout<<a.elements[i

5、]<<“ ”<< b.elements[i]<<endl;}return;},5,提綱,1. 引言2. STL中的基本概念3. 容器概述4. 迭代器5. 算法簡介6. 順序容器,6,概論,C++ 語言的核心優(yōu)勢之一就是便于軟件的重用C++中有兩個方面體現(xiàn)重用：1. 面向?qū)ο蟮乃枷耄豪^承和多態(tài)，標(biāo)準(zhǔn)類庫2. 泛型程序設(shè)計(generic programming) 的思想：模板機(jī)制，

6、以及標(biāo)準(zhǔn)模板庫 STL,7,泛型程序設(shè)計,泛型程序設(shè)計，簡單地說就是使用模板的程序設(shè)計法。將一些常用的數(shù)據(jù)結(jié)構(gòu)（比如鏈表，數(shù)組，二叉樹）和算法（比如排序，查找）寫成模板，以后則不論數(shù)據(jù)結(jié)構(gòu)里放的是什么對象，算法針對什么樣的對象，則都不必重新實現(xiàn)數(shù)據(jù)結(jié)構(gòu)，重新編寫算法。標(biāo)準(zhǔn)模板庫 (Standard Template Library) 就是一些常用數(shù)據(jù)結(jié)構(gòu)和算法的模板的集合。主要由 Alex Stepanov 開發(fā)，于1998年被添加

7、進(jìn)C++標(biāo)準(zhǔn)有了STL，不必再從頭寫大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。,8,STL中的幾個基本概念,容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)。迭代器：可依次存取容器中元素的東西算法：用來操作容器中的元素的函數(shù)模板。例如，STL用sort()來對一個vector中的數(shù)據(jù)進(jìn)行排序，用find()來搜索一個list中的對象。函數(shù)本身與他們操作的數(shù)據(jù)的結(jié)構(gòu)和類型無關(guān)，因此他們可以在從簡單數(shù)組到高度復(fù)雜容器的任何數(shù)據(jù)結(jié)構(gòu)上使用

8、。比如，數(shù)組int array[100]就是個容器，而 int * 類型的指針變量就可以作為迭代器，可以為這個容器編寫一個排序的算法,9,容器概述,可以用于存放各種類型的數(shù)據(jù)（基本類型的變量，對象等）的數(shù)據(jù)結(jié)構(gòu)。容器分為三大類：1) 順序容器  vector：后部插入/刪除，直接訪問deque：前/后部插入/刪除，直接訪問list：雙向鏈表，任意位置插入/刪除 2)關(guān)聯(lián)容器set：快速查找，無重

9、復(fù)元素multiset ：快速查找，可有重復(fù)元素map：一對一映射，無重復(fù)元素，基于關(guān)鍵字查找multimap ：一對一映射，可有重復(fù)元素，基于關(guān)鍵字查找前2者合稱為第一類容器 3)容器適配器stack：LIFOqueue：FIFOpriority_queue：優(yōu)先級高的元素先出,10,容器概述,對象被插入容器中時，被插入的是對象的一個復(fù)制品。許多算法，比如排序，查找，要求對容器中的元素進(jìn)行比較，所以，放入容器的對象

10、所屬的類，還應(yīng)該實現(xiàn) == 和 < 運算符。,11,順序容器簡介,1) vector 頭文件 實際上就是個動態(tài)數(shù)組。隨機(jī)存取任何元素都能在常數(shù)時間完成。在尾端增刪元素具有較佳的性能。 2) deque 頭文件 也是個動態(tài)數(shù)組，隨機(jī)存取任何元素都能在常數(shù)時間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。 3) list 頭文件 雙向鏈表，在任何位置增刪元素都能在常數(shù)時間

11、完成。不支持隨機(jī)存取。 上述三種容器稱為順序容器，是因為元素的插入位置同元素的值無關(guān)。,12,關(guān)聯(lián)容器簡介,關(guān)聯(lián)式容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來確定其位置。關(guān)聯(lián)式容器的特點是在查找時具有非常好的性能。1) set/multiset: 頭文件 set 即集合。set中不允許相同元素，multiset中允許存在相同的元素。2) map/multimap: 頭文件 map與set的不

12、同在于map中存放的是成對的key/value。 并根據(jù)key對元素進(jìn)行排序，可快速地根據(jù)key來檢索元素 map同multimap的不同在于是否允許多個元素有相同的key值。 上述4種容器通常以平衡二叉樹方式實現(xiàn)，插入和檢索的時間都是 O(logN),13,容器適配器簡介,1) stack :頭文件 棧。是項的有限序列，并滿足序列中被刪除、檢索和修改的項只能是最近插入序列的項。即按照后進(jìn)先出的原則2) que

13、ue :頭文件 隊列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照先進(jìn)先出的原則。3）priority_queue :頭文件 優(yōu)先級隊列。最高優(yōu)先級元素總是第一個出列,14,容器的共有成員函數(shù),1) 所有標(biāo)準(zhǔn)庫容器共有的成員函數(shù)：相當(dāng)于按詞典順序比較兩個容器大小的運算符： =, , >=, == , !=empty : 判斷容器中是否有元素max_size: 容器中最多能裝多少

14、元素size: 容器中元素個數(shù)swap: 交換兩個容器的內(nèi)容,比較兩個容器的例子：#include #include class A {private:int n;public:friend bool operator v1;std::vector v2;v1.push_back (A(5)); v1.push_back (A(1));v2.push_back (A(1)); v2.push_b

15、ack (A(2));v2.push_back (A(3));std::cout << (v1 < v2); return 0;},輸出：0,若兩容器長度相同、所有元素相等，則兩個容器就相等，否則為不等。若兩容器長度不同，但較短容器中所有元素都等于較長容器中對應(yīng)的元素，則較短容器小于另一個容器若兩個容器均不是對方的子序列，則取決于所比較的第一個不等的元素,16,容器的成員函數(shù)

16、,2) 只在第一類容器中的函數(shù)：begin 返回指向容器中第一個元素的迭代器end 返回指向容器中最后一個元素后面的位置的迭代器rbegin 返回指向容器中最后一個元素的迭代器rend 返回指向容器中第一個元素前面的位置的迭代器erase 從容器中刪除一個或幾個元素clear 從容器中刪除所有元素,,,,Head,Tail,,,,,,,begin,rbegin,rend,end,,17,

17、迭代器,用于指向第一類容器中的元素。有const 和非 const兩種。通過迭代器可以讀取它指向的元素，通過非const迭代器還能修改其指向的元素。迭代器用法和指針類似。定義一個容器類的迭代器的方法可以是：容器類名::iterator 變量名;或：容器類名::const_iterator 變量名;訪問一個迭代器指向的元素：* 迭代器變量名,18,迭代器,迭代器上可以執(zhí)行 ++ 操作, 以指向容器中的下一個元素。如

18、果迭代器到達(dá)了容器中的最后一個元素的后面，則迭代器變成past-the-end值。使用一個past-the-end值的迭代器來訪問對象是非法的，就好像使用NULL或未初始化的指針一樣。,例如：#include #include using namespace std;int main() {vector v; //一個存放int元素的向量，一開始里面沒有元素v.push_back(1);v.push_back(

19、2); v.push_back(3); v.push_back(4);vector::const_iterator i; //常量迭代器for( i = v.begin();i != v.end();i ++ ) cout << * i << ",";cout << endl;,vector::reverse_iterator r; //反向迭代器

20、for( r = v.rbegin();r != v.rend();r++ ) cout ::iterator j; //非常量迭代器for( j = v.begin();j != v.end();j ++ ) * j = 100;for( i = v.begin();i != v.end();i++ ) cout << * i << ",";}輸出結(jié)果

21、：1,2,3,4,4,3,2,1,100,100,100,100,,21,迭代器,不同容器上支持的迭代器功能強(qiáng)弱有所不同。 容器的迭代器的功能強(qiáng)弱，決定了該容器是否支持STL中的某種算法。例1：只有第一類容器能用迭代器遍歷。例2：排序算法需要通過隨機(jī)迭代器來訪問容器中的元素，那么有的容器就不支持排序算法。,22,STL 中的迭代器,STL 中的迭代器按功能由弱到強(qiáng)分為5種： 1. 輸入：Input iterators

22、提供對數(shù)據(jù)的只讀訪問。 1. 輸出：Output iterators 提供對數(shù)據(jù)的只寫訪問 2. 正向：Forward iterators 提供讀寫操作，并能一次一個地向前推進(jìn)迭代器。 3. 雙向：Bidirectional iterators提供讀寫操作，并能一次一個地向前和向后移動。 4. 隨機(jī)訪問：Random access iterators提供讀寫操作，并能在數(shù)據(jù)中隨機(jī)移動。編號大的迭代器擁有編號小

23、的迭代器的所有功能，能當(dāng)作編號小的迭代器使用。,23,不同迭代器所能進(jìn)行的操作(功能）,所有迭代器： ++p, p ++輸入迭代器： * p, p = p1, p == p1 , p!= p1輸出迭代器： * p, p = p1正向迭代器： 上面全部雙向迭代器： 上面全部，--p, p --,隨機(jī)訪問迭代器： 上面全部，以及：p+= i, p -= i, p + i： 返回指向 p 后面的第i個元素的迭代器p -

24、i： 返回指向 p 前面的第i個元素的迭代器p[i]: p 后面的第i個元素的引用p p1, p>= p1,24,容器所支持的迭代器類別,容器迭代器類別vector隨機(jī)deque隨機(jī)list 雙向set/multiset雙向map/multimap雙向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器,例如

25、，vector的迭代器是隨機(jī)迭代器，所以遍歷 vector 可以有以下幾種做法：vector v(100);vector::value_type i; //等效于寫 int i;(P687)for(i = 0;i ::const_iterator ii;for( ii = v.begin(); ii != v.end ();ii ++ )cout << * ii;//間隔一個輸出：ii = v.begin()

26、;while( ii < v.end()) {cout << * ii; ii = ii + 2; },而 list 的迭代器是雙向迭代器，所以以下代碼可以：list v;list::const_iterator ii;for( ii = v.begin(); ii ！＝ v.end ();ii ++ )cout << * ii;以下代碼則不行：for( ii = v

27、.begin(); ii < v.end ();ii ++ )cout << * ii;//雙向迭代器不支持 <for(int i = 0;i < v.size() ; i ++)cout << v[i]; //雙向迭代器不支持 [],27,算法簡介,STL中提供能在各種容器中通用的算法，比如插入，刪除，查找，排序等。大約有70種標(biāo)準(zhǔn)算法。算法就是一個個函數(shù)模板。算

28、法通過迭代器來操縱容器中的元素。許多算法需要兩個參數(shù)，一個是起始元素的迭代器，一個是終止元素的后面一個元素的迭代器。比如，排序和查找有的算法返回一個迭代器。比如 find() 算法，在容器中查找一個元素，并返回一個指向該元素的迭代器。算法可以處理容器，也可以處理C語言的數(shù)組,28,,算法分類,變化序列算法copy ,remove,fill,replace,random_shuffle,swap, …..會改變?nèi)萜鞣亲兓?/p>

29、序列算法：adjacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_n以上函數(shù)模板都在 中定義V2, P692（V5, P834）此外還有其他算法，比如中的算法,29,算法示例：find(),templateInIt find(InIt first, InIt last, const T& val); first 和

30、last 這兩個參數(shù)都是容器的迭代器，它們給出了容器中的查找區(qū)間起點和終點。這個區(qū)間是個左閉右開的區(qū)間，即區(qū)間的起點是位于查找范圍之中的，而終點不是val參數(shù)是要查找的元素的值函數(shù)返回值是一個迭代器。如果找到，則該迭代器指向被找到的元素。如果找不到，則該迭代器指向查找區(qū)間終點。,#include #include #include using namespace std;main() {int array[10] =

31、 {10,20,30,40};vector v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector::iterator p;p = find(v.begin(),v.end(),3);if( p != v.end())cout << * p << endl;,p = find(v.begin(),v

32、.end(),9);if( p == v.end())cout << "not found " << endl;p = find(v.begin()+1,v.end()-2,1);if( p != v.end())cout << * p << endl;int * pp = find( array,array+4,20);cout <

33、;< * pp << endl;}輸出：3not found320,32,順序容器,除前述共同操作外，順序容器還有以下共同操作：front() :返回容器中第一個元素的引用back() : 返回容器中最后一個元素的引用push_back(): 在容器末尾增加新元素pop_back(): 刪除容器末尾的元素比如，查 list::front 的help,得到的定義是：reference f

34、ront(); const_reference front() const;list有兩個front函數(shù),33,順序容器,reference和 const_reference 是typedef的類型，含義見P687對于 list , list::reference 實際上就是 double &list::const_reference 實際上就是 const double &對于 list ,

35、list::refrence 實際上就是 int &list::const_refreence 實際上就是 const int &,34,,vector,支持隨機(jī)訪問迭代器，所有STL算法都能對vector操作。隨機(jī)訪問時間為常數(shù)。在尾部添加速度很快，在中間插入慢。實際上就是動態(tài)數(shù)組。,例1：int main() {int i;int a[5] = {1,2,3,4,5 }; vector v

36、(5);cout v2(a,a+5); //構(gòu)造函數(shù)v2.insert( v2.begin() + 2, 13 ); //在begin()+2位置插入 13for( i = 0;i < v2.size();i ++ )cout << v2[i] << "," ; return 0;},輸出：50,1,2,3,100,1,2,

37、13,3,4,5,,例2：int main() {const int SIZE = 5;int a[SIZE] = {1,2,3,4,5 }; vector v (a,a+5); //構(gòu)造函數(shù)try {v.at(100) = 7;}catch( out_of_range e) {cout output(cout ,“*");copy (v.begin(),v.end(),outp

38、ut);v.erase( v.begin(),v.end()); //等效于 v.clear();,if( v.empty ())cout subscript1,52*3*4*5*empty1*2*3*4*5*,39,算法解釋,ostream_iterator output(cout ,“*");定義了一個 ostream_iterator 對象，可以通過cout輸出以 * 分隔的一個個整數(shù)copy (

39、v.begin(),v.end(),output);導(dǎo)致v的內(nèi)容在 cout上輸出copy 函數(shù)模板(算法）：template OutIt copy(InIt first, InIt last, OutIt x); 本函數(shù)對每個在區(qū)間[0, last - first)中的N執(zhí)行一次 *(x+N) = * ( first + N) ，返回 x + N對于copy (v.begin(),v.end(),output);firs

40、t 和 last 的類型是 vector::const_iteratoroutput 的類型是 ostream_iterator,關(guān)于 ostream_iterator, istream_iterator的例子int main() {istream_iterator inputInt(cin);int n1,n2;n1 = * inputInt; //讀入 n1inputInt ++; n2 = * i

41、nputInt; //讀入 n2cout > outputInt(cout);* outputInt = n1 + n2; cout << endl;int a[5] = { 1,2,3,4,5};copy(a,a+5,outputInt); //輸出整個數(shù)組 return 0;},41,程序運行后輸入 78 90敲回車，則輸出結(jié)果為：78,9016812345,4

42、2,list 容器,在任何位置插入刪除都是常數(shù)時間，不支持隨機(jī)存取。除了具有所有順序容器都有的成員函數(shù)以外，還支持8個成員函數(shù)：push_front: 在前面插入pop_front: 刪除前面的元素sort: 排序( list 不支持STL 的算法sort)remove: 刪除和指定值相等的所有元素unique: 刪除所有和前一個元素相同的元素merge: 合并兩個鏈表，并清空被合并的那個reverse: 顛倒鏈表spl

43、ice: 在指定位置前面插入另一鏈表中的一個或多個元素,并在另一鏈表中刪除被插入的元素,#include #include #include using std::list; using std::ostream; using std::cout; using std::endl;class A {private:int n;public:A( int n_ ) { n = n_; }friend bool op

44、erator<( const A & a1, const A & a2);friend bool operator==( const A & a1, const A & a2);friend ostream & operator <<( ostream & o, const A & a);};,bool operatorvoid PrintList(c

45、onst std::list & lst) {int tmp = lst.size();if( tmp > 0 ) {std::list::const_iterator i;i = lst.begin();for( i = lst.begin();i != lst.end(); i ++)cout << * i << ",";}},int ma

46、in() {list lst1,lst2;lst1.push_back(1);lst1.push_back(3);lst1.push_back(2);lst1.push_back(4); lst1.push_back(2);lst2.push_back(10);lst2.push_front(20);lst2.push_back(30);lst2.push_back(30);lst2.push_back(30);

47、lst2.push_front(40);lst2.push_back(40);cout << "1) "; PrintList( lst1); cout << endl;cout << "2) "; PrintList( lst2); cout << endl;lst2.sort();cout << "3)

48、"; PrintList( lst2); cout << endl;lst2.pop_front();cout << "4) "; PrintList( lst2); cout << endl;lst1.remove(2);//刪除所有和A(2)相等的元素cout << "5) "; PrintList( lst1); co

49、ut << endl;lst2.unique(); //刪除所有和前一個元素相等的元素,cout ::iterator p1,p2,p3;p1 = std::find(lst1.begin(),lst1.end(),3);p2 = std::find(lst2.begin(),lst2.end(),200);p3 = std::find(lst2.begin(),lst2.end(),400);lst1.

50、splice(p1,lst2,p2, p3); //將[p2,p3)插入p1之前，//并從lst2中刪除[p2,p3)cout << "11) "; PrintList( lst1); cout << endl;cout << "12) "; PrintList( lst2); cout << endl; retur

51、n 0;},47,輸出：,1) 1,3,2,4,2,2) 40,20,10,30,30,30,40,3) 10,20,30,30,30,40,40,4) 20,30,30,30,40,40,5) 1,3,4,6) 20,30,40,7) 1,3,4,20,30,40,8)9) 40,30,20,4,3,1,11) 40,30,20,4,200,300,3,1,12) 100,400,,48,deque 容器,所有適