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

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

C++在1991年引入了模板技術(shù)，此后C++的編程概念和風(fēng)格都發(fā)生了很大的變化，原先用宏來實(shí)現(xiàn)的代碼紛紛都用模板來重新實(shí)現(xiàn)。模板在C++的重要應(yīng)用就是開發(fā)泛型庫，包括泛型容器和泛型算法。模板技術(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*是無類型的；通用根類很好，但是限制太死，而且動態(tài)決議的開銷也是很可觀的，不能強(qiáng)制C++程序都使用它。只有模板最適合實(shí)現(xiàn)泛型編程，它不僅直觀，而且是類型安全的，也不會帶來任何額外的運(yùn)行開銷。

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

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

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

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

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

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

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

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

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

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

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

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

vector<int>::iterator

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

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

cout<<*iter<<“;”;//遍歷對象mvector

}

容器指示器就是指向容器中元素的指針，通過它來訪問容器中的元素。3、向量模板類對象的其他操作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<<"請輸入一個(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對象，當(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ì)列模板類對象：對象std::deque類似于向量，但雙端隊(duì)列對象可以在序列的兩端放置元素和刪除元素，并且是高效的。std::deque對象提供了對其元素的隨機(jī)訪問，也能在需要的時(shí)候動態(tài)改變自身大小，但在向量中的插入和刪除操作不那么有效。構(gòu)造std::deque對象必須包含頭文件<deque>,構(gòu)造方式有下面幾種：std::deque<type>name;//創(chuàng)建空對象std::deque<type>name(size);//創(chuàng)建一個(gè)大小為size對象std::deque<type>name(size,value);//創(chuàng)建一個(gè)大小為size，初值為value對象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ì)列對象的使用：例：

#include<iostream.h>

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

deque<int>mdeque(10,1);

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

deque<int>::iterator

iter;

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

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

cout<<*iter<<“;”;

//遍歷對象mdeque

}

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

程序開始包含了頭文件#include<deque>，最后遍歷顯示每個(gè)元素。3、雙端隊(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<<"請輸入一個(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對象，當(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)造鏈表模板類對象：對象std::list類似于向量和雙端隊(duì)列，只不過鏈表對象提供了對元素的隨機(jī)訪問。但是std::list對象在序列中的任何位置放置元素和刪除元素都是高效的。std::list對象也能在需要的時(shí)候動態(tài)改變自身大小。構(gòu)造std::list對象必須包含頭文件<list>,構(gòu)造方式有下面幾種：std::list<type>name;//創(chuàng)建空對象std::list<type>name(size);//創(chuàng)建一個(gè)大小為size對象std::list<type>name(size,value);//創(chuàng)建一個(gè)大小為size，初值為value對象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、鏈表對象的使用：例：

#include<iostream.h>

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

list<int>mlist(10,1);

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

list<int>::iterator

iter;

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

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

cout<<*iter<<“;”;

//遍歷對象mdeque

}

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

程序開始包含了頭文件#include<list>，最后遍歷顯示每個(gè)元素。3、鏈表類模板對象的其他操作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():返回對鏈表尾部元素的引用。front():返回對鏈表起始元素的引用。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<<"請輸入一個(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對象，當(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)了對元素的先進(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對象創(chuàng)建一個(gè)堆棧。構(gòu)造一個(gè)std::stack對象的方法為：

std::stack<type,container>name;

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

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

>intstack;2、容器適配器std::stack的操作：因?yàn)槎褩Ｊ且环N簡單的數(shù)據(jù)結(jié)構(gòu)，所以它只需要一些簡單操作。因此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)對其元素實(shí)現(xiàn)了先進(jìn)先出的操作，也就是說隊(duì)列中的元素在一端插入，在另一端刪除。STL用名為std::queue的容器實(shí)現(xiàn)了隊(duì)列。容器適配器std::queue可用來從std::deque或std::list對象創(chuàng)建隊(duì)列。

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

std::queue<type,container>;

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

隊(duì)列也是一種簡單的數(shù)據(jù)結(jié)構(gòu)，所以只需要一些基本的操作。主要有：empty():清空隊(duì)列。size():返回隊(duì)列的大小。front():置隊(duì)列首。back():置隊(duì)列尾。push():壓入隊(duì)列。pop():彈出隊(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

這是一種包含成對數(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對象可以使程序按照次序來存儲一組數(shù)值。在一個(gè)集合中，元素既作為被存儲的數(shù)據(jù)又作為數(shù)據(jù)的關(guān)鍵值。本質(zhì)上一個(gè)集合就是一個(gè)有序的排列?？梢杂孟铝械姆椒▌?chuàng)建std::set對象：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對象：std::set<int,std::less<int>>myset;2、使用集合容器：例：#include<iostream.h>#include<set>voidmain(void){usingnamespacestd;

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

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<<“;”;//遍歷對象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對象可以使程序按照次序來存儲一組數(shù)值。在一個(gè)多重集合中，元素既作為被存儲的數(shù)據(jù)又作為數(shù)據(jù)的關(guān)鍵值。本質(zhì)上一個(gè)多重集合就是一個(gè)有序的排列。多重集合可以包含重復(fù)的數(shù)據(jù)。用下列的方法可以創(chuàng)建std::multiset對象：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對象：std::multisetset<int,std::less<int>>myset;2、使用多重集合容器：例：#include<iostream.h>#include<set>voidmain(void){usingnamespacestd;

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

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<<“;”;//遍歷對象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對象可以使程序按照次序來存儲一組數(shù)值。每一個(gè)元素都與一個(gè)查詢關(guān)鍵值相關(guān)。可以使用下面方法來創(chuàng)建std::map對象：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對象：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對象

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<<“;”;}//遍歷對象mvector

}//輸出1->X;2->B;3->E;4->H;5->F;3、對映射進(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對象可以使程序按照次序來存儲一組數(shù)值。每一個(gè)元素都與一個(gè)查詢關(guān)鍵值相關(guān)。與映射不同，多重映射可以包含重復(fù)的數(shù)據(jù)值?？梢允褂孟旅娣椒▉韯?chuàng)建std::multimap對象：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對象：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提供了一整套通用算法，可以用來做從查找元素到對元素排序的任何事情，要使用這些算法需要包含頭文件algorithm。一、非修正序列算法：即算法不修改容器的內(nèi)容，STL定義了九個(gè)非修正序列算法。1、adjacent_find(first,last)返回指向一對鄰近相等元素中的第一個(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)對范圍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二、修正序列算法：某些種類的序列操作可能會修改容器的內(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)對每一個(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對象generate(myvector.begin(),myvector.end(),sum);for_each(myvector.begin(),myvector.end(),show);}//輸出：20406080100120三、排序算法：STL提供了對容器內(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