标准模板库STL课件

第十一章标准模板库（STL）

库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，为程序员提供大量实用的库是C++的又一特色。标准模板库（StandardTemplateLibrary）是ANSI/ISOC++最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。第十一章标准模板库（STL）库（library）是一系1第十一章标准模板库（STL）11.1标准模板库简介

11.3顺序容器

11.2迭代子类

11.5容器适配器

11.7VC++中的STL

11.6泛型算法与函数对象

11.4关联容器

第十一章标准模板库（STL）11.1标准模板库简介211.1

标准模板库简介

STL提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。

容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器（heterogeneouscontainer），一组相同类型的对象，称为同类容器(homogenouscontainer)。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。

11.1标准模板库简介STL提供了一个标准化的模板化的对311.1

标准模板库简介容器分为三大类：顺序容器（sequencecontainerorsequentialcontainer）关联容器（associativecontainer）容器适配器（containeradopter）

顺序容器和关联容器称为第一类容器（first-classcontainer）。另外有四种容器称为近容器（nearcontainer）：C语言风格数组、字符串string、操作1/0标志值的bitset和进行高速数学矢量运算的valarray。

11.1标准模板库简介容器分为三大类：411.1

标准模板库简介标准库容器类说明顺序容器vector（参量）deque（双端队列）list（列表）

从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与删除，双链表关联容器set（集合）multiset（多重集合）map（映射）multimap（多重映射）

快速查找，不允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器stack（栈）queue（队列）priority_queue（优先级队列）

后进先出（LIFO）先进先出（FIFO）最高优先级元素总是第一个出列表11.1标准库容器类

11.1标准模板库简介标准库容器类说明顺序容器

关联容器

511.1

标准模板库简介

STL也使容器提供接口。许多基本操作是所有容器都适用的，而有些操作则适用于类似容器的子集。可以用新的类来扩展STL。参见表11.2。这些函数和运算符可通称为容器的接口。各容器具体接口参见附录C。使用STL容器或容器适配器，要包含定义该容器模板类头文件。参见表11.3。这些头文件的内容都在std名字空间域（namespacestd）中，程序中必须加以说明。

11.1标准模板库简介STL也使容器提供接口。许多基本611.1

标准模板库简介

在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访问方法最终要归于内存地址的获得，所以说迭代子是面向对象版本的指针。

迭代子与指针有许多相同之处，但迭代子保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如++运算符总是返回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子指向的容器元素。

迭代子用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。

11.1标准模板库简介在有关数组、链表和二叉树等线性表711.1

标准模板库简介

STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。STL提供70种左右的标准算法。算法只是间接通过迭代子操作容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（genericalgorithm）。算法分为：１．修改容器的算法，即变化序列算法（mutating-sequencealgorithm），如copy()、remove()、replace()、swap()等。２．不修改容器的算法，即非变化序列算法（non-mutating-sequencealgorithm），如count()、find()等。３．数字型算法。

11.1标准模板库简介STL最大的优点是提供能在各种容811.2迭代子类

C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。

标准库定义迭代子类型说明输入（InputIterator）

输出（OutputIterator）

正向（ForwardIterator）

双向（BidirectionalIterator）

随机访问（RandomAccessIterator）从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始。向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。表11.4迭代子类别

11.2迭代子类C++标准库中有五种预定义迭代子，911.2迭代子类

标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！inputoutputforwardbidirectionalrandomaccess图11.1迭代子层次

11.2迭代子类标准库定义迭代子的层次结构，按这个1011.2迭代子类

只有第一类容器能用迭代子遍历。表11.5给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表11.6，

容器支持的迭代子类别顺序容器vectordequelist

随机访问（randomaccess）随机访问（randomaccess）双向（bidirection）关联容器setmultisetmapmultimap

双向（bidirection）双向（bidirection）双向（bidirection）双向（bidirection）容器适配器stackqueuepriority_queue

不支持迭代子不支持迭代子不支持迭代子11.2迭代子类只有第一类容器能用迭代子遍历。表11111.2迭代子类

下面结合find()算法讨论迭代子与泛型算法的关系。find()定义如下：

template<typenameInputIterator,typenameT>InputIteratorfind(InputIteratorfirst,InputIteratorlast,countTvalue){for(;first!=last;++first)if(value==*first)returnfirst;returnlast}可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。find()算法也支持系统内置的数组类型：

11.2迭代子类下面结合find()算法讨论迭代子与1211.2迭代子类【例11.1】寻找数组元素。#include<algorithm>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; cout<<"请输入需搜索的数："<<endl; cin>>search_value; int*presult=find(&ia[0],&ia[9],search_value); cout<<"数值"<<search_value<<(presult==&ia[9]?"不存在":"存在")<<endl;}这里a[9]数组元素并不存在，但内存地址单元存在。

11.2迭代子类【例11.1】寻找数组元素。1311.2迭代子类【例11.2】寻找vector容器元素。#include<algorithm>#include<vector>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; vector<int>vec(ia,ia+9);//数据填入vector cout<<"请输入需搜索的数："<<endl; cin>>search_value; vector<int>::iteratorpresult;//定义迭代子 presult=find(vec.begin(),vec.end(),search_value); cout<<"数值"<<search_value<<(presult==vec.end()?"不存在":"存在")<<endl;}11.2迭代子类【例11.2】寻找vector容器元素1411.2迭代子类在<iterator>头文件中还定义了一些专用迭代子：反转迭代子(reverseiterator)；插入型迭代子(insertioniterator)；流迭代子(streamiterator)；流缓冲迭代子(streambufferiterator)；11.2迭代子类在<iterator>头文件中还定义了1511.2迭代子类１．反转型迭代子（reverseiterator）把一切都颠倒过来

vector<int>veco;vector<int>::reverse_iteratorr_iter;for(r_iter=veco.rbegin();//将r_iter指向到末元素 r_iter!=veco.rend();//不等于首元素的前导 r_iter++){//实际是上是递减 //循环体}如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。

11.2迭代子类１．反转型迭代子（reverseit1611.2迭代子类２．插入型迭代子（insertioniterator）：可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子：back_insert_iterator<Type>是输出迭代子，用来将产生的元素添加到类型为Type的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。front_insert_iterator<Type>是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。insert_iterator<Type,Iter>也是输出迭代子，它用来将产生的元素插入到一个由迭代子（第二个参数Iter）指定的元素的前面。

与之对应的也有三个相关的适配器函数，它们返回特定的插入迭代子：back_inserter(Type&)：它使用容器的push_back()插入操作代替赋值操作符，实参是容器自己。返回一个back_inserter迭代子。front_insertor(Type&)：使用容器的push_front()插入操作代替赋值操作符，实参也是容器本身。返回一个front_inserter迭代子。inserter（Type&,Iter）：用容器的insert()插入操作符代替赋值操作符。inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。

11.2迭代子类２．插入型迭代子（insertion1711.2迭代子类３．流迭代子有输入流迭代子（istream_iterator）和输出流迭代子（ostream_iterator）。在<iostream.h>、<fstream.h>等头文件中定义了流类库，在STL中为输入/输出流iostream提供了迭代子，它们可以与标准库容器类型和泛型算法结合起来工作。使用这两个迭代子必须包含头文件<iterator>。

输入流迭代子（istream_iterator）类支持在istream及其派生类（如ifstream）上的迭代子操作。istream_iterator声明方式为：istream_iterator<Type>迭代子标识符(istream&);//Type为已定义了输入操作的类型,实参可以是任意公有派生的istream的子类型的对象

输出流也有对应的ostream_iterator类支持，其声明方式为：ostream_iterator<Type>迭代子标识符(ostream&)//实参同样可以是公有派生子类型对象ostream_iterator<Type>迭代子标识符(ostream&,char*)//第二参数为C风格字符串

11.2迭代子类３．流迭代子有输入流迭代子（istre1811.2迭代子类下面结合copy算法和sort算法来介绍istreamiterator和ostream_iterator。【例11.3】用istreamiterator从标准输入读入一个整数集到vector中。#include<iostream>#include<iterator>#include<algorithm>#include<vector>#include<functional>usingnamespacestd;

voidmain(){istream_iterator<int>input(cin); istream_iterator<int>end_of_stream; vector<int>vec; copy(input,end_of_stream,inserter(vec,vec.begin()));//输入^Z结束流 sort(vec.begin(),vec.end(),greater<int>());//升序排列 ostream_iterator<int>output(cout,""); unique_copy(vec.begin(),vec.end(),output);}11.2迭代子类下面结合copy算法和sort算法来介1911.2迭代子类输入：4139572317191311373123294139^Z泛型算法copy()定义如下：template<typenameInputIterator,typenameInputIterator,typenameOutputInterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputInteratorx){ for(;first!=last;++x,++first)*x=*first return(x);}11.2迭代子类输入：2011.2迭代子类

end_of_stream是指示文件（流）结束位置，它使用了缺省的构造函数，输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。拷贝算法要求我们提供一对iterator来指示文件（流）内部的开始和结束位置。我们使用由istream对象初始化的istream_iterator提供开始位置，本例中为input。

本例中插入迭代子inserter作为copy的第三个参数，它是输出型的，把流插入vec。泛型算法sort()为升序排序算法，声明如下template<typenameRandomAccessInterator,typenamePr>voidsort(RandomAccessIteratorfirst,RandomAccessInteratorlast,Prp);第三参数为排序方式，greater<int>()是预定义的“大于”函数对象，排序时用它来比较数值大小。缺省时为“小于”，即升序排序。

例中用输出迭代子output来输出，泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，拷贝到output迭代子，即用空格分隔各整数的标准输出。输出为：41393731292319171311975311.2迭代子类end_of_stream是指示2111.2迭代子类４．流缓冲迭代子。这是STL后添加的一对迭代子，用来直接从一个流缓冲区（streambuffer）中插入或提取某种类型（通常为char）的元素。

11.2迭代子类４．流缓冲迭代子。这是STL后添加的一2211.3顺序容器

C++标准模板库提供三种顺序容器：vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的。

矢量（vector）类提供了具有连续内存地址的数据结构。通过下标运算符[]直接有效地访问矢量的任何元素。与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量（vector）类的优点。在这里内存分配是由分配子（allocator）完成。

矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。

11.3顺序容器

C++标准模板库提供三种顺序容器：2311.3顺序容器使用向量容器的声明如下： #include<vector>

……vector<int>vi;//定义存放整形序列的向量容器对象vi，长度为0的空vectorvector<float>vf; //存放实型序列的向量容器vector<char>vch; //存放字符序列的向量容器vector<char*>vstr; //存放字符串（字符指针）序列的向量容器

使用方法是典型的函数模板的使用方法。调用缺省的构造函数，创建长度为0的向量。矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。这些构造函数还可以显式给出分配子(allocator)对象。11.3顺序容器使用向量容器的声明如下：2411.3顺序容器

对矢量的操作包含了在顺序表中所列出的操作，而且更多。１．列表（list）是由双向链表（doublylinkedlist）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在§7.2节中定义的双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件<list>中。２．双端队列（deque）（double-endedqueue）类。双端队列允许在队列的两端进行操作。支持随机访问迭代子。也支持通过使用下标操作符“[]”进行访问。

11.3顺序容器对矢量的操作包含了在顺序表中所列出的2511.3顺序容器

当要增加双端队列的存储空间时，可以在内存块中deque两端进行分配，通常保存为这些块的指针数组。双端队列利用不连续内存空间，它的迭代子比vector的迭代子更加智能化。对双端队列分配存储块后，往往要等删除双端队列时才释放，它比重复分配（释放和再分配）更有效，但也更浪费内存。

使用双端队列，必须包含头文件<deque>。

11.3顺序容器当要增加双端队列的存储空间时，可以在2611.4关联容器

查找和排序总是对关键字进行的，函数模板和类模板中只介绍了通用类型（亦称泛型类型），并没有涉及关键字。关联容器（associativecontainer）能通过关键字（searchkey）直接访问(存储和读取元素)。四个关联容器为：集合（set），多重集合（multiset），映射（map），多重映射（multimap）。集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，映射和多重映射类提供了操作与关键字相关联的映射值（mappedvalue）的方法。多重集合关联容器用于快速存储和读取关键字。

11.4关联容器查找和排序总是对关键字进行的，函数2711.4关联容器

multiset和set通常实现为红黑二叉排序树。常用的二叉排序树一般结点有四个域：一个数据域，三个指针域（左孩子指针，右孩子指针和双亲指针）。双亲指针使直接回访成为可能，它使二叉排序树删除节点的算法变的简单。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。11.4关联容器multiset和set通常实现为2811.4关联容器【例11.4】整型多重集合关联容器类的演示。类模板声明:template<typenameKey,typenamePred=less<Key>,typenameA=allocator<Key>>classmultiset;//模板参数表中的非类型参数同样可有缺省值

#include<iostream>#include<set> //包含集合头文件#include<algorithm> //包含算法头文件usingnamespacestd;//C++标准库名字空间域typedefmultiset<int>INTMS;//特例取名INTMS，整型多重集合按升序排列

11.4关联容器【例11.4】整型多重集合关联容器类的2911.4关联容器

voidmain(){constintsize=16; inta[size]={17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2}; INTMSintMultiset(a,a+size); ostream_iterator<int>output(cout,"");cout<<"这里原来有"<<intMultiset.count(17)<<"个数值17"<<endl; intMultiset.insert(17);//插入一个重复的数17 cout<<"输入后这里有"<<intMultiset.count(17)<<"个数值17"<<endl; INTMS::const_iteratorresult; result=intMultiset.find(18); if(result==intMultiset.end())cout<<"没找到值18"<<endl;elsecout<<"找到值18"<<endl; cout<<"intMultiset容器中有"<<endl; copy(intMultiset.begin(),intMultiset.end(),output); cout<<endl;}11.4关联容器

voidmain(){const3011.4关联容器

请注意multiset容器中自动作了升序排列。如需要，可以在VC++帮助中（MSDN）由关键字multiset查找有关迭代子、成员函数的定义和用法。

多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/valuepair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件<set>。

11.4关联容器请注意multiset容器中自动作3111.5容器适配器

STL提供了三个容器适配器（containeradapter）：栈（stack），队列（queue）和优先级队。栈是标准的栈，使用时要用头文件<stack>。队也是标准的，使用时要用头文件<queue>。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明：

stack<vector<char>>sk;然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（queue）缺省用deque为基础，栈（stack）可用vector或deque为基础。优先级队列（priority_queue）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（priority_queue）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。缺省情况下priority_queue实现时用vector为基础数据结构。

11.5容器适配器STL提供了三个容器适配器（co3211.5容器适配器【例11.5】优先级队列类演示，头文件用<queue>，优先级用数表示，数值越大优先级越高。#include<iostream>#include<queue>#include<functional>usingnamespacestd;

11.5容器适配器【例11.5】优先级队列类演示，头文3311.5容器适配器voidmain(){ priority_queue<int>prioque; //实例化存放int值的优先级队列，并用deque作为基础数据结构 prioque.push(7);//压入优先级队列 prioque.push(12); prioque.push(9); prioque.push(18); cout<<"从优先级队列中弹出"<<endl; while(!prioque.empty()){ cout<<prioque.top()<<'\t';//取最高优先级数据 prioque.pop();//弹出最高优先级数据 } cout<<endl;}11.5容器适配器voidmain(){3411.6泛型算法与函数对象

算法表现为一系列的函数模板，它们完整定义在STL头文件中。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。11.6.1函数对象

11.6.2泛型算法

11.6泛型算法与函数对象算法表现为一系列的函数模3511.6.1函数对象

每个泛型算法（genericalgorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。

在C++中，为了使程序的安全性更好，采用“引用”来代替指针作为函数的参数或返回值。在C++的泛型算法中类似地采用了“函数对象”（functionobject）来代替函数指针。函数对象是一个类，它重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。和“引用”一样，“函数对象”独立使用比较少。函数对象亦称拟函数对象（function_likeobject）和函子（functor）。下面给出一个求和函数对象的定义：template<typenameT>classSum{ Tres;public: sum(Ti=0):res(i){}//构造函数,即sum(Ti=0){res=i;} voidoperator()(Tx){res+=x;}//累加 Tresult()const{returnres;}//}11.6.1函数对象每个泛型算法（generica3611.6.1函数对象

函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以缓冲当前数据和结果，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象做类型检查。下面给出采用函数对象作为“数值比较算法”的求序列中最小值的函数模板。template<typenameType,typenameComp>constType&min(constType*p,intsize,Compcomp){ intminIndex=0;//最小元素下标初值为0,即设0号元素最小 for(inti=1;i<size;i++) if(comp(p[i],p[minIndex]))minIndex=i; returnp[minIndex];}11.6.1函数对象函数对象与函数指针相比较有三个3711.6.1函数对象函数对象来源。1．标准库预定义的一组算术，关系和逻辑函数对象；2．预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展；３．自定义函数对象。预定义函数对象分为算术、关系和逻辑操作。每个对象都是一个类模板，其中操作数类型作为模板参数。使用时要包含头文件：#include<functional>11.6.1函数对象函数对象来源。3811.6.1函数对象我们以加法为例，讨论名为plus的类模板，对整数的用法实例如下：plus<int>intAdd;intival1=30,ival2=15;intsum=intAdd(ival1,ival2);//等效于:sum=ival1+inval2但是函数对象主要是作为泛型算法的实参使用，通常用来改变缺省的操作，比如在【例11.3】中有sort(vec.begin(),vec.end(),greater<int>());这就是把整数的大于关系函数对象作为实参，得降序排列。如果是字符串，则有：sort(svec.begin(),svec.end(),greater<string>());11.6.1函数对象我们以加法为例，讨论名为plu3911.6.1函数对象比较算法在内置类型int，字符串类string中定义。还可以自定义整数类Int:classInt{public: Int(intival=0):_val(ival){} intoperator_(){return-_val;}//负数符号重载 intoperator%(intval){return_val%ival;}//求余符号重载 booloperator<(intval){return_val<ival;}//小于符号重载 booloperator!(){return_val==0;}//逻辑非符号重载private: int_val;};每个类对象都可以作为有名或无名对象传给函数，同时也把所需重载的算法传过去了。

11.6.1函数对象比较算法在内置类型int，字符4011.6.1函数对象

下面给出各种函数对象及其使用方法：参数和返回值。为方便，定义以下变量（对象）vector<string>svec;stringsval1,sval2,sres;complexcval1,cval2,cres;intival1,ival2,ires;IntIval1,Ival2,Ires;doubledval1,dval2,dres;11.6.1函数对象下面给出各种函数对象及其使用方4111.6.1函数对象

为了用实例来说明使用方法，定义一个可用单参数函数对象(一元函数对象)的函数模板和一个可用双参数函数对象（二元函数对象）的函数模板：template<TypenameFuncObject,TypenameType>TypeUnaryFunc(FuncObjectfob,constType&val){returnfob(val);}template<TypenameFuncObject,TypenameType>TypeBinaryFunc(FuncObjectfob,constType&val1,constType&val2){returnfob(val1,val2);}11.6.1函数对象为了用实例来说明使用方法，定义4211.6.1函数对象算术函数对象：加法：plus<Type>minus<int>intSub;ires=intSub(ival1,ival2);dres=BinaryFunc(plus<double>(),dval1,dval2);sres=BinaryFunc(plus<string>(),sval1,sval2);减法：minus<Type>//同加法乘法：multiplies<Type>//对串类无定义,不能用串，可用于复数和浮点数等cres=BinaryFunc(multiplies<complex>(),cal1,cal2);dres=BinaryFunc(multiplies<double>(),dval1,dval2);除法：divides<Type>//同乘法求余：modulus<Type>//不能用于复数,浮点数,只能用于整数modulus<Int>ImtModulus;Ires=IntModulus<Ival1,Ival2);//自定义类型ires=BinaryFunc(modulus<int>(),ival1,ival2);11.6.1函数对象算术函数对象：4311.6.1函数对象取反：negate<Type>//同取余,但为单参数ires=UnaryFunc(negate<Int>(),Ival1);逻辑函数对象，这里Type必须支持逻辑运算，有两个参数。逻辑与：//对应&&逻辑或：//对应||逻辑非：//对应!关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二参数相比：等于：equal_to<Type>不等于：not_equal_to<Type>大于：great<Type>大于等于：great_equal<Type>小于：less<Type>小于等于：less_equal<Type>11.6.1函数对象取反：negate<Type>//4411.6.1函数对象

返回布尔值的函数对象称为谓词（predicate），默认的二进制谓词是小于比较操作符“<”，所以默认的排序方式都是升序排列，它采用小于比较形式。和容器类一样，函数对象也可以由函数适配器来特殊化或扩展一元（单参数）或二元（双参数）函数对象：1．绑定器（binder）：把二元函数对象中的一个参数固定（绑定），使之转为一元函数，C++标准库提供两种预定义的binder适配器：bind1st和bind2nd，分别绑定了第一或第二个参数。２．取反器（negator）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。C++标准库也提供了两种negator适配器：not1和not2。not1用于一元预定义函数对象；not2用于二元预定义函数对象。

11.6.1函数对象返回布尔值的函数对象称为谓词（4511.6.2泛型算法

在C++标准库中给出了70余种算法，泛型算法函数名都加有后缀，这些后缀的意思如下：_if 表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素，而find查找特定的值。_copy 表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。reverser算法颠倒范围中元素的排列顺序，而reverse_copy算法同时把结果复制到目标范围中。其它的后缀从英文意思上立即可以认出其意义，对照附录C11.6.2泛型算法在C++标准库中给出了70余种4611.6.2泛型算法

其次我们介绍泛型算法的构造与使用方法。所有泛型算法的前两个实参是一对iterator，通常称为first和last，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括first，但不包含last的左闭合区间。即：[first,last)当first==last成立，则范围为空。对iterator的类则要求在每个算法声明中指出（5个基本类别），所声明的是最低要求。

11.6.2泛型算法其次我们介绍泛型算法的构造与使4711.6.2泛型算法泛型算法分以下几类：

１．查找算法：有13种查找算法用各种策略去判断容器中是否存在一个指定值。equal_range()、lower_bound()和upper_bound()提供对半查找形式。

２．排序和通用整序算法：共有14种排序（sorting）和通用整序（ordering）算法，为容器中元素的排序提供各种处理方法。所谓整序，是按一定规律分类，如分割（partition）算法把容器分为两组，一组由满足某条件的元素组成，另一组由不满足某条件的元素组成。３．删除和代替算法：有15种删除和代替算法。

11.6.2泛型算法泛型算法分以下几类：4811.6.2泛型算法４．排列组合算法：有2种算法。排列组合是指全排列。如：三个字符{a，b，c}组成的序列有6种可能的全排列：abc，acb，bac，bca，cab，cba；并且六种全排列按以上顺序排列，认为abc最小，cba最大，因为abc是全顺序（从小到大）而cba是全逆序（从大到小）。

５．生成和改变算法：有6种，包含生成（generate），填充（fill）等等。６．关系算法：有7种关系算法，为比较两个容器提供了各种策略，包括相等（equal()），最大（max()），最小（min()）等等。

７．集合算法：4种集合（set）算法提供了对任何容器类型的通用集合操作。包括并（union），交（intersection），差（difference）和对称差（symmetricdifference）。

11.6.2泛型算法４．排列组合算法：有2种算法。排列4911.7VC++中的STL

VC++支持STL，STL放在标准C++库中（StandardC++Library），由一系列的头文件组成，名称采用标准STL中的名称。

标准C++库中与模板有关的头文件主要有：输入输出流（iostream）和标准模板库。VC++中对STL有所扩展，它另外包括以下容器：hashmap；hashmultimap； hashset； hashmultiset；采用散列算法。这样VC++共有11种一类容器。

在VC++的MFC中有微软开发的群（collections）类（微软自译为集合类，为不和set混淆，本书取群类），包括有任何类型的对象群和任何类型对象指针群：CArray； CList；CMap；CTypePtrArray；CTypePtrList；CTypePtrMap；它们也都是模板。

在VC++的活动模板库类（ATL，ActiveTemplateLibrary）中也有微软开发的群（collections）类：CAtlArrayCAtllistCAtlMap CAutoPtrArrayCAutoPtrlistCAutoPtrMap后三种为智能指针。

11.7VC++中的STLVC++支持STL，ST50第十一章标准模板库（STL）

库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，为程序员提供大量实用的库是C++的又一特色。标准模板库（StandardTemplateLibrary）是ANSI/ISOC++最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。第十一章标准模板库（STL）库（library）是一系51第十一章标准模板库（STL）11.1标准模板库简介

11.3顺序容器

11.2迭代子类

11.5容器适配器

11.7VC++中的STL

11.6泛型算法与函数对象

11.4关联容器

第十一章标准模板库（STL）11.1标准模板库简介5211.1

标准模板库简介

STL提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。

容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器（heterogeneouscontainer），一组相同类型的对象，称为同类容器(homogenouscontainer)。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。

11.1标准模板库简介STL提供了一个标准化的模板化的对5311.1

标准模板库简介容器分为三大类：顺序容器（sequencecontainerorsequentialcontainer）关联容器（associativecontainer）容器适配器（containeradopter）

顺序容器和关联容器称为第一类容器（first-classcontainer）。另外有四种容器称为近容器（nearcontainer）：C语言风格数组、字符串string、操作1/0标志值的bitset和进行高速数学矢量运算的valarray。

11.1标准模板库简介容器分为三大类：5411.1

标准模板库简介标准库容器类说明顺序容器vector（参量）deque（双端队列）list（列表）

从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与删除，双链表关联容器set（集合）multiset（多重集合）map（映射）multimap（多重映射）

快速查找，不允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器stack（栈）queue（队列）priority_queue（优先级队列）

后进先出（LIFO）先进先出（FIFO）最高优先级元素总是第一个出列表11.1标准库容器类

11.1标准模板库简介标准库容器类说明顺序容器

关联容器

5511.1

标准模板库简介

STL也使容器提供接口。许多基本操作是所有容器都适用的，而有些操作则适用于类似容器的子集。可以用新的类来扩展STL。参见表11.2。这些函数和运算符可通称为容器的接口。各容器具体接口参见附录C。使用STL容器或容器适配器，要包含定义该容器模板类头文件。参见表11.3。这些头文件的内容都在std名字空间域（namespacestd）中，程序中必须加以说明。

11.1标准模板库简介STL也使容器提供接口。许多基本5611.1

标准模板库简介

在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访问方法最终要归于内存地址的获得，所以说迭代子是面向对象版本的指针。

迭代子与指针有许多相同之处，但迭代子保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如++运算符总是返回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子指向的容器元素。

迭代子用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。

11.1标准模板库简介在有关数组、链表和二叉树等线性表5711.1

标准模板库简介

STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。STL提供70种左右的标准算法。算法只是间接通过迭代子操作容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（genericalgorithm）。算法分为：１．修改容器的算法，即变化序列算法（mutating-sequencealgorithm），如copy()、remove()、replace()、swap()等。２．不修改容器的算法，即非变化序列算法（non-mutating-sequencealgorithm），如count()、find()等。３．数字型算法。

11.1标准模板库简介STL最大的优点是提供能在各种容5811.2迭代子类

C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。

标准库定义迭代子类型说明输入（InputIterator）

输出（OutputIterator）

正向（ForwardIterator）

双向（BidirectionalIterator）

随机访问（RandomAccessIterator）从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始。向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。表11.4迭代子类别

11.2迭代子类C++标准库中有五种预定义迭代子，5911.2迭代子类

标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！inputoutputforwardbidirectionalrandomaccess图11.1迭代子层次

11.2迭代子类标准库定义迭代子的层次结构，按这个6011.2迭代子类

只有第一类容器能用迭代子遍历。表11.5给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表11.6，

容器支持的迭代子类别顺序容器vectordequelist

随机访问（randomaccess）随机访问（randomaccess）双向（bidirection）关联容器setmultisetmapmultimap

双向（bidirection）双向（bidirection）双向（bidirection）双向（bidirection）容器适配器stackqueuepriority_queue

不支持迭代子不支持迭代子不支持迭代子11.2迭代子类只有第一类容器能用迭代子遍历。表16111.2迭代子类

下面结合find()算法讨论迭代子与泛型算法的关系。find()定义如下：

template<typenameInputIterator,typenameT>InputIteratorfind(InputIteratorfirst,InputIteratorlast,countTvalue){for(;first!=last;++first)if(value==*first)returnfirst;returnlast}可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。find()算法也支持系统内置的数组类型：

11.2迭代子类下面结合find()算法讨论迭代子与6211.2迭代子类【例11.1】寻找数组元素。#include<algorithm>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; cout<<"请输入需搜索的数："<<endl; cin>>search_value; int*presult=find(&ia[0],&ia[9],search_value); cout<<"数值"<<search_value<<(presult==&ia[9]?"不存在":"存在")<<endl;}这里a[9]数组元素并不存在，但内存地址单元存在。

11.2迭代子类【例11.1】寻找数组元素。6311.2迭代子类【例11.2】寻找vector容器元素。#include<algorithm>#include<vector>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; vector<int>vec(ia,ia+9);//数据填入vector cout<<"请输入需搜索的数："<<endl; cin>>search_value; vector<int>::iteratorpresult;//定义迭代子 presult=find(vec.begin(),vec.end(),search_value); cout<<"数值"<<search_value<<(presult==vec.end()?"不存在":"存在")<<endl;}11.2迭代子类【例11.2】寻找vector容器元素6411.2迭代子类在<iterator>头文件中还定义了一些专用迭代子：反转迭代子(reverseiterator)；插入型迭代子(insertioniterator)；流迭代子(streamiterator)；流缓冲迭代子(streambufferiterator)；11.2迭代子类在<iterator>头文件中还定义了6511.2迭代子类１．反转型迭代子（reverseiterator）把一切都颠倒过来

vector<int>veco;vector<int>::reverse_iteratorr_iter;for(r_iter=veco.rbegin();//将r_iter指向到末元素 r_iter!=veco.rend();//不等于首元素的前导 r_iter++){//实际是上是递减 //循环体}如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。

11.2迭代子类１．反转型迭代子（reverseit6611.2迭代子类２．插入型迭代子（insertioniterator）：可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子：back_insert_iterator<Type>是输出迭代子，用来将产生的元素添加到类型为Type的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。front_insert_iterator<Type>是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。insert_iterator<Type,Iter>也是输出迭代子，它用来将产生的元素插入到一个由迭代子（第二个参数Iter）指定的元素的前面。

与之对应的也有三个相关的适配器函数，它们返回特定的插入迭代子：back_inserter(Type&)：它使用容器的push_back()插入操作代替赋值操作符，实参是容器自己。返回一个back_inserter迭代子。front_insertor(Type&)：使用容器的push_front()插入操作代替赋值操作符，实参也是容器本身。返回一个front_inserter迭代子。inserter（Type&,Iter）：用容器的insert()插入操作符代替赋值操作符。inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。

11.2迭代子类２．插入型迭代子（insertion6711.2迭代子类３．流迭代子有输入流迭代子（istream_iterator）和输出流迭代子（ostream_iterator）。在<iostream.h>、<fstream.h>等头文件中定义了流类库，在STL中为输入/输出流iostream提供了迭代子，它们可以与标准库容器类型和泛型算法结合起来工作。使用这两个迭代子必须包含头文件<iterator>。

输入流迭代子（istream_iterator）类支持在istream及其派生类（如ifstream）上的迭代子操作。istream_iterator声明方式为：istream_iterator<Type>迭代子标识符(istream&);//Type为已定义了输入操作的类型,实参可以是任意公有派生的istream的子类型的对象

输出流也有对应的ostream_iterator类支持，其声明方式为：ostream_iterator<Type>迭代子标识符(ostream&)//实参同样可以是公有派生子类型对象ostream_iterator<Type>迭代子标识符(ostream&,char*)//第二参数为C风格字符串

11.2迭代子类３．流迭代子有输入流迭代子（istre6811.2迭代子类下面结合copy算法和sort算法来介绍istreamiterator和ostream_iterator。【例11.3】用istreamiterator从标准输入读入一个整数集到vector中。#include<iostream>#include<iterator>#include<algorithm>#include<vector>#include<functional>usingnamespacestd;

voidmain(){istream_iterator<int>input(cin); istream_iterator<int>end_of_stream; vector<int>vec; copy(input,end_of_stream,inserter(vec,vec.begin()));//输入^Z结束流 sort(vec.begin(),vec.end(),greater<int>());//升序排列 ostream_iterator<int>output(cout,""); unique_copy(vec.begin(),vec.end(),output);}11.2迭代子类下面结合copy算法和sort算法来介6911.2迭代子类输入：4139572317191311373123294139^Z泛型算法copy()定义如下：template<typenameInputIterator,typenameInputIterator,typenameOutputInterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputInteratorx){ for(;first!=last;++x,++first)*x=*first return(x);}11.2迭代子类输入：7011.2迭代子类

end_of_stream是指示文件（流）结束位置，它使用了缺省的构造函数，输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。拷贝算法要求我们提供一对iterator来指示文件（流）内部的开始和结束位置。我们使用由istream对象初始化的istream_iterator提供开始位置，本例中为input。

本例中插入迭代子inserter作为copy的第三个参数，它是输出型的，把流插入vec。泛型算法sort()为升序排序算法，声明如下template<typenameRandomAccessInterator,typenamePr>voidsort(RandomAccessIteratorfirst,RandomAccessInteratorlast,Prp);第三参数为排序方式，greater<int>()是预定义的“大于”函数对象，排序时用它来比较数值大小。缺省时为“小于”，即升序排序。

例中用输出迭代子output来输出，泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，拷贝到output迭代子，即用空格分隔各整数的标准输出。输出为：41393731292319171311