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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

vector<int>::iterator

iter;//定義一個int容器指示器指針

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

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

}

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

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

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

capacity():返回向量當(dāng)前所能容納的最多元素個數(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;//格式化輸出計數(shù),for循環(huán)計數(shù)用

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

cout<<"請輸入一個整數(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個字符

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

#include<iostream.h>

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

deque<int>mdeque(10,1);

//定義一個int型mdeque對象

deque<int>::iterator

iter;

//定義一個int容器指示器指針

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

cout<<*iter<<“;”;

//遍歷對象mdeque

}

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

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

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

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

例：利用雙端隊列模板類寫出求大數(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;//格式化輸出計數(shù),for循環(huán)計數(shù)用

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

cout<<"請輸入一個整數(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個字符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)計計算的時間為毫秒4、兩個雙端隊列的比較：模板類std::deque定義了一組完整的運算符，這些運算符可以比較std::deque對象，當(dāng)兩個雙端隊列有相同個數(shù)的元素時，且元素值也相同時，這兩個雙端隊列就是相等的，也可以判定一個雙端隊列小于或大于另一個雙端隊列。例如：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個雙端隊列的大小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類似于向量和雙端隊列，只不過鏈表對象提供了對元素的隨機訪問。但是std::list對象在序列中的任何位置放置元素和刪除元素都是高效的。std::list對象也能在需要的時候動態(tài)改變自身大小。構(gòu)造std::list對象必須包含頭文件<list>,構(gòu)造方式有下面幾種：std::list<type>name;//創(chuàng)建空對象std::list<type>name(size);//創(chuàng)建一個大小為size對象std::list<type>name(size,value);//創(chuàng)建一個大小為size，初值為value對象std::list<type>name(mydeque);//拷貝構(gòu)造函數(shù)std::list<type>name(first,last);//構(gòu)造一個元素在某個范圍內(nèi)的向量。該范圍用first及l(fā)ast指示器來說明。2、鏈表對象的使用：例：

#include<iostream.h>

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

list<int>mlist(10,1);

//定義一個int型mlist對象

list<int>::iterator

iter;

//定義一個int容器指示器指針

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

cout<<*iter<<“;”;

//遍歷對象mdeque

}

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

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

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

back():返回對鏈表尾部元素的引用。front():返回對鏈表起始元素的引用。size():返回鏈表的大?。ㄔ氐膫€數(shù)）。clear():刪除鏈表中的所有元素。empty():如果鏈表為空，則返回TRUE。swap(deque):交換2個鏈表的內(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;//格式化輸出計數(shù),for循環(huán)計數(shù)用

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

cout<<"請輸入一個整數(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個字符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)計計算的時間為毫秒4、兩個鏈表的比較：類模板std::list定義了一組完整的運算符，這些運算符可以比較std::list對象，當(dāng)兩個雙端隊列有相同個數(shù)的元素時，且元素值也相同時，這兩個鏈表就是相等的，也可以判定一個鏈表小于或大于另一個鏈表。例如：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個鏈表的大小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)造：

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

std::stack<type,container>name;

參數(shù)type是堆棧所操作的數(shù)據(jù)類型，container參數(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的操作：因為堆棧是一種簡單的數(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)造：

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

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

std::queue<type,container>;

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

隊列也是一種簡單的數(shù)據(jù)結(jié)構(gòu)，所以只需要一些基本的操作。主要有：empty():清空隊列。size():返回隊列的大小。front():置隊列首。back():置隊列尾。push():壓入隊列。pop():彈出隊列。下面的例子說明對列的使用。#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();//獲得隊列的大小for(i=0;i<size;i++){cout<<intqueue.front()<<“;”;//10;20;30;40;50;60;70

intqueue.pop();}}8.3

結(jié)合容器

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

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

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

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

與std::map

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

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

set<int>myset;//定義一個int型mvector對象

set<int>::iterator

iter;//定義一個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():返回指向集合中第一個元素的指示器

clear():刪除集合的所有元素。count(x):返回元素x在集合中出現(xiàn)的次數(shù)（0或1次）empty():如果集合為空，則返回TRUE。end():返回指向集合中最后一個元素的指示器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():返回集合的大?。ㄔ氐膫€數(shù)）。swap(set):交換2個集合的內(nèi)容。

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

：

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

multiset<int>myset;//定義一個int型mvector對象

multiset<int>::iterator

iter;//定義一個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():返回指向多重集合中第一個元素的指示器

clear():刪除多重集合的所有元素。count(x):返回元素x在多重集合中出現(xiàn)的次數(shù)empty():如果多重集合為空，則返回TRUE。end():返回指向多重集合中最后一個元素的指示器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():返回多重集合的大?。ㄔ氐膫€數(shù)）。swap(set):交換2個多重集合的內(nèi)容。

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

std::map對象可以使程序按照次序來存儲一組數(shù)值。每一個元素都與一個查詢關(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)造一個整數(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;//定義一個int型mvector對象

map<int,char>::iterator

iter;//定義一個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():返回指向映射中第一個元素的指示器

clear():刪除映射中的所有元素。count(x):返回元素x在映射中出現(xiàn)的次數(shù)（0或1）empty():如果映射為空，則返回TRUE。end():返回指向映射中最后一個元素的指示器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():返回映射的大?。ㄔ氐膫€數(shù)）。swap(set):交換2個映射的內(nèi)容。

max_size():返回映射當(dāng)前所能容納的最多元素個數(shù)。四、std::multimap多重映射容器std::multimap對象可以使程序按照次序來存儲一組數(shù)值。每一個元素都與一個查詢關(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)造一個整數(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定義了九個非修正序列算法。1、adjacent_find(first,last)返回指向一對鄰近相等元素中的第一個元素的指示器。函數(shù)搜索指示器first及l(fā)ast所規(guī)定的范圍。2、count(first,last,val)返回一個序列中具有某個特定值val的元素個數(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ī)定的范圍里的第一個數(shù)值等于val的元素指示器。5、for_each(first,last，func)對范圍first、last里的每一個元素執(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ù)制到另一個由指示器first2指向的元素所開始的范圍2、copy_backward(first,last,first2)把指示器first及l(fā)ast所規(guī)定的范圍中的元素復(fù)制到另一個由指示器first2指向的元素所開始的范圍。但是這個函數(shù)是從最后一個元素開始復(fù)制由后向前直到第一個元素。3、fill(first,last,val)把數(shù)值val賦值到由指示器first及l(fā)ast所規(guī)定的范圍中的所有元素。4、generate(first,last,func)對每一個元素調(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里的兩個元素。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);//定義一個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