第12章 标准模板库STL

第12章标准模板库STL标准模板库（StandardTemplateLibrary，简称STL）是ANSI/ISOC++最有特色、最实用的部分之一。标准模板库STL主要包括：•容器（Containers）•算法（Algorithms）•迭代器（Iterators）•函数对象（FunctionObjects）•适配器（Adaptors）•内存配置器（Allocators）标准模板库STL主要由6大组件组成：（1）容器（Containers）。包括各种基本数据结构的类模板。STL容器部分主要由头文件vector、list、deque、set、map、stack和queue组成。（2）算法（Algorithms）。包括各种基本算法，如比较、交换、查找、排序、遍历操作、复制、修改、移除、反转、合并等等。STL算法部分主要由头文件algorithm和numeric组成。12．1标准模板库STL概述（3）迭代器（Iterators）。迭代器是面向对象版本的指针，如同指针可以指向内存中的一个地址，迭代器可以指向容器中的一个位置。STL的每一个容器类模板中，都定义了一组对应的迭代器类，用以存取容器中的元素。这样，在STL中迭代器就将算法和容器联系起来了，通过迭代器，算法函数可以访问容器中指定位置的元素，而无需关心元素的具体类型。STL迭代器部分主要由头文件utility和iterator组成。（4）函数对象（FunctionObjects）。一种行为类似于函数的class，实现技术上是一个改写了“calloperator()”的class。STL提供15个预定义的Functionobjects。头文件functional中定义了一些类模板，用以声明函数对象。（5）适配器（Adaptors）。简单地说就是一种接口类，专门用来修改现有类的接口，提供一种新的接口；或调用现有的函数来实现所需要的功能。主要包括3种适配器ContainerAdaptors、IteratorAdaptors与FunctionAdaptors。其中迭代器适配器的定义在头文件iterator中，函数适配器的定义在头文件functional中。（6）内存配置器（Allocators）。为STL提供空间配置的系统。头文件memory中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。容器使用allocator完成对内存的操作，allocator提供内存原语以对内存进行统一的存取。STL六大组件的交互关系容器通过内存配置器取得数据存储空间，算法通过迭代器存取容器的内容，函数对象用在和算法的结合中，协助算法完成不同的策略变化，从而扩展算法的效用。适配器可以对容器和迭代器的接口进行转换、修饰或套接函数对象。例12-1一个简单的STL应用示例#includealgorithm#includefunctional#includevector#includeiostreamusingnamespacestd;intmain(){intia[]={34,18,23,89,40,15,56,14,41,24};vectorint,allocatorintvec(ia,ia+10);//将vec声明为元素为int类型的向量容器vectorint::iteratorit;//将it声明为int类型的向量容器的迭代器。intnum;sort(vec.begin(),vec.end());for(it=vec.begin();it!=vec.end();it++)cout*it;//14151823243440415689coutendl;num=count_if(vec.begin(),vec.end(),//使用算法count_if按条件统计bind2nd(less_equalint(),40));cout小于等于40的数有num个。endl;return0;}算法、函数对象和向量容器三个头文件STL算法STL函数适配器STL函数对象STL最主要的一个特点：数据结构和算法的分离。容器是像链表，向量、栈、队列之类的数据结构，并按类模板方式提供；算法是函数模板，用于操作容器中的数据。由于STL以模板为基础，所以能用于任何数据类型和结构。实际上，可以认为STL是以容器和迭代器为基础的一种泛型算法（GenericAlgorithms）库。所谓泛型（Genericity）是指能够在多种数据类型上进行操作，在泛型化程序设计思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。算法是泛型的，不与任何特定的数据结构或对象类型系在一起；容器是泛化的，它可以是数组、向量、链表、集合、映射、队列、栈、字符串等等，容器中包含的元素对象可以是任意数据类型，容器提供迭代器用来定址其所包含的元素；迭代器是泛型的指针，是一种指向其他对象的对象，迭代器能够遍历由对象所形成的序列区间（Range）。迭代器将容器与作用其上的算法分离，大多数的算法自身并不直接操作于容器上，而是操作于迭代器所形成的区间中。例如，要对指定容器中满足指定条件的元素进行指定的处理，采用泛型编程方法编写的算法为：templateclassIterator,classAct,classTestvoidprocess(Iteratorbegin,Iteratorend,Actact,Testtest)//对容器中在给定范围内（即起于begin止于end）所有满足给定条件的元素//（即test（元素）==true）进行处理（即act（元素））{for(;begin!=end;++begin)//从头至尾遍历容器内元素if(test(*begin))act(*begin);//若当前元素满足条件，则对其进行指定处理}12.2容器类容器类是容纳一组对象或对象集的类。STL中容器有顺序容器（SequenceContainerorSequentialContainer）和关联容器（AssociativeContainer）。顺序容器组织成对象的有限线性集合，所有对象都是同一类型。STL中三种基本顺序容器是：向量（vector）、线性表（list）、双向队列（deque）。关联容器提供了基于Key的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。STL有四种关联容器：集合（set）、多元集合（multiset）、映射（map）、多元映射（multimap）。当一个Key对应一个Value时，可以使用集合和映射；若对应同一Key有多个元素被存储时，可以使用多元集合和多元映射。12.2.1顺序容器1.vector向量vector是用于容纳不定长线性序列的容器，提供对序列的快速随机访问（也称直接访问）。vector的数据安排以及操作方式，与C++中的数组非常相似。区别在于：C++中的数组是固定大小的，分配给C++数组的空间数量在数组的生存期内是不会改变的。向量vector是动态结构，它的大小不固定，可以在程序运行时增加或减少。vector中的元素在内存是连续存储的，可以直接访问。包含vector类的头文件是vector。所以，如果要在程序里使用向量容器，就要在程序中包含下面语句：#includevector在定义向量类型对象时，必须指定该对象的类型。例如：vectorintintVec;将intVec声明为一个元素类型为int的向量容器对象。vectorstringstringVec;将stringVec声明为一个元素类型为string的向量容器对象。Vector提供的成员函数主要列举如书296页表12-1所示。（1）向量的定义和初始化vector类有4种构造函数：vector();默认构造函数，它构造一个空的vector，其大小为零。例如，vectorelementTypevecList;使用默认构造函数创建一个没有任何元素的空向量vecList。vecList.size()=0。vector(size_typen，constT&value=T());构造一个初始放入n个值为value的元素的vector。第1个参数为vector初始化的大小，第2个参数是vector中每个对象的初始值，默认为T()构造的对象。例如，vectorelementTypevecList(size);创建一个大小为size的向量vecList，并使用elementType类的默认构造函数初始化该向量。vectorelementTypevecList(n,elem);创建一个大小为n的向量vecList，该向量中所有的n个元素都初始化为elem。vector(constvector&x);复制构造函数，用另一个向量x来初始化此向量。例如，vectorelementTypevecList(otherVecList);创建一个向量vecList，并使用向量otherVecList中的元素初始化该向量。向量vecList与向量otherVecList的类型相同。vector(const_iteratorstart，const_iteratorend);从另一个支持const_iterator的容器中选取一部分（[start,end)区间的元素）来构造一个新的vector。例如，vectorelementTypevecList(begin,end);创建一个向量vecList，并初始化该向量[begin,end）中的元素，即从begin到end-1之间的所有元素。例12-2vector的定义并初始化方法示例#includeiostream#includevectorusingnamespacestd;intmain(){intnum[10]={5,5,5,5,5,5,5,5,5,5};inti;vectorintv1(10,5);//初始化有10个元素、其值都是5的向量v1vectorintv2(10);//初始化size为10、元素值为默认值0的向量v2vectorintv3(v1);vectorintv4(v1.begin(),v1.end());vectorintv5(&num[0],&num[10]);//指针可以作为迭代器来使用for(i=0;i10;i++)//将向量v2中的10个元素值均修改为5v2[i]=5;//五个vector对象是相等的，可以用operator==来判断。if(v1==v2)coutv1==v2endl;//v1==v2elsecoutv1!=v2endl;if(v1==v3)coutv1==v3endl;//v1==v3elsecoutv1!=v3endl;if(v1==v4)coutv1==v4endl;//v1==v4elsecoutv1!=v4endl;if(v1==v5)coutv1==v5endl;//v1==v5elsecoutv1!=v5endl;return0;}（2）访问向量信息向量容器vector有4个成员函数可以返回向量的信息，函数原型如下：size_typesize();//返回当前vector所容纳元素的数目size_typecapacity();//返回当前vector在重新进行内存分配以前所能容纳的元素数量size_typemax_size();//返回当前vector所能容纳元素数量的最大值（包括可重新分配内存）boolempty();//如果当前vector没有容纳任何元素，则empty()函数返回true，否则返回false例12-3访问向量信息的程序示例#includeiostream#includevectorusingnamespacestd;int