第十一章 标准模板库（STL） 库（library）是一系列程序组件的集合，它们可 以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，模板（template）为通用性带来了不可估量的前景，我们可以在使用模板时才对某些类型作选择。模板是标准C++实现代码复用的有力工具，特别是在有关数据结构的算法方面。为程序员提供大量实用的库是C++的又一特色。 标准模板库（Standard Template Library）是ANSI/ISO C++最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。泛型算法（generic algorithm）和函数对象（function object）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖，这样就可以编出更具通用性的算法。

第十一章 标准模板库（STL） 11.1 标准模板库简介 11.5 容器适配器 11.2 迭代子类 11.6 泛型算法与函数对象 11.5 容器适配器 11.2 迭代子类 11.6 泛型算法与函数对象 11.3 顺序容器 11.7 VC++中的STL 11.4 关联容器

11.1 标准模板库简介 STL提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。 容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。 迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。 泛型算法不依赖于具体的容器，通用的算法更易于扩充。泛型算法中采用函数对象（function object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。

11.1 标准模板库简介 容器分为三大类： 标准库容器类 说明 顺序容器 vector（参量） deque（双端队列） list（列表） 从后面快速插入与删除，直接访问任何元素 从前面或后面快速插入与删除，直接访问任何元素 从任何地方快速插入与删除，双链表 关联容器 set（集合） multiset（多重集合） map（映射） multimap（多重映射） 快速查找，不允许重复值 快速查找，允许重复值 一对一映射，基于关键字快速查找，不允许重复值 一对多映射，基于关键字快速查找，允许重复值 容器适配器 stack（栈） queue（队列） priority_queue （优先级队列） 后进先出（LIFO） 先进先出（FIFO） 最高优先级元素总是第一个出列

11.1 标准模板库简介 顺序容器和关联容器称为第一类容器（first-class container）。另外有四种容器称为近容器（near container）：C语言风格数组、字符串string、操作1/0标志值的bitset和进行高速数学矢量运算的valarray。 它们虽然提供与第一类容器类似的功能，但没有全部功能。 STL也使容器提供类似的接口。许多基本操作是所有容器都适用的，而有些操作则适用于类似容器的子集。这样就可以用新的类来扩展STL。这些函数和运算符可通称为容器的接口。 表11.2 所有标准库容器共有的函数 提供容器默认初始化的构造函数。通常每个容器都有几个不同的构造函数，提供容器不同的初始化方法 将容器初始化为现有同类容器副本的构造函数 撤消容器时，进行内存处理 判容器是否为空，空返回true,不空返回false 返回容器中最多允许的元素量 返回容器当前元素量 默认构造函数 拷贝构造函数 析构函数 empty() max_size() size() 说明 标准库容器共有的函数

11.1 标准模板库简介 将一个容器赋值拷贝给另一个同类容器 交换两个容器的元素 如果前面的容器小于后面的容器，则返回true，否则返回false，不适用于priority_queue 如果前面的容器小于等于后面的容器，则返回true，否则返回false，不适用于priority_queue 如果前面的容器大于后面的容器，则返回true，否则返回false，不适用于priority_queue 如果前面的容器大于等于后面的容器，则返回true，否则返回false，不适用于priority_queue 如果前面的容器等于后面的容器，则返回true，否则返回false，不适用于priority_queue 如果前面的容器不等于后面的容器，则返回true，否则返回false，不适用于priority_queue operator= swap() operator< operator<= operator> operator>= operator== operator!= 说明 标准库容器共有的函数

11.1 标准模板库简介 表11.3 只在第一类中的函数 获得指向被控序列开始处的迭代子，引用容器第一个元素 表11.3 只在第一类中的函数 获得指向被控序列开始处的迭代子，引用容器第一个元素 获得指向被控序列末端的迭代子，引用容器最后一个元素的后继位置 获得指向被控序列末端的反转型迭代子，引用容器最后一个元素。实际上这是该容器前后反转之后的begin() 获得指向被控序列开始处的反转型迭代子，引用容器第一个元素的前导位置。实际上这是该容器前后反转之后的end() 从容器中清除一个或几个元素 从容器中清除所有元素 begin() end() rbegin() rend() erase() clear() 说明 只在第一类容器中的函数

11.1 标准模板库简介 使用STL容器或容器适配器，要包含定义该容器模板类头文件。参见表11.4。这些头文件的内容都在std名字空间域中，程序中必须加以说明。 表11.4 标准容器库的头文件 头文件 说明 <deque> <list> <map> <set> <queue> <stack> <vector> 两端队deque的头文件 表list的头文件 映射map和多重映射multimap的头文件 集合set和多重集合multimap的头文件 队queue和优先级队列priority_queue的头文件 栈stack的头文件 向量vector的头文件

11.1 标准模板库简介 　　在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访问方法最终要归于内存地址的获得，所以说迭代子是面向对象版本的指针。 　迭代子与指针有许多相同之处，但迭代子保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如++运算符总是返回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子指向的容器元素。 迭代子用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。

11.1 标准模板库简介 STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。 　　算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（generic algorithm）。 算法分为： １．修改容器的算法，即变化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等。 ２．不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如count()、find()等。 ３．数字型算法。

11.2 迭代子类 C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。 表11.5 迭代子类别 标准库迭代子类型 说明 11.2 迭代子类 　　C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。 标准库迭代子类型 说明 输入 InputIterator   输出 OutputIterator 正向 ForwardIterator 双向Bidirectional Iterator 随机访问 Random AccessIterator 从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始。 向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。 组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。 组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。 组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。 表11.5 迭代子类别

11.2 迭代子类 标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！ input output forward 11.2 迭代子类 　　标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！ input output forward bidirectional random access 图11.1 迭代子层次

11.2 迭代子类 只有第一类容器能用迭代子遍历。 表11.6 STL容器支持的迭代子类别 容器 支持的迭代子类别 顺序容器 vector 11.2 迭代子类 　　只有第一类容器能用迭代子遍历。 表11.6 STL容器支持的迭代子类别 容器 支持的迭代子类别 顺序容器 vector deque list   随机访问（random access） 双向（bidirection） 关联容器 set multiset map multimap 容器适配器 stack queue priority_queue 不支持迭代子

表11.7 各种迭代子可执行的操作 包含正向迭代子所有功能，再增加 先++后执行，前置自减迭代子 先执行后++，后置自减迭代子 双向迭代子 --p p-- 提供输入和输出迭代子的所有功能 正向迭代子 间接引用迭代子，作为左值 将一个迭代子赋给另一个迭代子 输出迭代子 *p p=p1 间接引用迭代子，作为右值 比较迭代子的相等性 比较迭代子的不等性 输入迭代子 p==p1 p!=p1 前置自增迭代子，先++后执行 后置自增迭代子，执行后再++ 所有迭代子 ++p p++ 说明 迭代操作

结合find()算法讨论迭代子与泛型算法的关系。find()定义如下： 包含双向迭代子所有功能，再增加 迭代子p递增i位（后移i位）（p本身变） 迭代子p递减i位（前移i位）（p本身变） 在p所在位置后移i位后的迭代子（迭代子p本身不变） 在p所在位置前移i位后的迭代子（迭代子p本身不变） 返回与p所在位置后移i位的元素引用 如迭代子p小于p1，返回true，所谓小，即p在p1之前 如迭代子p小于等于p1，返回true，否则返回false 如迭代子p大于等于p1，返回true，所谓大即p在p1之后 如迭代子p大于迭代子p1，返回true，否则返回false 随机访问迭代子 p+=i p-=i p+i p-i p[i] p<p1 p<=p1 p>=p1 p>p1 说明 迭代操作 　结合find()算法讨论迭代子与泛型算法的关系。find()定义如下： template<typename InputIterator,typename T > InputIterator find(InputIterator first, InputIterator last, count T value ){ for(;first!=last;++first) if(value==*first) return first; return last} 　可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。

11.2 迭代子类 【例11.1】寻找数组元素。 #include<algorithm> 11.2 迭代子类 【例11.1】寻找数组元素。 #include<algorithm> #include<iostream> using namespace std;  void main(){ int search_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.2】寻找vector容器元素。 #include<algorithm> 11.2 迭代子类 【例11.2】寻找vector容器元素。 #include<algorithm> #include<vector> #include<iostream> using namespace std; void main(){ int search_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>::iterator presult; //定义迭代子 presult=find(vec.begin(),vec.end(),search_value); cout<<"数值"<<search_value<< (presult==vec.end() ?"不存在":"存在")<<endl;}

11.2 迭代子类 在<iterator>头文件中还定义了一些专用迭代子： 11.2 迭代子类 在<iterator>头文件中还定义了一些专用迭代子： １．反转型迭代子（reverse iterator）把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上实现的是反向遍历。第一类容器支持两对操作：begin()和end()，分别返回指向容器首元素和容器的末元素的后继的迭代子；而rbegin()和rend()，分别返回指向容器末元素和容器的首元素的前导的迭代子。后一对操作用于支持反转型迭代子。 vector<int> veco; vector<int>::reverse_iterator r_iter; for(r_iter=veco.rbegin(); //将r_iter指向到末元素 r_iter!=veco.rend(); //不等于首元素的前导 r_iter++){ … … } //实际是上是递减 如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。

11.2 迭代子类 ２．插入型迭代子（insertion iterator）：可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子： 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 迭代子类 ３．流迭代子有输入流迭代子（istream_iterator）和输出流迭代子（ostream_iterator）。在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 迭代子类 【例11.3】用istream iterator从标准输入读入一个整数集到vector中。 11.2 迭代子类 【例11.3】用istream iterator从标准输入读入一个整数集到vector中。 #include<iostream> #include<iterator> #include<algorithm> #include<vector> #include<functional> using namespace std; void main(){ 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 迭代子类 首先，用一个istream_iterator迭代子input（其实参为cin，即标准输入）读入一个整数集到一个矢量类对象中，出现光标后，可输入： 41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 ^Z 例中泛型算法copy()定义如下： template<typename InputIterator,typename InputIterator,typename OutputInterator>OutputIterator copy(InputIterator first,InputIterator last,OutputInterator x){ for(;first!=last;++x,++first) *x=*first return (x); } end_of_stream是指示文件（流）的结束位置，它使用了缺省的构造函数，不必由读者去为它定参数和做任何事，这里标识符是无关紧要的，重要的是无参，调用缺省的构造函数。输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。拷贝算法要求提供一对iterator来指示文件（流）内部的开始和结束位置。我们使用由istream对象初始化的istream_iterator提供开始位置，本例中为input。 本例中插入迭代子inserter作为copy的第三个参数，它是输出型的，把流插入vec。

11.2 迭代子类 泛型算法sort()为升序排序算法，声明如下 template<typename RandomAccessInterator, typename Pr> void sort(RandomAccessIterator first, RandomAccessInterator last, Pr p); 第三参数为排序方式，greater<int>()是预定义的“大于”函数对象，排序时用它来比较数值大小。缺省时为“小于”，即升序排序。 例中用输出迭代子output来输出，泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，拷贝到output迭代子，即用空格分隔各整数的标准输出。输出为： 41 39 37 31 29 23 19 17 13 11 9 7 5 3 ４．流缓冲迭代子。这是STL后添加的一对迭代子，用来直接从一个流缓冲区（streambuffer）中插入或提取某种类型（通常为char）的元素。

11.3 顺序容器 C++标准模板库提供三种顺序容器：vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的。  1. 矢量（vector）类提供了具有连续内存地址的数据结构。通过下标运算符[ ]直接有效地访问矢量的任何元素。与数组不同，矢量的内存用尽时，矢量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。在这里内存分配是由分配子（allocator）完成。 矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，具有最强的功能 。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。

11.3 顺序容器 使用向量容器的声明如下： #include<vector> …… 11.3 顺序容器 使用向量容器的声明如下： #include<vector> …… vector<int> vi; //定义存放整形序列的向量容器对象vi，长度为0的空vector vector<float> vf; //存放实型序列的向量容器 vector<char> vch; //存放字符序列的向量容器 vector<char*>vstr;//存放字符串序列的向量容器 使用方法是典型的函数模板的使用方法。调用缺省的构造函数，创建长度为0的向量。矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。这些构造函数还可以显式给出分配子(allocator)对象。

11.3 顺序容器 2. 列表（list）是由双向链表（doubly linked list）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在§7.2节中定义的双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件<list>中。 3. 双端队列（deque）（double-ended queue）类。双端队列允许在队列的两端进行操作。以顺序表为基础，支持随机访问迭代子。 双端队列有高度的灵活性，它放松了访问的限制，对象既可从队首进队，也可以从队尾进队，同样也可从任一端出队。除了可从队首和队尾移走对象外，也支持通过使用下标操作符“[ ]”进行访问。 要增加存储空间时，可以在内存块中对deque两端分别进行分配。并且新分配的存储空间保存为指向这些块的指针数组，这样双端队列可以利用不连续内存空间。因此它的迭代子比vector的迭代子更加智能化。为双端队列分配的存储块，往往要等删除双端队列时才释放，它比重复分配（再分配和释放）更有效，但也更浪费内存。 使用双端队列，必须包含头文件<deque>。

11.4 关联容器 关联容器（associative container）能通过关键字（search key）直接访问(存储和读取元素)。四个关联容器为：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。 集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。集合与多重集合类的主要差别在于多重集合允许重复的关键字（key），而集合不允许重复的关键字。元素的顺序由比较器函数对象（comparator function object）确定。如对整型multiset，只要用比较器函数对象less<int>排序关键字，元素即可按升序排列。 multiset和set通常实现为红黑二叉排序树。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。

11.4 关联容器 【例11.4】整型多重集合关联容器类的演示。类模板声明: 11.4 关联容器 　【例11.4】整型多重集合关联容器类的演示。类模板声明: template<typename Key, typename Pred = less<Key>, typename A = allocator<Key> > class multiset; //模板参数表中的非类型参数同样可有缺省值 #include<iostream> #include<set> //包含集合头文件 #include<algorithm> //包含算法头文件 using namespace std; //C++标准库名字空间域 typedef multiset<int>INTMS; //特例取名INTMS，整型多重集合按升序排列 void main(){ const int size=16; int a[size]={17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2}; INTMS intMultiset(a,a+size); //用a来初始化INTMS容器实例 ostream_iterator<int> output(cout," "); //整型输出迭代子output，可通过cout输出一个用空格分隔的整数 cout<<"这里原来有"<<intMultiset.count(17)<<"个数值17"<<endl; //查找有几个关键字17

11.4 关联容器 请注意multiset容器中自动作了升序排列。 intMultiset.insert(17); //插入一个重复的数17 11.4 关联容器 intMultiset.insert(17); //插入一个重复的数17 cout<<"输入后这里有"<<intMultiset.count(17)<<"个数值17"<<endl; INTMS::const_iterator result; //const_iterator使程序可读INTMS的元素 //但不让程序修改它的元素，result为INTMS的迭代子 result=intMultiset.find(18); //找到则返回所在位置，设找到返回与调end()返回的同样值 if(result==intMultiset.end()) cout<<"没找到值18"<<endl; else cout<<"找到值18"<<endl; cout<<"intMultiset容器中有"<<endl; copy(intMultiset.begin(),intMultiset.end(),output); //输出容器中全部元素 cout<<endl; } 运行结果为： 这里原来有1个数值17 输入后这里有2个数值17 没找到值18 容器中有： 2 3 5 11 17 17 29 29 31 37 41 47 53 59 61 73 89 请注意multiset容器中自动作了升序排列。

11.4 关联容器 映射和多重映射类提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件<set>。

11.5 容器适配器 STL提供了三个容器适配器（container adapter）：栈，队列和优先级队。栈是标准的栈，使用时要用头文件<stack>。队也是标准的，使用时要用头文件<queue>。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明： stack<vector<char>> sk; 然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（queue）缺省用deque为基础，栈（stack）可用vector或deque为基础。 优先级队列（priority_queue）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（priority_queue）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。缺省情况下priority_queue实现时用vector为基础数据结构。

11.5 容器适配器 【例11.5】优先级队列类演示，头文件用<queue>，优先级用数表示，数值越大优先级越高。 11.5 容器适配器 【例11.5】优先级队列类演示，头文件用<queue>，优先级用数表示，数值越大优先级越高。 #include<iostream> #include<queue> #include<functional> using namespace std; void main(){ 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; } 输出结果为： 从优先级队列中弹出：18 12 9 7 

11.6 泛型算法与函数对象 　　算法表现为一系列的函数模板，它们是STL中最类似于传统函数库的部分。它们不是作为预先编译好的对象模块组成的可链接库来提供。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数，大大提高了它作为通用型程序组件的适用性。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。如每个容器都可使用find()算法。 11.6.1 函数对象 11.6.2 泛型算法

11.6.1 函数对象 每个泛型算法（generic algorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。 11.6.1 函数对象 每个泛型算法（generic algorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。 在C++中，为了使程序的安全性更好，采用“引用”来代替指针作为函数的参数或返回值。在C++的泛型算法中类似地采用了“函数对象”（function object）来代替函数指针。函数对象是一个类，它重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。和“引用”一样，“函数对象”独立使用比较少。函数对象亦称拟函数对象（function_like object）和函子（functor） 【例11.6】求和函数对象的定义和测试。 函数对象是一个类，它重载了调用操作符“()”。使用方法与类模板相同： #include<iostream.h> template<typename T>class Sum{ T res; public: Sum(T i=0):res(i){} //构造函数,即sum(T i=0){res=i;} T operator()(T x){res+=x;return res;} //累加，重载的调用操作符() T result() const {return res;} };

11.6.1 函数对象 注意Sum仅能实例化为有限种类型：整型、实型、字符型等等。 11.6.1 函数对象 template<typename FuncObject,typename T> T Func1(FuncObject fob,const T &val){return fob(val);} //不可实现累加 T Func2(FuncObject &fob,const T &val){return fob(val);} //可实现累加 void main(){ Sum<int> sum(10); int i=5,j=10; cout<<sum(j)<<'\t';cout<<sum(i)<<endl; // 检测函数对象 cout<<Func1(sum,i)<<'\t';cout<<Func1(sum,j)<<'\t'; cout<<Func1(sum,10)<<endl; //使用函数对象，但未实现累加 cout<<Func2(sum,i)<<'\t';cout<<Func2(sum,j)<<'\t'; cout<<Func2(sum,10)<<endl; //使用函数对象，实现累加 cout<<Func1(Sum<int>(5),i)<<'\t';cout<<Func1(Sum<int>(),j)<<'\t'; cout<<Func1(Sum<int>(),10)<<endl; //函数对象标准用法，未实现累加 cout<<Func2(Sum<int>(5),i)<<'\t';cout<<Func2(Sum<int>(),j)<<'\t'; cout<<Func2(Sum<int>(),10)<<endl; //函数对象标准用法，未实现累加 } 注意Sum仅能实例化为有限种类型：整型、实型、字符型等等。

11.6.1 函数对象 　函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检查。 下面给出采用函数对象作为“数值比较算法”的求序列中最小值的函数模板： template<typename Type,typename Comp> const Type& min(const Type*p,int size,Comp comp){ int minIndex=0; //最小元素下标初值为0,即设0号元素最小 for(int i=1;i<size;i++) if(comp(p[i],p[minIndex])) minIndex=i; return p[minIndex]; } 例中Comp为比较函数对象类，对不同的数据类型，可以定义不同的函数对象。

11.6.1 函数对象 函数对象有多种来源 1. 标准库预定义的一组算术，关系和逻辑函数对象； 11.6.1 函数对象 函数对象有多种来源 1. 标准库预定义的一组算术，关系和逻辑函数对象； 2. 预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展； 3. 自定义函数对象。 预定义函数对象分为算术、关系和逻辑操作。每个对象都是一个类模板，其中操作数类型作为模板参数。使用时要包含头文件： #include<functional> 以加法为例，讨论名为plus的类模板，对整数的用法实例如下： plus<int>intAdd; int ival1=30,ival2=15; int sum=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 函数对象 greater<Type>的 比较算法在内置类型int，字符串类string中定义。譬如可以自定义整数类Int，其中重载了“<”运算符： class Int{ public: Int(int ival=0):_val(ival){} int operator-(){return -_val;} //负数符号重载 int operator%(int ival){return _val%ival;} //求余符号重载 bool operator<(int ival){return _val<ival;} //小于符号重载 bool operator!(){return _val==0;} //逻辑非符号重载 private: int _val; }; 每个类对象都可以作为有名或无名对象传递给函数，同时也把所需重载的算法传递过去了。

11.6.1 函数对象 下面给出各种预定义的函数对象及其使用方法：参数和返回值。 为方便说明，定义以下变量（对象）： 11.6.1 函数对象 下面给出各种预定义的函数对象及其使用方法：参数和返回值。 为方便说明，定义以下变量（对象）： vector<string>svec; string sval1,sval2,sres; complex cval1,cval2,cres; int ival1,ival2,ires; Int Ival1,Ival2,Ires; double dval1,dval2,dres; 同时为了用实例来说明使用方法，再定义一个可用单参数函数对象(一元函数对象)的函数模板和一个可用双参数函数对象（二元函数对象）的函数模板： template<Typename FuncObject,Typename Type> Type UnaryFunc(FuncObjectfob,const Type&val){return fob(val);} Type BinaryFunc(FuncObjectfob,const Type&val1,const Type&val2){return fob(val1,val2);}

11.6.1 函数对象 算术函数对象： 加法：plus<Type> 11.6.1 函数对象 算术函数对象： 加法：plus<Type> plus<int>intPlus; ires=intPlus(ival1,ival2); dres=BinaryFunc(plus<double>(),dval1,dval2); sres=BinaryFunc(plus<string>(),sval1,sval2); 减法：minus<Type> //同加法 乘法：multiplies<Type> //不能用串，可用于复数和浮点数等 multiplies<int> intMulti;ires= intMulti(ival1,ival2); cres=BinaryFunc(multiplies<complex>(),cal1,cal2); dres=BinaryFunc(multiplies<double>(),dval1,dval2); 除法：divides<Type> //同乘法 求余：modulus<Type> //不能用于复数,浮点数,只能用于整数 modulus<Int>IntModulus; //Int 自定义类型 Ires=IntModulus(Ival1,Ival2); ires=BinaryFunc(modulus<int>(),ival1,ival2); 取反：negate<Type> //同取余,但为单参数 ires=UnaryFunc(negate<Int>(),Ival1);

11.6.1 函数对象 逻辑函数对象，这里Type必须支持逻辑运算，有两个参数。 11.6.1 函数对象 逻辑函数对象，这里Type必须支持逻辑运算，有两个参数。 逻辑与：logical_and<Type> //对应&& 逻辑或：logical_or<Type> //对应|| 逻辑非：logical_not<Type> //对应! 关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二参数相比： 等于：equal_to<Type> 不等于：not_equal_to<Type> 大于：great<Type> 大于等于：great_equal<Type> 小于：less<Type> 小于等于：less_equal<Type> 返回布尔值的函数对象称为谓词（predicate），默认的二进制谓词是小于比较操作符“<”，所以默认的排序方式都是升序排列，它采用小于比较形式。

11.6.1 函数对象 和容器类一样，函数对象也可以由函数适配器来特殊化或扩展一元（单参数）或二元（双参数）函数对象： 11.6.1 函数对象 和容器类一样，函数对象也可以由函数适配器来特殊化或扩展一元（单参数）或二元（双参数）函数对象： 1．绑定器（binder）：把二元函数对象中的一个参数固定（绑定），使之转为一元函数，C++标准库提供两种预定义的binder适配器：bind1st和bind2nd，分别绑定了第一或第二个参数。 2．取反器（negator）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。C++标准库也提供了两种negator适配器：not1和not2。not1用于一元预定义函数对象；not2用于二元预定义函数对象。

11.6.2 泛型算法 在C++标准库中给出了70余种算法，泛型算法函数名都加有后缀，这些后缀的意思如下： 11.6.2 泛型算法 　　在C++标准库中给出了70余种算法，泛型算法函数名都加有后缀，这些后缀的意思如下： 　　_if 表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素，而find查找特定的值。 　　_copy 表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。reverser算法颠倒范围中元素的排列顺序，而reverse_copy算法同时把结果复制到目标范围中。 　　其它的后缀从英文意思上立即可以认出其意义，对照附录C *在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足指定二进制谓词规则的元素，因为谓词是返回布尔值的函数对象，满足则返回true，即与满足指定条件是同样意思。

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

11.6.2 泛型算法 泛型算法分以下几类： 1．查找算法：有13种查找算法用各种策略去判断容器中是否存在一个指定值。equal_range()、lower_bound()和upper_bound()提供对半查找形式。 2．排序和通用整序算法：共有14种排序（sorting）和通用整序（ordering）算法，为容器中元素的排序提供各种处理方法。所谓整序，是按一定规律分类，如分割（partition）算法把容器分为两组，一组由满足某条件的元素组成，另一组由不满足某条件的元素组成。 3．删除和代替算法：有15种删除和代替算法。 4．排列组合算法：有2种算法。排列组合是指全排列。如：三个字符{a，b，c}组成的序列有6种可能的全排列：abc，acb，bac，bca，cab，cba；并且六种全排列按以上顺序排列，认为abc最小，cba最大，因为abc是全顺序（从小到大）而cba是全逆序（从大到小）。

11.6.2 泛型算法 5．生成和改变算法：有6种，包含生成（generate），填充（fill）等等。 11.6.2 泛型算法 5．生成和改变算法：有6种，包含生成（generate），填充（fill）等等。 6．关系算法：有7种关系算法，为比较两个容器提供了各种策略，包括相等（equal()），最大（max()），最小（min()）等等。 7．集合算法：4种集合（set）算法提供了对任何容器类型的通用集合操作。包括并（union），交（intersection），差（difference）和对称差（symmetric difference）。 8. 堆算法：有4种堆算法。堆是以数组来表示二叉树的一种形式。标准库提供大根堆（max_heap），它的每个结点的关键字大于其子结点的关键字。 9. 算术算法：该类算法有4种，使用时要求包含头文件<numeric>。

11.7 VC++中的STL 　　VC++支持STL，STL放在标准C++库中（Standard C++ Library），由一系列的头文件组成，名称采用标准STL中的名称。 　　标准C++库中与模板有关的头文件主要有：输入输出流（iostream）和标准模板库。VC++中对STL有所扩展，它另外包括以下容器： hash map； hash multimap； hash set； hash multiset； 采用散列算法。这样VC++共有11种一类容器。 　　在VC++的MFC中有微软开发的群（collections）类（微软自译为集合类，为不和set混淆，本书取群类），包括有任何类型的对象群和任何类型对象指针群： CArray； CList； CMap； CTypePtrArray； CTypePtrList； CTypePtrMap； 它们也都是模板。 　　在VC++的活动模板库类（ATL，Active Template Library）中也有微软开发的群（collections）类： CAtlArray CAtllist CAtlMap CAutoPtrArray CAutoPtrlist CAutoPtrMap 后三种为智能指针。