第9章 标准模板库STL

1第二部分面向对象的程序设计第3章类和对象(一)第4章类和对象(二)第5章继承和派生第6章虚函数与多态性第7章运算符重载第8章模板第9章标准模板库STL第10章C++语言的输入和输出2第9章标准模板库STL本章重点：STL概述容器迭代器算法与函数对象3在C++中，库(library)表示的是一系列程序组件的集合，它的主要用途就是在不同的程序中被重复使用。STL标准模板库（StandardTemplateLibrary）其主要思想是结合C++的模板机制，设计出一系列的针对数据结构中具体问题的类模板和函数模板，并不针对具体的数据类型，形成了具有优秀、高效编码的模板库，成为了标准C++体系的一部分。49.1STL概述STL（StandardTemplateLibrary，标准模板库）是一个C++的通用库，是美国加州的惠普实验室开发的一系列软件的统称，开发者主要是AlexanderStepanov，MengLee，DavidRMusser三位。STL中的代码主要采用模板类和函数模板的方式，极大地提高了编程效率。STL倡导泛型编程，即以通用的方式来写数据结构和算法。5STL主要由:容器(Containers)迭代器(Iterators)算法(Algorithms)函数对象(Functionobjects)内存分配器(Allocators)适配器(Adapter)等六大部分组成，每一部分又有多个组件构成。6容器用来表示各种数据结构对象，如vector、list、deque、set、map等，主要用于存放数据，每个容器表现为类模板；迭代器用来把容器和算法联系起来，是一种智能指针，通过运算符重载，一般化了C++中指针的概念；算法包括对数据集合的查找、排序、复制等操作，都以函数模版的形式出现；函数对象，就是一个行为类似于函数的对象，重载了运算符函数operator()；内存分配器，主要用来为各种容器配置并管理内存空间，以类模板形式出现；适配器，用来修饰接口，分为容器配接器、迭代器配接器和函数对象配接器等。7为了更好的理解和使用STL，还需要了解它以下几个概念:namespace命名空间命名空间也叫名字空间，它的本质就是在类的作用域之外定义更大的作用范畴，换句话说就是为类定义容器。其作用是对类进行层次分类，可以避免了不同模块内标识符同名冲突问题。8可以用如下方式定义命名空间：namespaceMath//Math命名空间{classMatrix//矩阵类{关于Matrix类的定义};classComplex//复数类{关于Complex类的定义};constdoublePI=3.1415926//常数PIdoubleSin(doublerad);//正弦函数声明其他的定义...};9如下语句用完整类名定义了一个对象并调用了空间内的函数Math::Complexc1;//定义对象c1f1=Math::Sin(Math::PI*0.1);//调用函数Sin求值为了避免每次定义都使用命名空间作前缀，还可以用using关键字来指定命名空间，如经过如下声明后：usingMath::Matrix;10在当前的程序范围内就可以直接引用标识符Matrix,来定义一个新的对象：Matrixmat;或者可以做如下声明：usingnamespaceMath;这样，Math命名空间内的所有标识符就可以在当前程序范围内直接使用了，不需要加任何前缀，但是要注意的是，不要和同作用域内的标识符发生同名冲突。11(2)C++标准头文件#include指令包含一个头文件usingnamespacestd；需要说明的是，在新的C++的标准头库中，头文件不再使用扩展名，在这些头文件里声明了所有的标识符，例如”iostream”头文件其包含的形式如下：#includeiostream12我们可以打开这iosteam这个头文件，可以看到如下内容：......_STD_BEGIN//宏定义等价于“namespacestd{“//OBJECTSstaticios_base::Init_Ios_init;extern_CRTIMPistreamcin;//输入对象extern_CRTIMPostreamcout;//输出对象extern_CRTIMPostreamcerr,clog;//错误和记录对象......_STD_END//宏定义等价于“}”而关于_STD_BEGIN和_STD_END两个宏的具体定义如下：#define_STD_BEGINnamespacestd{#define_STD_END}13在C++标准头文件主要分为三类：C标准头文件：原来的stdlib.h、math.h、string.h等。在用于C++时，要把扩展名去掉，同时还在名称前加字母“c”，如cstdlib、cmath、cstring等，这其实就是对于原来头文件的一个兼容形式。C++标准头文件：iostream、iomanip、limits、stdexecept等，包含了一些C++常用的类和对象的定义与声明。14STL常用的组件头文件：包括容器、迭代器、算法、函数对象等。其中:顺序容器类的头文件有vector、list、deque关联容器有set、map适配器容器有stack、queue、string等。算法位于algorithm中通用的数值方法在numeric中迭代器类在iterator中函数对象在functional中。159.2容器9.2.1容器分类与共同操作STL容器可用来存放、容纳各种不同类型的数据，它们都是类模板。实例化为类型T的容器类能够存放T类型的对象。STL提供七种容器：向量vector、链表list、双端队列deque、集合set、多重集合multiset、映射map、多重映射multimap。16这些容器分为两种类型：顺序容器（SequenceContainers）：包括vector，list，deque。关联容器（AssociativeContainers）：包括set、multiset、map、multimap。17顺序容器（SequenceContainers）：顺序容器以线性方式存储序列元素，并且这些序列元素有头有尾，依次存放。序列的“头”是序列的首元素。序列的“尾”是序列的末元素。对于这些元素的访问，总可以从首元素出发，逐个访问每个中间元素，然后到达最后一个元素。向量vector、链表list、双端队列deque都是典型的顺序容器。18顺序容器（SequenceContainers）：顺序容器中元素可采用两种方式进行访问：顺序访问:顺序访问则必须从首元素开始逐渐递增到目标元素，向量vector和双端队列deque也可以使用该种方式，而链表list只能使用该方式访问内部的元素。随机访问:随机访问类似于对传统数组的访问，如对于向量vector和双端队列deque，给定下标就可以直接找到对应的元素的引用。关联容器中的元素没有严格线性关系，所以其中的元素没有首元素和末元素的区别。对于关联容器中的元素一般采用索引方式进行访问。19关联容器（AssociativeContainers）：关联容器中的元素没有严格线性关系，所以其中的元素没有首元素和末元素的区别。对于关联容器中的元素一般采用索引方式进行访问。201容器对象的构造和析构所有容器类都提供了不带参数的默认构造函数，可用这种方式构造出空的容器对象，然后向容器内插入元素。所有容器类还提供了构造函数利用一个给定的数据区间来构造容器。所有容器类还提供了一个拷贝构造函数能以现有容器对象为样本复制生成内容相同的另一个容器。所有容器都提供了一个析构函数来释放容器元素所占用的存储空间。如表9.1所示。21表9.1容器对象的构造和析构语句说明ContainersTc;定义指定类型T的容器对象，利用默认构造函数ContainersTc(begin,begin+N);利用一个给定的数据区间[beg，beg+N)来构造容器对象，注意：包含beg位置的元素，不包含beg+N位置的元素ContainersTc(c1);拷贝构造对象~Containers()析构函数释放元素所占内存c=c1;对象复制c.swap(c1);实现两个容器对象内容的互换其中Containers是容器类，T为指定的数据类型，c、c1为容器对象222容器元素的访问所有的容器都要配合迭代器才能访问内部的元素。迭代器：理解为智能指针。可以用迭代器对象指向容器内的元素。可用迭代器对象前面加“*”运算符的方式访问所指向的元素。还可以用“++”和“--”运算符使智能指针指向相邻的元素。23所有容器都提供基于迭代器的访问函数表9.2容器元素的访问迭代器有关的成员函数说明CT::iteratorit定义指定类型容器的迭代器对象c.begin()返回指向容器对象中首元素的迭代器c.end()返回指向容器对象中末元素后续位置的迭代器c.rbegin()返回指向容器对象中逆向首元素的迭代器c.rend()返回指向容器对象中逆向末元素的迭代器其中C是容器类，T为指定的数据类型，c为一个容器对象243容器的维护与查询所有容器都可以进行:插入元素删除元素清空容器查询容器的容量和大小判断是否为空等25表9.3容器的维护与查询函数说明c.insert(pos,e)在指定位置插入数据元素ec.erase(pos)删除指定位置的元素c.erase(begin,end)删除区间[begin，end)中的元素c.clear()删除容器内所有的元素c.max_size()返回容器对象的容量c.size()返回容器对象当前所包含元素的数量c.empty()返回容器是否为空c为容器对象，pos、begin、end均为迭代器26【例9.1】容器的构造与操作。/*09_01.cpp*/#includeiostream#includevector#includelistusingnamespacestd;intmain(){inta[5]={3,8,2,7,1};vectorintv1,v2(a,a+5);//定义v1,v2两个向量对象vectorint::iteratoritv;//定义向量迭代器v1.insert(v1.begin(),4);//把4插入向量v1首端v1.insert(v1.begin(),6);//把6插入向量v1末端元素4之前v2.insert(v2.begin(),9);//把9插入向量v2首端v2.insert(v2.end(),5);//把5插入向量v2末端listintl1(v2.begin(),v2.end());//以向量v2的内容为数据范围listint::iteratoritl;//定义链表迭代器v2.erase(v2.begin());//删掉v2的首元素27coutv1:;for(itv=v1.begin();itv!=v1.end();itv++)cout*itv“”;//输出v1的所有元素coutendlv2:;for(itv=v2.begin();itv!=v2.end();itv++)cout*itv;//输出v2的所有元素coutendll1:;for(itl=l1.begin();itl!=l1.end();itl++)cout*itl;//输出l1的所有元素return0;}28v1:64v2:382715l1:9382715程序的运行结果为：299.2.2顺序容器STL的顺序容器主要包括:向量vector链表list双向队列deque字符串类string等。对于顺序容器，允许进行首、尾元素的访问，也可以在首、末插入和删除元素，其具体函数如表9.4所示。3