標準模板庫分析

標準模板庫vectorbegin()end()sort()containersalgorithmsiterators(STL)classlibrariesfunctionlibrariesclass

templatesclassesfunction

templatesdatatypesuser-defined

(enums,structs,etc.)Data+Algorithms=Programsoverloaded

functionsspecificfunctionsinlineCodeFig1TheEvolutionofReusability/Genericity主要內容標準模板庫（STL）容器順序容器：vector,

list,

deque關聯(lián)容器：set，map迭代器iteratorconst_iterator算法排序算法：sort()等查找對象算法：find()

,

count()等等STL簡介STL（StandardTemplateLibrary），即標準模板庫，是一個具有工業(yè)強度的，高效的C++程序庫。它被容納于C++標準程序庫（C++StandardLibrary）中，是ANSI/ISOC++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域里所常用的基本數(shù)據(jù)結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現(xiàn)了軟件的可復用性。C++標準庫STL的三個關鍵組件一個STL容器是對象的集合，STL容器包括vector、deque、list、set、map、stack和queue等。一個STL容器是一個數(shù)據(jù)結構。STL算法是對容器進行處理的函數(shù)，例如copy、sort、search、merge等。一個STL算法是處理數(shù)據(jù)結構的函數(shù)。STL迭代器是訪問容器中對象的一種機制，一次訪問一個對象。在任何情況下，STL算法都用迭代器來處理STL容器。迭代器容器算法容器概覽順序容器

sequencecontainersvector：

從后面快速的插入與刪除，直接訪問任何元素deque

：從前面或后面快速的插入與刪除，直接訪問任何元素list：雙鏈表，從任何地方快速插入與刪除關聯(lián)容器

associative

containersset：快速查找，不允許重復值multiset：

快速查找，允許重復值map：一對一映射，基于關鍵字快速查找，不允許重復值multimap

：一對多映射，基于關鍵字快速查找，允許重復值容器適配器

containeradaptersstack：

后進先出queue：先進先出

priority_queue

：最高優(yōu)先級元素總是第一個出列標準庫容器的頭文件這些頭文件的內容都在std名字空間域中，程序中必須加以說明。

頭文件說明<deque><list><map><set><queue><stack><vector>兩端隊deque的頭文件表list的頭文件映射map和多重映射multimap的頭文件集合set和多重集合multimap的頭文件隊queue和優(yōu)先級隊列priority_queue的頭文件棧stack的頭文件向量vector的頭文件容器內定義的類型別名所有容器內部都提供了下列類型別名：

size_type

無符號類型，足以存儲此容器類型的最大可能容器長度

iterator此容器類型的迭代器類型

value_type

元素類型

容器小結——初始化C<T>c；創(chuàng)建一個名為c的空容器Cc(c2);創(chuàng)建c2的副本cCc(b,e);創(chuàng)建c，其元素是迭代器b和e標示范圍內元素的副本Cc(n,t);用n個值為t的元素創(chuàng)建容器c，只適用于順序容器Cc(n);創(chuàng)建有n個值初始化元素的容器c，只適用于順序容器容器元素類型必須滿足以下兩個約束：元素類型必須支持賦值運算；元素類型的對象必須可以復制；vector順序容器vector類提供了具有連續(xù)內存地址的數(shù)據(jù)結構。通過下標運算符[]直接有效地訪問vector的任何元素。與數(shù)組不同，vector的內存用盡時，vector自動分配更大的連續(xù)內存區(qū)，將原先的元素復制到新的內存區(qū)，并釋放舊的內存區(qū)。這是vector類的優(yōu)點。在這里內存分配是由分配子（allocator）完成。

vector可以用來實現(xiàn)堆棧等其他更復雜的結構。vector支持隨機訪問迭代器所有的STL算法都可以用于vector。vector的迭代器通常實現(xiàn)為一個指向vector元素的指針。OperationsConstructors:

vector<T>v,//emptyvector

v1(100),//contains100elementsoftypeT

v2(100,val),//contains100copiesofval

v3(fptr,lptr);//containscopiesofelementsin

//memorylocationsfptruptolptr

Copyconstructor Destructor

v.size() Numberofelementsvactuallycontains

v.empty() Checkifvisemptyv.push_back(val) Addvalatend

v[i],v.at(i)

i-thvaluewithout/withrangechecking

(atthrowsout-of-rangeexception)Relationaloperators LexicographicorderisusedAssignment(=) e.g.,v1=v2;

v.swap(v1) Swapcontentswiththoseofvectorv1

練習：使用vector作為stack的數(shù)據(jù)成員#include<vector>

usingnamespacestd;

template<typenameStackElement>

classStack

{

/*****FunctionMembers*****/

public:

Stack(){};//letvector'sconstructordothework

boolempty()const;

voidpush(constStackElement&value);

voiddisplay(ostream&out)const;

StackElementtop()const;

voidpop();/*****DataMembers*****/

private:vector<StackElement>myVector;//vectortostoreelements//don'tneedmyTop--backofvectoristopofstack

};//endofclassdeclaration迭代器/迭代子（iterator）概覽迭代器是面向對象版本的指針。迭代器保存所操作的特定容器需要的狀態(tài)信息，從而實現(xiàn)與每種容器類型相適應的迭代器。迭代器用來將STL的各部分結合在一起。從本質上說，STL提供的所有算法都是模板，我們可以通過使用自己指定的迭代器來對這些模板實例化。迭代器可以包括指針，但又不僅是一個指針。迭代器是一種檢查容器內元素并遍歷元素的數(shù)據(jù)類型每種標準容器都定義了迭代器類型現(xiàn)代C++程序更傾向于使用迭代器而不是下標訪問容器元素迭代器操作迭代器操作定義vector<int>::iterator

iter;begin和end操作vector<int>::iterator

iter=ivec.begin();迭代器指向第一個元素end操作返回的迭代器指向末端元素的下一個vector迭代器的自增和解引用運算：iter++,*iter比較：==,

!=迭代器舉例要求：using

iteraotrs

to

seset

all

the

elements

in

ivec

to

0for

(vector<int>::iterator

iter

=

ivec.begin();

iter

!=

ivec.end();

++iter)

*iter

=

0;const_iterator上面的代碼vector<int>::iterator改變vector中的元素值每種容器類型還定義了一種名為const_iterator的類型，該類型只能用于讀取容器內元素，不能改變其值。舉例：for

(vector<string>::const_iterator

iter

=

text.begin();

iter

!=

text.end();

++iter)

cout<<*iter

<<endl;練習：Read

words

from

the

standard

input

and

store

as

elements

in

a

vector

#include<iostream>#include<vector>#include<string>using

namespace

std;intmain(int

argc,const

char*argv[]){

vector<string>svec;

stringdata;

vector<string>::iteratorit;

while(cin>>data){

svec.push_back(data);}

for(it=svec.begin();it!=svec.end();it++){

cout<<*it<<endl;}

return

0;}順序容器小結——begin和endc.begin()返回一個迭代器，指向容器c的第一個元素c.end()返回一個迭代器，指向容器c的最后一個元素的下一位置c.rbegin()返回一個逆序迭代器，指向容器c的最后一個元素c.rend()返回一個逆序迭代器，指向容器c的第一個元素前面的位置順序容器小結——添加元素c.push_back(t)在容器c的尾部添加值為t的元素，返回void類型c.push_front(t)在容器c的前端添加值為t的元素，返回void類型只適用于list和deque容器類型c.insert(p,t)在迭代器p所指的元素前插入值為t的新元素，返回指向新添加元素的迭代器c.insert(p,n,t)在迭代器p所指向的元素前面插入n個值為t的新元素，返回void類型c.insert(p,b,e)在迭代器p所指向的元素前面插入由迭代器b和e標記的范圍內的元素，返回void順序容器小結——容器大小的操作c.size()返回容器c中的元素個數(shù)，類型為c::size_typec.max_size()返回容器c可容納的最多元素個數(shù)c.empty()返回容器大小是否為0的布爾值c.resize(n)調整容器c的大小，使其能容納n個元素c.resize(n,t)調整容器c的大小，使其能容納n個元素，所有新添加元素值為t順序容器小結——訪問元素c.back()返回容器c最后一個元素的引用c.front()返回容器c第一個元素的引用c[n]返回下標為n的元素引用只適用于vector和deque容器c.at(n)返回下標為n的元素的引用只適用于vector和deque容器順序容器小結——刪除元素c.erase(p)刪除迭代器p所指向的元素，返回一個迭代器，指向被刪除元素后面的元素。c.erase(b,e)刪除迭代器b和e所標記的范圍內所有元素c.clear()刪除容器c內的所有元素，返回voidc.pop_back()刪除容器c的最后一個元素，返回void。c.pop_front()刪除容器c的第一個元素，返回void。只適用于list和deque容器順序容器小結——賦值與swapc1=c2刪除容器c1的所有元素，然后將c2的元素復制給c1。c1和c2的類型（包括容器類型和元素類型）必須相同。c1.swap(c2)交換容器c1和c2內容。c.assign(b,e)重新設置c的元素：將迭代器b和e標記范圍內的所有元素復制到c中。b和e不是指向c中元素的迭代器c.assign(n,t)將容器c重新設置為存儲n個值為t的元素容器的選擇選擇容器類型的法則：如果程序要求隨機訪問元素，使用vector或deque容器如果程序必須在容器中間位置插入刪除元素，采用list容器如果程序不在容器中間位置，而是在容器首部或尾部插入或刪除元素，使用deque容器。如果需要讀取輸入時在容器中間位置插入元素，然后要求隨機訪問元素?？梢栽谳斎霑r讀入到一個list容器，然后對其排序，再復制到一個vector容器。提示：通常來說，除非找到選擇使用其他容器的更好理由，否則vector容器都是最佳選擇容器適配器適配器(adaptor)是標準庫中通用的概念容器適配器：讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式實現(xiàn)。舉例：stack適配器可使任何一種順序容器以棧的方式工作三種順序容器適配器：queue,

priority_queue

,

stack使用適配器時，包含相關頭文件#include<stack>

,

#include<queue>容器適配器的基礎容器類型stack?？梢越⒃趘ector,list或deque容器上，默認是deque容器。queue適配器要求關聯(lián)的容器提供push_front運算，不能建立在vector容器上，默認是基于deque容器實現(xiàn)priority_queue要求提供隨機訪問功能，可建立在vector和deque容器上，默認基于vector容器實現(xiàn)適配器的初始化stack<int>

stk;

//空對象stack<int>

stk2(deq);

//用參數(shù)容器的副本初始化棧stack<string,vector<string>

>

str_stk;

//

empty

stack

implemented

on

top

of

vectorstack<string,

vector<string>

>

str_stk2(svec);

//str_stk2

is

implemented

on

top

of

vector

and

holds

a

copy

of

svec棧適配器舉例——棧支持的操作intmain(){

const

stack<int>::size_type

stk_size=10;

stack<int>intStack;

intix=0;

while(intStack.size()!=stk_size)

intStack.push(ix++);

int

error_cnt=0;

while(intStack.empty()==false){

intvalue=intStack.top();

if(value!=--ix){

cerr<<"oops!expected"<<ix<<"received"<<value<<endl;++error_cnt;}else

cout<<value<<"";

intStack.pop();}

cout<<"Ourprogramranwith"<<error_cnt<<"errors!"<<endl;}9876543210Ourprogramranwith0errors!關聯(lián)容器pair類型簡單標準庫類型，在utility頭文件中定義關聯(lián)容器：通過鍵key存儲和讀取元素map類型適合存儲每個鍵所關聯(lián)的值例如：字典，單詞本身是鍵，它的解釋說明是值set類型：存儲不同值的集合例如：做文本處理時，用set保存要忽略的單詞pair類型提供的操作pair<T1,T2>

p1

創(chuàng)建一個空的pair對象，兩個元素分別是T1和T2類型，采用初始化值pair<T1,T2>

p1(v1,v2)

其中first成員初始化為v1,second成員初始化為v2make_pair(v1,v2)

以v1和v2值創(chuàng)建一個新的pair對象p1<p2兩個pair對象之間的小于運算，遵循字典次序p1==p2若兩個pair對象的first和second成員依次相等，則兩對象相等p.first

返回p中名為first的（公有）數(shù)據(jù)成員p.second返回p中名為second的（公有）數(shù)據(jù)成員關聯(lián)容器關聯(lián)容器操作關聯(lián)容器共享大部分順序容器的操作但不提供front,push_front,pop_front,back,push_back,pop_back操作關聯(lián)容器特點

關聯(lián)容器根據(jù)鍵排列元素

即在迭代遍歷關聯(lián)容器時，確保按鍵的順序訪問元素，而與元素在容器中存放位置完全無關。map類型——鍵值對集合map定義的類型map<K,V>::key_type用作索引的鍵的類型map<K,V>::mapped_type鍵所關聯(lián)的值的類型map<K,V>::

value_type一個pair類型，它的first元素具有const

map<K,V>::key_type類型，而second元素則為map<K,V>::mapped_type類型程序舉例：“單詞轉換”map對象問題：給出一個string對象，把它轉換為另一個string對象程序輸入：兩個文件，第一個文件是單詞轉換集合，第二個文件提供了需要轉換的文本程序舉例如果單詞轉換內容為：‘a(chǎn)m

them

cuz

because

gratz

grateful

i I

nah no

pos supposed

sez

said

tanx thanks

wuz

was要轉換的文本是nah

i

sez

tanx

cuz

i

wuz

pos

to

not

cuz

i

wuz

gratz程序產(chǎn)生的輸出結果no

I

said

thanks

because

I

was

supposed

to

not

because

I

was

grateful 單詞轉換程序解決方案：將單詞轉換文件的內容存儲在一個map容器中，將被替換的單詞作為鍵，而用作替換的單詞作為相應的值。接著讀取輸入，查找輸入的每個單詞是否對應有轉換。若有，則轉換，輸出轉換后的值，否則，輸出原詞。步驟1:讀入文件，單詞轉換文件及需要轉換的文件intmain(int

argc,char**argv){map<string,string>trans_map;//maptoholdthewordtransformationpairsstringkey,value;if(argc!=3){cerr<<"wrongnumberofarguments”;exit(0);}

ifstream

map_file;if(!open_file(map_file,argv[1])){cerr<<"notransformationfile!”;exit(-1);}//readthetransformationmapandbuildthemapwhile(map_file>>key>>value)

trans_map.insert(make_pair(key,value));

ifstreaminput;if(!open_file(input,argv[2])){cerr<<"noinputfile!”;exit(-1);}步驟2:對要轉換的文件，用getline函數(shù)逐行讀入，對每行內容用istringstream將每行中的單詞提取出來步驟3:對提取出來的單詞判斷是否在轉換的map對象中出現(xiàn)。如果在，則從該map對象中取出對應的值替代此單詞stringline;while(getline(input,line)){

istringstreamstream(line);

//readthelineawordatatimestringword;

bool

firstword=true;//controls

whetheraspaceisprinted

while(stream>>word){//theactual

mapwork,