标准模板库分析

标准模板库vectorbegin()end()sort()containersalgorithmsiterators(STL)classlibrariesfunctionlibrariesclass

templatesclassesfunction

templatesdatatypesuser-defined

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

functionsspecificfunctionsinlineCodeFig1TheEvolutionofReusability/Genericity主要内容标准模板库（STL）容器顺序容器：vector,

list,

deque关联容器：set，map迭代器iteratorconst_iterator算法排序算法：sort()等查找对象算法：find()

,

count()等等STL简介STL（StandardTemplateLibrary），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++StandardLibrary）中，是ANSI/ISOC++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。C++标准库STL的三个关键组件一个STL容器是对象的集合，STL容器包括vector、deque、list、set、map、stack和queue等。一个STL容器是一个数据结构。STL算法是对容器进行处理的函数，例如copy、sort、search、merge等。一个STL算法是处理数据结构的函数。STL迭代器是访问容器中对象的一种机制，一次访问一个对象。在任何情况下，STL算法都用迭代器来处理STL容器。迭代器容器算法容器概览顺序容器

sequencecontainersvector：

从后面快速的插入与删除，直接访问任何元素deque

：从前面或后面快速的插入与删除，直接访问任何元素list：双链表，从任何地方快速插入与删除关联容器

associative

containersset：快速查找，不允许重复值multiset：

快速查找，允许重复值map：一对一映射，基于关键字快速查找，不允许重复值multimap

：一对多映射，基于关键字快速查找，允许重复值容器适配器

containeradaptersstack：

后进先出queue：先进先出

priority_queue

：最高优先级元素总是第一个出列标准库容器的头文件这些头文件的内容都在std名字空间域中，程序中必须加以说明。

头文件说明<deque><list><map><set><queue><stack><vector>两端队deque的头文件表list的头文件映射map和多重映射multimap的头文件集合set和多重集合multimap的头文件队queue和优先级队列priority_queue的头文件栈stack的头文件向量vector的头文件容器内定义的类型别名所有容器内部都提供了下列类型别名：

size_type

无符号类型，足以存储此容器类型的最大可能容器长度

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

value_type

元素类型

容器小结——初始化C<T>c；创建一个名为c的空容器Cc(c2);创建c2的副本cCc(b,e);创建c，其元素是迭代器b和e标示范围内元素的副本Cc(n,t);用n个值为t的元素创建容器c，只适用于顺序容器Cc(n);创建有n个值初始化元素的容器c，只适用于顺序容器容器元素类型必须满足以下两个约束：元素类型必须支持赋值运算；元素类型的对象必须可以复制；vector顺序容器vector类提供了具有连续内存地址的数据结构。通过下标运算符[]直接有效地访问vector的任何元素。与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是vector类的优点。在这里内存分配是由分配子（allocator）完成。

vector可以用来实现堆栈等其他更复杂的结构。vector支持随机访问迭代器所有的STL算法都可以用于vector。vector的迭代器通常实现为一个指向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的数据成员#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）概览迭代器是面向对象版本的指针。迭代器保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代器。迭代器用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代器来对这些模板实例化。迭代器可以包括指针，但又不仅是一个指针。迭代器是一种检查容器内元素并遍历元素的数据类型每种标准容器都定义了迭代器类型现代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中的元素个数，类型为c::size_typec.max_size()返回容器c可容纳的最多元素个数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容器。如果需要读取输入时在容器中间位置插入元素，然后要求随机访问元素。可以在输入时读入到一个list容器，然后对其排序，再复制到一个vector容器。提示：通常来说，除非找到选择使用其他容器的更好理由，否则vector容器都是最佳选择容器适配器适配器(adaptor)是标准库中通用的概念容器适配器：让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。举例：stack适配器可使任何一种顺序容器以栈的方式工作三种顺序容器适配器：queue,

priority_queue

,

stack使用适配器时，包含相关头文件#include<stack>

,

#include<queue>容器适配器的基础容器类型stack栈可以建立在vector,list或deque容器上，默认是deque容器。queue适配器要求关联的容器提供push_front运算，不能建立在vector容器上，默认是基于deque容器实现priority_queue要求提供随机访问功能，可建立在vector和deque容器上，默认基于vector容器实现适配器的初始化stack<int>

stk;

//空对象stack<int>

stk2(deq);

//用参数容器的副本初始化栈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!关联容器pair类型简单标准库类型，在utility头文件中定义关联容器：通过键key存储和读取元素map类型适合存储每个键所关联的值例如：字典，单词本身是键，它的解释说明是值set类型：存储不同值的集合例如：做文本处理时，用set保存要忽略的单词pair类型提供的操作pair<T1,T2>

p1

创建一个空的pair对象，两个元素分别是T1和T2类型，采用初始化值pair<T1,T2>

p1(v1,v2)

其中first成员初始化为v1,second成员初始化为v2make_pair(v1,v2)

以v1和v2值创建一个新的pair对象p1<p2两个pair对象之间的小于运算，遵循字典次序p1==p2若两个pair对象的first和second成员依次相等，则两对象相等p.first

返回p中名为first的（公有）数据成员p.second返回p中名为second的（公有）数据成员关联容器关联容器操作关联容器共享大部分顺序容器的操作但不提供front,push_front,pop_front,back,push_back,pop_back操作关联容器特点

关联容器根据键排列元素

即在迭代遍历关联容器时，确保按键的顺序访问元素，而与元素在容器中存放位置完全无关。map类型——键值对集合map定义的类型map<K,V>::key_type用作索引的键的类型map<K,V>::mapped_type键所关联的值的类型map<K,V>::

value_type一个pair类型，它的first元素具有const

map<K,V>::key_type类型，而second元素则为map<K,V>::mapped_type类型程序举例：“单词转换”map对象问题：给出一个string对象，把它转换为另一个string对象程序输入：两个文件，第一个文件是单词转换集合，第二个文件提供了需要转换的文本程序举例如果单词转换内容为：‘am

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程序产生的输出结果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函数逐行读入，对每行内容用istringstream将每行中的单词提取出来步骤3:对提取出来的单词判断是否在转换的map对象中出现。如果在，则从该map对象中取出对应的值替代此单词stringline;while(getline(input,line)){

istringstreamstream(line);

//readthelineawordatatimestringword;

bool

firstword=true;//controls

whetheraspaceisprinted

while(stream>>word){//theactual

mapwork,