高質(zhì)量C++編程指南：標(biāo)準(zhǔn)模板庫(kù)（STL）

第八章、標(biāo)準(zhǔn)模板庫(kù)（STL）8．１基本概念

C++在1991年引入了模板技術(shù)，此后C++的編程概念和風(fēng)格都發(fā)生了很大的變化，原先用宏來實(shí)現(xiàn)的代碼紛紛都用模板來重新實(shí)現(xiàn)。模板在C++的重要應(yīng)用就是開發(fā)泛型庫(kù)，包括泛型容器和泛型算法。模板技術(shù)和運(yùn)算符重載成為C++實(shí)現(xiàn)泛型編程的兩大支柱。

泛型編程技術(shù)與面向?qū)ο缶幊滩o直接的聯(lián)系，甚至是背道而馳的：面向?qū)ο蟪珜?dǎo)把數(shù)據(jù)和操作綁定在一起，而泛型容器和算法則將數(shù)據(jù)和操作分離開來。實(shí)現(xiàn)泛型編程的方法不外乎下面幾種：**使用帶參數(shù)的宏。過去的通用函數(shù)就是用宏來編寫的。比如：MAX、MIN等。**使用void*。過去許多泛型算法就是使用它來實(shí)現(xiàn)的。**使用通用的根類和虛函數(shù)，比如：Java的Object。**使用模板技術(shù)。

宏的缺點(diǎn)是顯然的；void*是無類型的；通用根類很好，但是限制太死，而且動(dòng)態(tài)決議的開銷也是很可觀的，不能強(qiáng)制C++程序都使用它。只有模板最適合實(shí)現(xiàn)泛型編程，它不僅直觀，而且是類型安全的，也不會(huì)帶來任何額外的運(yùn)行開銷。

模板通過把數(shù)據(jù)類型參數(shù)化實(shí)現(xiàn)了類型無關(guān)，從而可以提高程序的可重用性和可移植性。

STL支持多種容器類型，這些容器的類型分為序列式容器和結(jié)合容器。指示器對(duì)象類似于C++的指針，它的層次結(jié)構(gòu)管理了對(duì)容器的訪問，指示器指向容器中的對(duì)象并允許程序以各種方法在容器中用指示器提取對(duì)象。

所有的容器都有通用的管理成員函數(shù)，如insert()、erase()、begin()、end()等。模板定義中定義了這些成員函數(shù)。容器類型是用模板實(shí)現(xiàn)的，當(dāng)程序?qū)嵗萜鲗?duì)象時(shí)所給出模板參數(shù)確定了容器所包含的對(duì)象模型。8.2序列容器

STL用如下的模板類和適配器實(shí)現(xiàn)序列容器：std::vector:一種隨機(jī)訪問的數(shù)組類型，它提供了對(duì)數(shù)組元素的快速、隨機(jī)訪問，以及在序列尾部快速、隨機(jī)的插入和刪除操作。std::vector

對(duì)象可在需要的時(shí)候修改其自身大小。std::deque:一種隨機(jī)訪問的數(shù)組類型，它提供了在序列兩端快速的插入和刪除操作。std::deque對(duì)象可在需要的時(shí)候修改其自身大小。std::list:一種不支持隨機(jī)訪問的數(shù)組類型，因?yàn)镾TL以雙向鏈表的方式實(shí)現(xiàn)std::list

對(duì)象。所以訪問鏈表元素要用指針從鏈表的某個(gè)端點(diǎn)開始。插入和刪除操作所花的時(shí)間是固定的。也就是說std::list

對(duì)象插入和刪除一個(gè)元素所花的時(shí)間與元素在鏈表中的位置無關(guān)。std::queue:適配器容器類型，它用std::deque或std::list

對(duì)象創(chuàng)建一個(gè)排隊(duì)序列。一、向量模板類：1、構(gòu)造向量模板類對(duì)象：

std::vector對(duì)象提供對(duì)序列中元素隨機(jī)訪問，也可以順序訪問。類似于數(shù)組，但不同于數(shù)組,std::vector對(duì)象在運(yùn)行時(shí)可以動(dòng)態(tài)改變自身的大小以便容納任何數(shù)目的元素。

std::vector對(duì)象可以快速地在序列尾部插入和刪除元素，但在序列其它地方插入和刪除效率有所降低。這是因?yàn)閟td::vector對(duì)象必須移動(dòng)元素位置以容納新的元素。

使用std::vector對(duì)象必須包含其頭文件vector，其對(duì)象的構(gòu)造有下面幾種：

vector<type>name;//創(chuàng)建空對(duì)象vector<type>name(size);//創(chuàng)建一個(gè)大小為size對(duì)象vector<type>name(size,value);//創(chuàng)建一個(gè)大小為size，初值為value對(duì)象vector<type>name(mvector);//拷貝構(gòu)造函數(shù)vector<type>name(first,last);//構(gòu)造一個(gè)元素在某個(gè)范圍內(nèi)的向量。該范圍用first及l(fā)ast指示器來說明。2、使用向量模板類對(duì)象：例：#include<iostream.h>#include<vector>voidmain(void){usingnamespacestd;vector<int>mvector(10,1);//定義一個(gè)int型mvector對(duì)象

vector<int>::iterator

iter;//定義一個(gè)int容器指示器指針

for(iter=mvector.begin();iter!=mvector.end();iter++)

cout<<*iter<<“;”;//遍歷對(duì)象mvector

}

容器指示器就是指向容器中元素的指針，通過它來訪問容器中的元素。3、向量模板類對(duì)象的其他操作push_back(x):把值x插入到向量尾部。pop_back():刪除向量中的最后一個(gè)元素。insert(i,x):把值x插入到指示器i指向的位置insert(i,start,end):把指示器start和end所指定范圍的值插入到向量指示器i所指定的位置。erase(i):刪除指示器i所指的向量元素。begin():返回指向向量中第一個(gè)元素的指示器

end():返回指向向量中最后一個(gè)元素的指示器

at(n):返回向量中位置n處的元素值。size():返回向量的大小（元素的個(gè)數(shù)）。clear():刪除向量的所有元素。empty():如果向量為空，則返回TRUE。reverse():反轉(zhuǎn)元素順序。

capacity():返回向量當(dāng)前所能容納的最多元素個(gè)數(shù)。例：利用向量模板類寫出求大數(shù)階乘精確值得代碼：#include<iostream.h>#include<vector>#include<windows.h>

voidmain(void){usingnamespacestd;vector<int>intvector(1,1);vector<int>::iterator

iter;

intm=0,n,s;//格式化輸出計(jì)數(shù),for循環(huán)計(jì)數(shù)用

intcarry=0;//進(jìn)位值

cout<<"請(qǐng)輸入一個(gè)整數(shù)::n="; cin>>n;DWORDTime1=GetTickCount();

for(s=1;s<=n;s++) {carry=0;

for(iter=intvector.begin();iter!=intvector.end();iter++){*iter=*iter*s+carry;carry=*iter/10;*iter=*iter%10;}

while(carry>0){m=carry%10; carry=carry/10;intvector.push_back(m);}

if(carry>0)intvector.push_back(carry); }n=0;//控制格式化輸出每行60個(gè)字符

for(m=intvector.size()-1;m>=0;m--) {cout<<intvector.at(m);n++; if(n%60==0)cout<<endl;}DWORDTime=GetTickCount()-Time1;

cout<<endl<<Time<<“ms”<<endl;}//統(tǒng)計(jì)計(jì)算的時(shí)間為毫秒4、兩個(gè)向量的比較：模板類std::vector定義了一組完整的運(yùn)算符，這些運(yùn)算符可以比較std::vector對(duì)象，當(dāng)兩個(gè)向量有相同個(gè)數(shù)的元素時(shí)，且元素值也相同時(shí)，這兩個(gè)向量就是相等的，也可以判定一個(gè)向量小于或大于另一個(gè)向量。例如：voidmain(){usingnamespacestd;vector<char>vector1;vector<char>vector2;for(inti=0;i<10;i++){vector1.push_back(65+i);

//寫入：ABCDEFGHIJ

vector2.push_back(68+i);}

//寫入：DEFGHIJKLMif(vector1==vector2)

//比較2個(gè)向量的大小cout<<“vector1==vector2”<<endl;elseif(vector1>vector2)cout<<“vector1>vector2”<<endl;elseif(vector1<vector2)cout<<“vector1<vector2”<<endl;}//結(jié)果為：vector1<vector2二、雙端隊(duì)列模板類1、構(gòu)造雙端隊(duì)列模板類對(duì)象：對(duì)象std::deque類似于向量，但雙端隊(duì)列對(duì)象可以在序列的兩端放置元素和刪除元素，并且是高效的。std::deque對(duì)象提供了對(duì)其元素的隨機(jī)訪問，也能在需要的時(shí)候動(dòng)態(tài)改變自身大小，但在向量中的插入和刪除操作不那么有效。構(gòu)造std::deque對(duì)象必須包含頭文件<deque>,構(gòu)造方式有下面幾種：std::deque<type>name;//創(chuàng)建空對(duì)象std::deque<type>name(size);//創(chuàng)建一個(gè)大小為size對(duì)象std::deque<type>name(size,value);//創(chuàng)建一個(gè)大小為size，初值為value對(duì)象std::deque<type>name(mydeque);//拷貝構(gòu)造函數(shù)std::deque<type>name(first,last);//構(gòu)造一個(gè)元素在某個(gè)范圍內(nèi)的向量。該范圍用first及l(fā)ast指示器來說明。2、雙端隊(duì)列對(duì)象的使用：例：

#include<iostream.h>

#include<deque>voidmain(void){usingnamespacestd;

deque<int>mdeque(10,1);

//定義一個(gè)int型mdeque對(duì)象

deque<int>::iterator

iter;

//定義一個(gè)int容器指示器指針

for(iter=mdeque.begin();iter!=mdeque.end();iter++)

cout<<*iter<<“;”;

//遍歷對(duì)象mdeque

}

程序創(chuàng)建了有10個(gè)元素的std::deque對(duì)象，所有元素都被初始化為1，

程序開始包含了頭文件#include<deque>，最后遍歷顯示每個(gè)元素。3、雙端隊(duì)列模板類對(duì)象的其他操作push_back(x):把值x插入到雙端隊(duì)列尾部。push_front(x):把值x插入到雙端隊(duì)列頭部。pop_back():刪除雙端隊(duì)列的最后一個(gè)元素。pop_front():刪除雙端隊(duì)列的第一個(gè)元素。insert(i,x):把值x插入到指示器i指向的位置insert(i,start,end):把指示器start和end所指定范圍的值插入到指示器i所指定的位置。erase(i):刪除指示器i所指的雙端隊(duì)列元素。begin():返回指向雙端隊(duì)列第一個(gè)元素的指示器

end():返回指向雙端隊(duì)列最后一個(gè)元素的指示器

at(n):返回雙端隊(duì)列中位置n處的元素值。size():返回雙端隊(duì)列的大小（元素的個(gè)數(shù)）。clear():刪除雙端隊(duì)列的所有元素。empty():如果雙端隊(duì)列為空，則返回TRUE。swap(deque):交換2個(gè)雙端隊(duì)列的內(nèi)容。

例：利用雙端隊(duì)列模板類寫出求大數(shù)階乘精確值得代碼：#include<iostream.h>#include<windows.h>#include<deque>

voidmain(void){usingnamespacestd;

deque<int>intdeque(1,1);

deque<int>::iterator

iter;

intm=0,n,s;//格式化輸出計(jì)數(shù),for循環(huán)計(jì)數(shù)用

intcarry=0;//進(jìn)位值

cout<<"請(qǐng)輸入一個(gè)整數(shù)::n="; cin>>n;DWORDTime1=GetTickCount();

for(s=1;s<=n;s++) {carry=0;for(iter=intdeque.begin();iter!=intdeque.end();iter++){*iter=*iter*s+carry;carry=*iter/10;*iter=*iter%10;}

while(carry>0){m=carry%10; carry=carry/10;intdeque.push_back(m);}

if(carry>0)intdeque.push_back(carry); }

n=0;//控制格式化輸出每行60個(gè)字符for(iter=intdeque.end()-1;iter!=intdeque.begin();iter--) {

cout<<*iter;n++; if(n%60==0)cout<<endl;}cout<<*iter;

DWORDTime=GetTickCount()-Time1;

cout<<endl<<Time<<"ms"<<endl;}//統(tǒng)計(jì)計(jì)算的時(shí)間為毫秒4、兩個(gè)雙端隊(duì)列的比較：模板類std::deque定義了一組完整的運(yùn)算符，這些運(yùn)算符可以比較std::deque對(duì)象，當(dāng)兩個(gè)雙端隊(duì)列有相同個(gè)數(shù)的元素時(shí)，且元素值也相同時(shí)，這兩個(gè)雙端隊(duì)列就是相等的，也可以判定一個(gè)雙端隊(duì)列小于或大于另一個(gè)雙端隊(duì)列。例如：voidmain(){usingnamespacestd;deque<char>deque1;deque<char>deque2;for(inti=0;i<10;i++){deque1.push_back(65+i);

//寫入：ABCDEFGHIJ

deque2.push_back(68+i);}

//寫入：DEFGHIJKLMif(deque1==deque2)

//比較2個(gè)雙端隊(duì)列的大小cout<<“deque1==deque2”<<endl;elseif(deque1>deque2)cout<<“deque1>deque2”<<endl;elseif(deque1<deque2)cout<<“deque1<deque2”<<endl;}//結(jié)果為：deque1<deque2三、鏈表模板類1、構(gòu)造鏈表模板類對(duì)象：對(duì)象std::list類似于向量和雙端隊(duì)列，只不過鏈表對(duì)象提供了對(duì)元素的隨機(jī)訪問。但是std::list對(duì)象在序列中的任何位置放置元素和刪除元素都是高效的。std::list對(duì)象也能在需要的時(shí)候動(dòng)態(tài)改變自身大小。構(gòu)造std::list對(duì)象必須包含頭文件<list>,構(gòu)造方式有下面幾種：std::list<type>name;//創(chuàng)建空對(duì)象std::list<type>name(size);//創(chuàng)建一個(gè)大小為size對(duì)象std::list<type>name(size,value);//創(chuàng)建一個(gè)大小為size，初值為value對(duì)象std::list<type>name(mydeque);//拷貝構(gòu)造函數(shù)std::list<type>name(first,last);//構(gòu)造一個(gè)元素在某個(gè)范圍內(nèi)的向量。該范圍用first及l(fā)ast指示器來說明。2、鏈表對(duì)象的使用：例：

#include<iostream.h>

#include<list>voidmain(void){usingnamespacestd;

list<int>mlist(10,1);

//定義一個(gè)int型mlist對(duì)象

list<int>::iterator

iter;

//定義一個(gè)int容器指示器指針

for(iter=mlist.begin();iter!=mlist.end();iter++)

cout<<*iter<<“;”;

//遍歷對(duì)象mdeque

}

程序創(chuàng)建了有10個(gè)元素的std::list對(duì)象，所有元素都被初始化為1，

程序開始包含了頭文件#include<list>，最后遍歷顯示每個(gè)元素。3、鏈表類模板對(duì)象的其他操作push_back(x):把值x插入到鏈表尾部。push_front(x):把值x插入到鏈表頭部。pop_back():刪除鏈表的最后一個(gè)元素。pop_front():刪除鏈表的第一個(gè)元素。insert(i,x):把值x插入到指示器i指向的位置insert(i,start,end):把指示器start和end所指定范圍的值插入到指示器i所指定的位置。erase(start,end):刪除指示器start和end所指范圍的鏈表元素。erase(i):刪除指示器i所指的鏈表元素。begin():返回指向鏈表第一個(gè)元素的指示器

end():返回指向鏈表中最后一個(gè)元素的指示器

back():返回對(duì)鏈表尾部元素的引用。front():返回對(duì)鏈表起始元素的引用。size():返回鏈表的大?。ㄔ氐膫€(gè)數(shù)）。clear():刪除鏈表中的所有元素。empty():如果鏈表為空，則返回TRUE。swap(deque):交換2個(gè)鏈表的內(nèi)容。

例：利用鏈表模板類寫出求大數(shù)階乘精確值得代碼：#include<iostream.h>#include<windows.h>#include<list>

voidmain(void){usingnamespacestd;list<int>intlist(1,1);list<int>::iterator

iter;

intm=0,n,s;//格式化輸出計(jì)數(shù),for循環(huán)計(jì)數(shù)用

intcarry=0;//進(jìn)位值

cout<<"請(qǐng)輸入一個(gè)整數(shù)::n="; cin>>n;DWORDTime1=GetTickCount();

for(s=1;s<=n;s++) {carry=0;for(iter=intlist.begin();iter!=intlist.end();iter++){*iter=*iter*s+carry;carry=*iter/10;*iter=*iter%10;}

while(carry>0){m=carry%10; carry=carry/10;intlist.push_back(m);}if(carry>0)intlist.push_back(carry); }

n=0;//控制格式化輸出每行60個(gè)字符intlist.reverse();for(iter=intlist.begin();iter!=intlist.end();iter++) {cout<<*iter;n++; if(n%60==0)cout<<endl;}//cout<<*iter;

DWORDTime=GetTickCount()-Time1;

cout<<endl<<Time/1000.0<<"s"<<endl;}

//統(tǒng)計(jì)計(jì)算的時(shí)間為毫秒4、兩個(gè)鏈表的比較：類模板std::list定義了一組完整的運(yùn)算符，這些運(yùn)算符可以比較std::list對(duì)象，當(dāng)兩個(gè)雙端隊(duì)列有相同個(gè)數(shù)的元素時(shí)，且元素值也相同時(shí)，這兩個(gè)鏈表就是相等的，也可以判定一個(gè)鏈表小于或大于另一個(gè)鏈表。例如：voidmain(){usingnamespacestd;list<char>list1;list<char>list2;for(inti=0;i<10;i++){list1.push_back(65+i);

//寫入：ABCDEFGHIJ

list2.push_back(68+i);}

//寫入：DEFGHIJKLMif(list1==list2)

//比較2個(gè)鏈表的大小cout<<“l(fā)ist1==list2”<<endl;elseif(list1>list2)cout<<“l(fā)ist1>list2”<<endl;elseif(list1<list2)cout<<“l(fā)ist1<list2”<<endl;}//結(jié)果為：list1<list2四、容器適配器std::stack1、容器適配器std::stack的構(gòu)造：

堆棧是一種序列，它實(shí)現(xiàn)了對(duì)元素的先進(jìn)后出的操作，因?yàn)槎褩Ｊ且环N通用的數(shù)據(jù)結(jié)構(gòu)，所以STL實(shí)現(xiàn)了堆棧。在STL中的堆棧不是用類模板實(shí)現(xiàn)的，而是用名為std::stack的容器適配器實(shí)現(xiàn)的，容器適配器std::stack可以從std::vector、std::deque、std::list對(duì)象創(chuàng)建一個(gè)堆棧。構(gòu)造一個(gè)std::stack對(duì)象的方法為：

std::stack<type,container>name;

參數(shù)type是堆棧所操作的數(shù)據(jù)類型，container參數(shù)是實(shí)現(xiàn)堆棧所用的容器類型（std::vector、std::deque或std::list）。例如，基于std::list對(duì)象為整數(shù)數(shù)據(jù)類型創(chuàng)建std::stack對(duì)象的方法是：

std::stack<int,std::list<int>

>intstack;2、容器適配器std::stack的操作：因?yàn)槎褩Ｊ且环N簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，所以它只需要一些簡(jiǎn)單操作。因此std::stack容器適配器只定義了函數(shù)：empty():

堆棧清空。size():

獲得堆棧大小。top():

取堆棧頂數(shù)據(jù)。push():

數(shù)據(jù)壓棧。pop():

數(shù)據(jù)彈出堆棧。使用堆棧必須包含相應(yīng)頭文件<stack>。例子：#include<list>#include<stack>voidmain(void){usingnamespacestd;stack<int,list<int>>intstack;for(inti=1;i<8;i++){intstack.push(i*10);cout<<10*i<<“;”;}//10;20;30;40;50;60;70cout<<endl;intsize=intstack.size();//獲得堆棧的大小for(i=0;i<size;i++){cout<<intstack.top()<<“;”;//70;60;50;40;30;20;10

intstack.pop();}}五、容器適配器std::queue1、容器適配器std::queue的構(gòu)造：

隊(duì)列數(shù)據(jù)結(jié)構(gòu)對(duì)其元素實(shí)現(xiàn)了先進(jìn)先出的操作，也就是說隊(duì)列中的元素在一端插入，在另一端刪除。STL用名為std::queue的容器實(shí)現(xiàn)了隊(duì)列。容器適配器std::queue可用來從std::deque或std::list對(duì)象創(chuàng)建隊(duì)列。

構(gòu)造std::queue對(duì)象的方法：

std::queue<type,container>;

參數(shù)type是隊(duì)列所操作的數(shù)據(jù)類型。container是用于實(shí)現(xiàn)隊(duì)列的容器類型（std::deque或std::list），例如：基于std::list對(duì)象為整數(shù)數(shù)據(jù)類型創(chuàng)建std::queue對(duì)象的方法是：std::queue<int,std::list<int>>myque;1、容器適配器std::queue的操作：

隊(duì)列也是一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，所以只需要一些基本的操作。主要有：empty():清空隊(duì)列。size():返回隊(duì)列的大小。front():置隊(duì)列首。back():置隊(duì)列尾。push():壓入隊(duì)列。pop():彈出隊(duì)列。下面的例子說明對(duì)列的使用。#include<list>#include<queue>voidmain(void){usingnamespacestd;queue<int,list<int>>intqueue;for(inti=1;i<8;i++){intqueue.push(i*10);cout<<10*i<<“;”;}//10;20;30;40;50;60;70cout<<endl;intsize=intqueue.size();//獲得隊(duì)列的大小for(i=0;i<size;i++){cout<<intqueue.front()<<“;”;//10;20;30;40;50;60;70

intqueue.pop();}}8.3

結(jié)合容器

結(jié)合容器不同于序列，在容器中每一個(gè)元素都有一個(gè)關(guān)鍵詞，通過它可以找到相應(yīng)元素。結(jié)合容器主要有：std::set

一種隨機(jī)存取的容器。其關(guān)鍵詞和數(shù)據(jù)元素時(shí)同一個(gè)值，也就是說它不能夠包含重復(fù)的元素。std::multiset

與std::set相似，不同的是std::multiset容器可以包含重復(fù)的元素。std::map

這是一種包含成對(duì)數(shù)值的容器類型。其中一個(gè)值是實(shí)際數(shù)據(jù)值，另一個(gè)是用來尋找數(shù)據(jù)的關(guān)鍵值。一個(gè)特定的關(guān)鍵詞只能與一個(gè)元素相聯(lián)系。std::multimap

與std::map

類似，所不同的是一個(gè)關(guān)鍵詞可以與多個(gè)數(shù)據(jù)元素向聯(lián)系。一、std::set集合容器1、構(gòu)造集合容器std::set

：std::set對(duì)象可以使程序按照次序來存儲(chǔ)一組數(shù)值。在一個(gè)集合中，元素既作為被存儲(chǔ)的數(shù)據(jù)又作為數(shù)據(jù)的關(guān)鍵值。本質(zhì)上一個(gè)集合就是一個(gè)有序的排列?？梢杂孟铝械姆椒▌?chuàng)建std::set對(duì)象：std::set<type,predicate>name;std::set<type,predicate>name(myset);std::set<type,predicate>name(first,last);默認(rèn)的謂詞是std::less<>，即從小到大排序。例如要給整數(shù)創(chuàng)建一個(gè)空的set對(duì)象：std::set<int,std::less<int>>myset;2、使用集合容器：例：#include<iostream.h>#include<set>voidmain(void){usingnamespacestd;

set<int>myset;//定義一個(gè)int型mvector對(duì)象

set<int>::iterator

iter;//定義一個(gè)int容器指示器指針

myset.insert(10);myset.insert(5);myset.insert(3);myset.insert(1);myset.insert(8);myset.insert(6);

for(iter=myset.begin();iter!=myset.end();iter++)

cout<<*iter<<“;”;//遍歷對(duì)象mvector

}//輸出1；3；5；6；8；103、集合容器的其它操作：begin():返回指向集合中第一個(gè)元素的指示器

clear():刪除集合的所有元素。count(x):返回元素x在集合中出現(xiàn)的次數(shù)（0或1次）empty():如果集合為空，則返回TRUE。end():返回指向集合中最后一個(gè)元素的指示器erase(i):刪除指示器i所指的集合元素。erase(x):刪除集合元素x。find(x):返回指向x的指示器。如果x不存在，則返回指示器與end（）相等insert(i,x):把值x插入到指示器i指向的元素之前insert(start,end):把指示器start和end所指定范圍的值插入到集合中insert(x):把值x插入到集合中size():返回集合的大?。ㄔ氐膫€(gè)數(shù)）。swap(set):交換2個(gè)集合的內(nèi)容。

max_size():返回集合當(dāng)前所能容納的最多元素個(gè)數(shù)。二、std::multiset多重集合容器1、構(gòu)造多重集合容器std::multiset

：

std::multiset對(duì)象可以使程序按照次序來存儲(chǔ)一組數(shù)值。在一個(gè)多重集合中，元素既作為被存儲(chǔ)的數(shù)據(jù)又作為數(shù)據(jù)的關(guān)鍵值。本質(zhì)上一個(gè)多重集合就是一個(gè)有序的排列。多重集合可以包含重復(fù)的數(shù)據(jù)。用下列的方法可以創(chuàng)建std::multiset對(duì)象：std::multisetset<type,predicate>name;std::multisetset<type,predicate>name(myset);std::multisetset<type,predicate>name(first,last);

默認(rèn)的謂詞是std::less<>，即從小到大排序。例如要給整數(shù)創(chuàng)建一個(gè)空的multisetset對(duì)象：std::multisetset<int,std::less<int>>myset;2、使用多重集合容器：例：#include<iostream.h>#include<set>voidmain(void){usingnamespacestd;

multiset<int>myset;//定義一個(gè)int型mvector對(duì)象

multiset<int>::iterator

iter;//定義一個(gè)int容器指示器指針

myset.insert(10);myset.insert(5);myset.insert(3);myset.insert(1);myset.insert(5);myset.insert(8);myset.insert(6);myset.insert(8);

for(iter=myset.begin();iter!=myset.end();

iter++)

cout<<*iter<<“;”;//遍歷對(duì)象mvector

}//輸出1；3；5；5；6；8；8；103、多重集合容器的其它操作：begin():返回指向多重集合中第一個(gè)元素的指示器

clear():刪除多重集合的所有元素。count(x):返回元素x在多重集合中出現(xiàn)的次數(shù)empty():如果多重集合為空，則返回TRUE。end():返回指向多重集合中最后一個(gè)元素的指示器erase(i):刪除指示器i所指的多重集合元素。erase(x):刪除多重集合元素x。find(x):返回指向x的指示器。如果x不存在，則返回指示器與end（）相等insert(i,x):把值x插入到指示器i指向的元素之前insert(start,end):把指示器start和end所指定范圍的值插入到集合中insert(x):把值x插入到多重集合中size():返回多重集合的大?。ㄔ氐膫€(gè)數(shù)）。swap(set):交換2個(gè)多重集合的內(nèi)容。

max_size():返回多重集合當(dāng)前所能容納的最多元素個(gè)數(shù)。三、std::map映射容器1、構(gòu)造std::map映射容器

std::map對(duì)象可以使程序按照次序來存儲(chǔ)一組數(shù)值。每一個(gè)元素都與一個(gè)查詢關(guān)鍵值相關(guān)。可以使用下面方法來創(chuàng)建std::map對(duì)象：std::map<key,type,predicate>name;std::map<key,type,predicate>name(myset);std::map<key,type,predicate>name(first,last);

key參數(shù)是在映射中所使用的關(guān)鍵詞類型。例如要構(gòu)造一個(gè)整數(shù)的空std::map對(duì)象：std::map<int,int,std::less<int>>name;

std::less<int>默認(rèn)謂詞，不需要再聲明中包含2、使用std::map映射容器例：#include<iostream.h>#include<map>voidmain(void){usingnamespacestd;map<int,char>mymap;//定義一個(gè)int型mvector對(duì)象

map<int,char>::iterator

iter;//定義一個(gè)int容器指示器指針

mymap.insert(map<int,char>::value_type(1,’X’));

mymap.insert(map<int,char>::value_type(2,’B’));

mymap.insert(map<int,char>::value_type(3,’E’));

mymap.insert(map<int,char>::value_type(4,’H’));

mymap.insert(map<int,char>::value_type(5,’F’));

for(iter=mymap.begin();iter!=mymap.end();

iter++){

cout<<(*iter).first<<“

”;

cout<<(*iter).second<<“;”;}//遍歷對(duì)象mvector

}//輸出1->X;2->B;3->E;4->H;5->F;3、對(duì)映射進(jìn)行搜索iter=mymap.find(4);if(iter==mymap.end())cout<<“elementnotfound”<<endl;elsecout<<“element:”<<(*iter).second;//輸出：

element:H4、映射成員函數(shù)begin():返回指向映射中第一個(gè)元素的指示器

clear():刪除映射中的所有元素。count(x):返回元素x在映射中出現(xiàn)的次數(shù)（0或1）empty():如果映射為空，則返回TRUE。end():返回指向映射中最后一個(gè)元素的指示器erase(i):刪除指示器i所指的映射元素。erase(x):刪除映射元素x。find(x):返回指向x的指示器。如果x不存在，則返回指示器與end（）相等insert(i,x):把值x插入到指示器i指向的元素之前insert(start,end):把指示器start和end所指定范圍的值插入到映射中insert(x):把值x插入到映射中size():返回映射的大?。ㄔ氐膫€(gè)數(shù)）。swap(set):交換2個(gè)映射的內(nèi)容。

max_size():返回映射當(dāng)前所能容納的最多元素個(gè)數(shù)。四、std::multimap多重映射容器std::multimap對(duì)象可以使程序按照次序來存儲(chǔ)一組數(shù)值。每一個(gè)元素都與一個(gè)查詢關(guān)鍵值相關(guān)。與映射不同，多重映射可以包含重復(fù)的數(shù)據(jù)值。可以使用下面方法來創(chuàng)建std::multimap對(duì)象：std::multimap<key,type,predicate>name;std::multimap<key,type,predicate>name(myset);std::multimap<key,type,predicate>name(first,last);

key參數(shù)是在映射中所使用的關(guān)鍵詞類型。例如要構(gòu)造一個(gè)整數(shù)的空std::map對(duì)象：std::multimap<int,int,std::less<int>>name;

std::less<int>默認(rèn)謂詞，不需要再聲明中包含std::multimap的使用以及它的操作函數(shù)同std::map，這里不再敘述。8.4

通用算法STL提供了很多類型的容器，可以用來操縱不同數(shù)據(jù)類型的數(shù)值。為了能夠更方便地操作這些容器的內(nèi)容，STL提供了一整套通用算法，可以用來做從查找元素到對(duì)元素排序的任何事情，要使用這些算法需要包含頭文件algorithm。一、非修正序列算法：即算法不修改容器的內(nèi)容，STL定義了九個(gè)非修正序列算法。1、adjacent_find(first,last)返回指向一對(duì)鄰近相等元素中的第一個(gè)元素的指示器。函數(shù)搜索指示器first及l(fā)ast所規(guī)定的范圍。2、count(first,last,val)返回一個(gè)序列中具有某個(gè)特定值val的元素個(gè)數(shù)。函數(shù)搜索指示器first及l(fā)ast所規(guī)定的范圍。3、equal(first,last,first2)如果指示器first及l(fā)ast所規(guī)定的范圍的值與從指示器first2起始相同范圍的值相等，函數(shù)返回真。4、find(first,last,val)返回指示器first及l(fā)ast所規(guī)定的范圍里的第一個(gè)數(shù)值等于val的元素指示器。5、for_each(first,last，func)對(duì)范圍first、last里的每一個(gè)元素執(zhí)行由函數(shù)func所定義的操作。例：for_each函數(shù)的使用#include<set>#include<algorithm>voidshow(int

val){cout<<val<<““;}

voidmain(void){multiset<int,less<int>>samp;samp.insert(10);samp.insert(8);samp.insert(3);samp.insert(8);samp.insert(5);samp.insert(8);for_each(samp.begin(),samp.end(),show);}//13588810二、修正序列算法：某些種類的序列操作可能會(huì)修改容器的內(nèi)容，STL修正序列算法提供了這樣的操作。1、copy(first,last,first2)把指示器first及l(fā)ast所規(guī)定的范圍中的元素復(fù)制到另一個(gè)由指示器first2指向的元素所開始的范圍2、copy_backward(first,last,first2)把指示器first及l(fā)ast所規(guī)定的范圍中的元素復(fù)制到另一個(gè)由指示器first2指向的元素所開始的范圍。但是這個(gè)函數(shù)是從最后一個(gè)元素開始復(fù)制由后向前直到第一個(gè)元素。3、fill(first,last,val)把數(shù)值val賦值到由指示器first及l(fā)ast所規(guī)定的范圍中的所有元素。4、generate(first,last,func)對(duì)每一個(gè)元素調(diào)用func函數(shù)，把函數(shù)結(jié)果復(fù)制到元素中。5、remove(first,last,val)在指示器first及l(fā)ast所規(guī)定的范圍中刪除所有等于val的元素。6、replace(first,last,val1,val2)在指示器first及l(fā)ast所規(guī)定的范圍中用val2替代所有的val1。7、reverse(first,last)把指示器first及l(fā)ast所規(guī)定的范圍中元素顛倒排列。8、swap(it1,it2)交換指示器it1和it2里的兩個(gè)元素。9、unique(first,last)刪除指示器first及l(fā)ast所規(guī)定的范圍中重復(fù)的相鄰元素。例：generate(first,last,func)使用#include<iostream.h>#include<vector>#include<algorithm>

int

sum(void){staticintm;for(ints=1;s<5;s++)m+=2*s;//m=2+4+6+8returnm;}

voidshow(int

val){cout<<val<<"";}

voidmain(void){usingnamespacestd;vector<int>myvector(6);//定義一個(gè)int型myector對(duì)象generate(myvector.begin(),myvector.end(),sum);for_each(myvector.begin(),myvector.end(),show);}//輸出：20406080100120三、排序算法：STL提供了對(duì)容器內(nèi)容進(jìn)行排序的許多函數(shù)，其中主要的有：1、merge(first,last,first1,last1,result)把first,last規(guī)定的序列與first1,last1規(guī)定的序列中的元素一起進(jìn)行排序，結(jié)果放到以result開始的序列中。2、partial_sort_copy(first,last,first1,last1)把指示器first及l(fā)ast規(guī)定的范圍中的元素進(jìn)行排序，并把排序的結(jié)果放到以first1開始到last1結(jié)束的序列中，并且不超過last1。3、sort(first,last)順序排列指示器first及l(fā)ast規(guī)定的范圍中的元素。例：

partial_sort_copy(first,last,first1,last1)函數(shù)#include<iostream>#include<algorithm>#include<vector>voidmain(){usingnamespacestd;vector<int>Numbers(8);vector<int>Result(5);vector<int>::iteratorstart,end,it;

Numbers[0]=4;Num