STL中的線性容器List、stack的使用list的結(jié)構(gòu)list的函數(shù)異常處理stack容器了解list的結(jié)構(gòu)特點(diǎn)掌握list的函數(shù)和異常處理方法掌握stack容器的原理及使用2list使用一個雙向鏈表來管理元素。List的結(jié)構(gòu)：使用list時必須包含頭文件<list>：#include<list>其中l(wèi)ist類型是定義于namespacestd中，是個classtemplate：namespacestd{template<classT,classAllocator=allocator<T>>classlist;}5STL中的線性容器5.3：list容器3list的內(nèi)部結(jié)構(gòu)和vector或deque截然不同。list在以下幾個主要方面與前兩者存在明顯區(qū)別：1）list不支持隨機(jī)存取。如果要存取第5個元素，就得遍歷前4個元素。所以，在list中隨機(jī)遍歷任意元素，是很緩慢的行為。2）任何位置上（不只是兩端）執(zhí)行元素的插入和刪除都非常快，始終都是常數(shù)時間內(nèi)完成，因為無需移動任何其他元素。實際上內(nèi)部只是進(jìn)行了一些指針操作而已。3）插入和刪除動作并不會造成指向其他元素的各個指針、引用、迭代器失效。4）list對于異常有著這樣的處理方式：如果操作不成功，將不會對list中數(shù)據(jù)進(jìn)行任何操作。決不會陷入“只成功一半”的狀態(tài)。5STL中的線性容器5.3：list容器4list所提供的成員函數(shù)反映出它和vector以及deque的不同：1）由于不支持隨機(jī)存取，list既不提供下標(biāo)運(yùn)算符，也不提供at()。2）list并未提供容量、空間重新分配等操作函數(shù)，因為全無必要。每個元素都有自己的內(nèi)存，在被刪除之前一直有效。3）list提供了不少特殊的成員函數(shù)，專門用于移動元素。較之同名的STL通用算法，這些函數(shù)執(zhí)行起來更快，因為它們無需拷貝或移動，只需調(diào)整若干指標(biāo)即可。5STL中的線性容器5.3：list容器5List的操作List的構(gòu)造函數(shù)和析構(gòu)函數(shù)函數(shù)功能list<Elem>c產(chǎn)生一個空的listlist<Elem>c1(c2)產(chǎn)生一個與c2同類型的list（每個元素都被復(fù)制）list<Elem>c(n)產(chǎn)生擁有n個元素的list，這些元素都以默認(rèn)構(gòu)造函數(shù)初始化list<Elem>c(n,elem)產(chǎn)生擁有n個元素的list，每個元素都是elem的副本list<Elem>c(beg,end)產(chǎn)生一個list并以[beg;end)區(qū)間內(nèi)的元素為初值c.~list<Elem>()銷毀所有元素，釋放內(nèi)存5STL中的線性容器5.3：list容器6非變動性操作：函數(shù)功能c.size()返回元素個數(shù)c.empty()判斷容器大小是否為零。等同于size()==0，但可能更快c.max_size()返回元素的最大可能數(shù)量c1==c2判斷是否c1等于c2c1!=c2判斷是否c1不等于c2。等同于!(c1==c2)c1<c2判斷是否c1小于c2c1>c2判斷是否c1大于c2。等同于與c2<c1相同c1<=c2判斷是否c1小于等于c2。等同于!(c2<c1)c1>=c2判斷是否c1大于等于c2。等同于!(c1<c2)5STL中的線性容器5.3：list容器7賦值操作函數(shù)功能c1=c2將c2的全部元素賦值給c1c.assign(n,elem)將elem的n個拷貝賦值給cc.assign(beg,end)將區(qū)間[beg;end)的元素賦值給cc1.swap(c2)將c1和c2的元素互換swap(c1,c2)同上。此為全局函數(shù)5STL中的線性容器5.3：list容器8list不支持隨機(jī)存取，只有front()和back()能夠直接存取元素函數(shù)功能c.front()返回第一個元素，不檢查元素是否存在c.back()返回最后一個元素，不檢查元素是否存在這些操作并不檢查容器是否為空。調(diào)用者必須確保容器至少含有一個元素。std::list<Elem>coll; //空liststd::cout<<coll.front(); //錯誤！if(!coll.empty()) //正確的操作方式{std::cout<<coll.back();}5STL中的線性容器5.3：list容器9list元素的front和back操作：intiarray[5]={1,2,3,4,5};

list<int>lContainers(iarray,&iarray[5]);if(!lContainers.empty()){ cout<<"lContainers第一個元素為:“ <<lContainers.front()<<endl; cout<<"lContainers最后一個元素為：“ <<lContainers.back()<<endl;}5STL中的線性容器5.3：list容器10迭代器相關(guān)函數(shù)：只有運(yùn)用迭代器，才能夠存取list中的各個元素。由于list不能隨機(jī)存取，這些迭代器只是雙向（而非隨機(jī)）迭代器。所以凡是用到隨機(jī)存取迭代器的算法（所有用來操作元素順序的算法，特別是排序算法都?xì)w此類）都不能調(diào)用。不過可以拿list的特殊成員函數(shù)sort()代替。函數(shù)功能c.begin()返回一個雙向迭代器，指向第一個元素c.end()返回一個雙向迭代器，指向最后元素的下一個位置c.rbegin()返回一個逆向迭代器，指向逆向迭代的第一個元素c.rend()返回一個逆向迭代器，指向逆向迭代的最后元素的下一個位置5STL中的線性容器5.3：list容器11元素的插入和刪除操作：和一般運(yùn)用STL時相似，必須確保參數(shù)的正確。迭代器必須指向合法位置，區(qū)間終點(diǎn)不能位于區(qū)間起點(diǎn)的前面，還有，不能從空容器中刪除元素。函數(shù)功能c.insert(pos,elem)在迭代器pos所指位置上插入一個elem副本，并返回新元素的位置c.insert(pos,n,elem)在迭代器pos所指位置上插入n個elem副本，無返回值c.insert(pos,beg,end)在迭代器pos所指位置上插入[beg;end)區(qū)間內(nèi)的所有元素的副本，無返值c.push_back(elem)在尾部追加一個elem副本c.pop_back()刪除最后一個元素（但不返回其值）5STL中的線性容器5.3：list容器12c.push_front(elem)在頭部插入一個elem副本c.pop_front()刪除第一個元素（但不返回其值）c.remove(val)刪除所有值為val的元素c.remove_if(op)刪除所有“造成op(elem)結(jié)果為true”的元素c.erase(pos)刪除迭代器pos所指元素，返回下一個元素位置c.erase(beg,end)刪除區(qū)間[beg;end)內(nèi)的所有元素，返回下一個元素位置c.resize(num)將元素容量變?yōu)閚um。如果size()變大，則以默認(rèn)構(gòu)造函數(shù)構(gòu)造所有新增元素c.resize(num,elem)將元素容量變?yōu)閚um。如果size()變大，則以elem副本作為新增元素的初值c.clear()刪除全部元素，將整個容器清空5STL中的線性容器5.3：list容器13Splice函數(shù)鏈表的一大好處就是不論在任何位置，元素的插入和刪除都只需要常數(shù)時間。list不僅提供remove()，還提供其他一些成員函數(shù)，用來改變元素和區(qū)間次序，或是用來重新串鏈。5STL中的線性容器5.3：list容器14list的特殊變動性操作操作功能c.unique()如果存在若干相鄰而數(shù)值相同的元素，就刪除重復(fù)元素，只留下一個c.unique(op)如果存在若干相鄰元素，都使op()的結(jié)果為true，則刪除重復(fù)元素，只留下一個c1.splice(pos,c2)將c2內(nèi)的所有元素轉(zhuǎn)移到c1之內(nèi)、迭代器pos之前c1.splice(pos,c2,c2pos)將c2內(nèi)的c2pos所指元素轉(zhuǎn)移到c1內(nèi)的pos所指位置上（c1和c2可相同）5STL中的線性容器5.3：list容器15c1.splice(pos,c2,c2beg,c2end)將c2內(nèi)的[c2beg;c2end)區(qū)間內(nèi)所有元素轉(zhuǎn)移到c1內(nèi)的pos之前（c1和c2可相同）c.sort()以operator<為準(zhǔn)則，對所有元素排序c.sort(op)以op()為準(zhǔn)則，對所有元素排序c1.merge(c2)假設(shè)c1和c2容器都包含已排序元素，將c2的全部元素轉(zhuǎn)移到c1，并保證合并后的list仍為已排序c1.merge(c2,op)假設(shè)c1和c2容器都包含op()原則下的已排序元素，將c2的全部元素轉(zhuǎn)移到c1，并保證合并后的list在op()原則下仍為已排序c.reverse()將所有元素反序5STL中的線性容器5.3：list容器16intiarray[10]={1,2,2,3,3,4,4,5,5,6};list<int>lContainers1(iarray,&iarray[10]);如果存在若干相鄰而數(shù)值相同的元素，就刪除重復(fù)元素，只留下一個lContainers1.unique();將lContainers2內(nèi)的所有元素轉(zhuǎn)移到lContainers1之內(nèi)、迭代器pos之前l(fā)ist<int>lContainers2;lContainers2.push_back(7);list<int>::iteratorpos=lContainers1.end();lContainers1.splice(pos,lContainers2);5STL中的線性容器5.3：list容器17將lContainers1內(nèi)的pos所指元素轉(zhuǎn)移到lContainers2內(nèi)的pos2所指位置上list<int>::iteratorpos2=lContainers2.begin();pos=lContainers1.begin();lContainers2.splice(pos2,lContainers1,pos);將lContainers1內(nèi)的[beg;end)區(qū)間內(nèi)所有元素轉(zhuǎn)移到lContainers2內(nèi)的pos2之前pos2=lContainers2.end();lContainers2.splice(pos2,lContainers1,lContainers1.begin(), lContainers1.end());5STL中的線性容器5.3：list容器18以operator<為準(zhǔn)則，對所有元素排序intiarray2[10]={10,9,8,7,6,5,4,3,2,1};lContainers1.insert(lContainers1.begin(),iarray2,&iarray2[10]);lContainers1.sort();將lContainers2的全部元素轉(zhuǎn)移到lContainers1并保證合并后的lContainers1仍為已排序Containers2.push_back(6);lContainers2.push_back(19);lContainers1.merge(lContainers2);將lContainers1所有元素反序lContainers1.reverse();5STL中的線性容器5.3：list容器19異常處理所有STL標(biāo)準(zhǔn)容器中，list對于異常安全性提供了最佳支持。push_back()如果不成功，就是無任何作用push_front()如果不成功，就是無任何作用insert()如果不成功，就是無任何作用pop_back()不拋出異常pop_front()不拋出異常erase()不拋出異常clear()不拋出異常5STL中的線性容器5.3：list容器20resize()如果不成功，就是無任何作用remove()只要元素間的比較動作拋出異常，它就不會拋出異常remove_if()只要判斷式不拋出異常，它就不會拋出異常unique()只要元素間的比較動作不拋出異常，它就不會拋出異常splice()不拋出異常merge()只要元素比較時不拋出異常，它便保證“或者成功，或者無任何作用”reverse()不拋出異常swap()不拋出異常5STL中的線性容器5.3：list容器215STL中的線性容器5.4：stack容器棧（stack）中的數(shù)據(jù)是先進(jìn)后出的（FirstInLastOut,FILO）。棧只有一個出口，允許新增元素（只能在棧頂上增加）、移出元素（只能移出棧頂元素）、取得棧頂元素等操作。在STL中，棧是以別的容器作為底部結(jié)構(gòu)，再將接口改變，使之符合棧的特性。既stack要依托與之前講過的3種容器中的某一種。（默認(rèn)是deque，請參看后邊的源碼）在STL中棧一共就5個常用操作函數(shù)：empty() 堆棧為空則返回真pop() 移除棧頂元素push() 在棧頂增加元素size() 返回棧中元素數(shù)目top() 返回棧頂元素225STL中的線性容器5.4：stack容器下面給出VS2005中stack的源碼：template<class_Ty,class_Container=deque<_Ty>>classstack{ //LIFOqueueimplementedwithacontainerpublic: typedef_Containercontainer_type; typedeftypename_Container::value_typevalue_type; typedeftypename_Container::size_typesize_type; typedeftypename_Container::referencereference; typedeftypename_Container::const_referenceconst_reference; stack():c() { //constructwithemptycontainer

}235STL中的線性容器5.4：stack容器 explicitstack(const_Container&_Cont):c(_Cont) { //constructbycopyingspecifiedcontainer

} boolempty()const { //testifstackisempty return(c.empty());

} size_typesize()const { //testlengthofstack return(c.size());

} referencetop() { //returnlastelementofmutablestack return(c.back());

}245STL中的線性容器5.4：stack容器 const_referencetop()const { //returnlastelementofnonmutablestack return(c.back());

} voidpush(constvalue_type&_Val) { //insertelementatend c.push_back(_Val);

} voidpop() { //eraselastelement c.pop_back();

} //protected: _Containerc; //theunderlyingcontainer};255STL中的線性容器5.4：stack容器stack的基本用法1：使用默認(rèn)的deque存儲數(shù)據(jù)#include<iostream>#include<stack>usingnamespacestd;voidmain(){ stack<int>myStack; intiSum=0; for(inti=1;i<=10;i++) myStack.push(i); while(!myStack.empty())

{ iSum+=myStack.top(); myStack.pop();

} cout<<"total:"<<iSum<<endl; system("pause");}265STL中的線性容器5.4：stack容器stack的基本用法2：使用默認(rèn)的vector存儲數(shù)據(jù)#include<iostream>#include<stack>#include<vector>usingnamespacestd;voidmain(){ stack<int,vector<int>>myStack_vector; for(inti=0;i<10;i++) myStack_vector.push(i); while(!myStack_vector.empty())

{ cout<<myStack_vector.top()<<","; myStack_vector.pop();

} system("pause");}275STL中的線性容器5.4：stack容器stack的基本用法3：使用默認(rèn)的list存儲數(shù)據(jù)#include<iostream>#include<stack>#include<list>usingnamespacestd;voidmain(){ stack<int,list<int>>myStack_list; for(inti=0;i<10;i++) myStack_list.push(i);

//取棧項數(shù)據(jù)并將數(shù)據(jù)彈出棧 while(!myStack_list.empty())

{ cout<<myStack_list.top()<<","; myStack_list.pop();

} system("pause");}285STL中的線性容器5.4：stack容器#include<iostream>#include<vector>#include<list>#include<deque>#include<stack>usingnamespacestd;voidmain(){ deque<int>myDeque(2,100); vector<int>myVector(3,200); stack<int>first; stack<int>second(myDeque); stack<int,vector<int>>third; stack<int,vector<int>>fourth(myVector);stack的基本用法4295STL中的線性容器5.4：stack容器 cout<<"sizeoffirst:"<<(int)first.size()<<endl; cout<<"sizeofsecond:"<<(int)second.size()<<endl; cout<<"sizeofthird:"<<(int)third.si