标准模板库STL课件.ppt

1、库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，为程序员提供大量实用的库是C+的又一特色。 标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。 11.1 标准模板库简介标准模板库简介 11.3 顺序容器顺序容器 11.2 迭代子类迭代子类 11.5 容器适配器容器适配器 11.7 VC+中的中的STL 11.6 泛型算法与函数对象泛型算法与函数对象 11.4 关

2、联容器关联容器 STL提供了一个标准化的模板化的对象容器库，包含多种数据结提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。构及其算法，可以节省大量的时间和精力，而且程序是高质量的。容器类是管理序列的类，是容纳一组对象或对象集的对象，甚容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器至可以包含混合的对象，包含一组不同类型的对象，称为异类容器（heterogeneous container），一组相同类型的对象，称为同），一组相同类型的对象，称为同类容器类容器(homoge

3、nous container)。通过由容器类提供的成员函。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。法。这样就可以把算法用于容器所管理的序列。 容器分为三大类：容器分为三大类：顺序容器（顺序容器（sequence conta

4、iner or sequential container）关联容器（关联容器（associative container）容器适配器（容器适配器（container adopter）顺序容器和关联容器称为第一类容器（顺序容器和关联容器称为第一类容器（first-class container）。另外有四种容器称为近容器（）。另外有四种容器称为近容器（near container）：）：C语言风格数组、字符串语言风格数组、字符串string、操作、操作1/0标志值的标志值的bitset和进行和进行高速数学矢量运算的高速数学矢量运算的valarray。 标准库容器类标准库容器类说明说明顺序容器顺序

5、容器vector（参量）（参量）deque（双端队列）（双端队列）list（列表）（列表） 从后面快速插入与删除，直接访问任何元素从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与删除，双链表从任何地方快速插入与删除，双链表关联容器关联容器set（集合）（集合）multiset（多重集合）（多重集合）map（映射）（映射）multimap（多重映射）（多重映射） 快速查找，不允许重复值快速查找，不允许重复值快速查找，允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对一映射

6、，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器容器适配器stack（栈）（栈）queue（队列）（队列）priority_queue（优先级（优先级队列）队列） 后进先出（后进先出（LIFO）先进先出（先进先出（FIFO）最高优先级元素总是第一个出列最高优先级元素总是第一个出列表表11.1 标准库容器类标准库容器类 STLSTL也使容器提供接口。许多基本操作是所也使容器提供接口。许多基本操作是所有容器都适用的，而有些操作则适用于类似容有容器都适用的，而有些操作则适用于类似容器的子集。可以用新的类来扩展器的子集。可

7、以用新的类来扩展STLSTL。参见表。参见表11.211.2。这些函数和运算符可通称为容器的接口。这些函数和运算符可通称为容器的接口。各容器具体接口参见附录各容器具体接口参见附录C C。使用使用STLSTL容器或容器适配器，要包含定义容器或容器适配器，要包含定义该容器模板类头文件。参见表该容器模板类头文件。参见表11.311.3。这些头文头文件的内容都在件的内容都在stdstd名字空间域（名字空间域（namespace stdnamespace std）中中，程序中必须加以说明程序中必须加以说明。 在有关数组、链表和二叉树等线性表和非线性表的讨论中，在有关数组、链表和二叉树等线性表和非线性表的

8、讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访）。访问方法最终要归于内存地址的获得，所以说问方法最终要归于内存地址的获得，所以说迭代子是面向对象版迭代子是面向对象版本的指针本的指针。迭代子与指针有许多相同之处，但迭代子与指针有许多相同之处，但迭代子保存所操作的特定迭代子保存所操作的特定容器需要的状态信息

9、容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如而且有些迭代子操作在所有容器中是一致的，如+运算符总是返运算符总是返回容器下一个元素的迭代子，间接引用符回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子，总是表示迭代子指向的容器元素。指向的容器元素。 迭代子用来将迭代子用来将STL的各部分结合在一起。从本质上说，的各部分结合在一起。从本质上说，STL提提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指

10、针，但又不仅是一个指针。对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。 STL最大的优点是提供能在各种容器中通用的算法，例如插入、最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。删除、查找、排序等等。STL提供提供70种左右的标准算法。算法只是间接通过迭代子操作种左右的标准算法。算法只是间接通过迭代子操作容器元素。容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（所以称为泛型算法（generic algorithm）。）。算法分为：算法分为：修改容器的算法，即变化序列算法

11、（修改容器的算法，即变化序列算法（mutating-sequence algorithm），如），如copy()、remove()、replace()、swap()等。等。不修改容器的算法，即非变化序列算法（不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如），如count()、find()等。等。数字型算法。数字型算法。 C+标准库中有五种预定义迭代子，其功能最强最标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。灵活的是随机访问迭代子。 标准库定义迭代子类型说明输入（InputIterator）输出（OutputItera

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

13、代子类别迭代子类别 标准库定义迭代子的层次结构，按这个层次，从上到标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！下，功能越来越强。但不是继承！inputoutputforwardbidirectionalrandom access图图11.1 迭代子层次迭代子层次 只有第一类容器能用迭代子遍历。表只有第一类容器能用迭代子遍历。表11.5给出各种不同容器所支持的给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表迭代子类别。标准库定义的各种迭代子可进行的操作参见表11.6， 容器支持的迭代子类别顺序容器vectordequelist随机访问（

14、random access）随机访问（random access）双向（bidirection）关联容器setmultisetmapmultimap双向（bidirection）双向（bidirection）双向（bidirection）双向（bidirection）容器适配器stackqueuepriority_queue不支持迭代子不支持迭代子不支持迭代子下面结合下面结合find()算法讨论迭代子与泛型算法的关系。算法讨论迭代子与泛型算法的关系。find()定义定义如下：如下： templateInputIterator find(InputIterator first, InputIte

15、rator last,count T value )for(;first!=last;+first) if(value=*first) return first;return last可见，泛型算法不直接访问容器的元素，与容器无关。元素的全可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。部访问和遍历都通过迭代子实现。并不需要预知容器类型。find()算法也支持系统内置的数组类型：算法也支持系统内置的数组类型： 【例【例11.1】寻找数组元素。】寻找数组元素。#include#includeusing namespace std; vo

16、id main()int search_value,ia9=47,29,37,23,11,7,5,31,41;cout请输入需搜索的数：请输入需搜索的数：search_value;int* presult=find(&ia0,&ia9,search_value);cout数值数值search_value(presult=&ia9 ?不存在不存在:存存在在)endl;这里这里a9数组元素并不存在，但内存地址单元存在。数组元素并不存在，但内存地址单元存在。 【例【例11.2】寻找】寻找vector容器元素。容器元素。#include#include#includeusing namespace s

17、td; void main()int search_value,ia9=47,29,37,23,11,7,5,31,41;vector vec(ia,ia+9); /数据填入数据填入vectorcout请输入需搜索的数：请输入需搜索的数：search_value;vector:iterator presult; /定义迭代子定义迭代子presult=find(vec.begin(),vec.end(),search_value);cout数值数值search_value(presult=vec.end() ?不存在不存在:存在存在)endl;在在头文件中还定义了一些专用迭代子：头文件中还定义了

18、一些专用迭代子：反转迭代子反转迭代子(reverse iterator)；插入型迭代子插入型迭代子(insertion iterator)；流迭代子流迭代子(stream iterator)；流缓冲迭代子流缓冲迭代子(stream buffer iterator)；反转型迭代子（反转型迭代子（reverse iterator）把一切都颠倒过来）把一切都颠倒过来 vector veco;vector:reverse_iterator r_iter;for(r_iter=veco.rbegin();/将将r_iter指向到末元素指向到末元素r_iter!=veco.rend();/不等于首元素的前

19、导不等于首元素的前导r_iter+)/实际是上是递减实际是上是递减/循环体循环体如果要把升序的序列改为降序的序列，只要使用反转迭代子就如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。可以了。反转迭代子定义为随机迭代子。 插入型迭代子（插入型迭代子（insertion iterator）：可以用输出迭代子来产生一个元素序列。）：可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子：可以添加元素而不必重写。有三种插入迭代子：back_insert_iterator是输出迭代子，用来将产生的元素添加到类型为是输出迭代子，用来将产生的元

20、素添加到类型为Type的容器对象的末端。就象在一个字符串末尾加一个串（的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。）。front_insert_iterator是输出迭代子，用来将产生的元素添加到容器的前是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。端，就是，产生出来的元素以逆序方式结束于被控序列前端。insert_iterator也是输出迭代子，它用来将产生的元素插入到一个也是输出迭代子，它用来将产生的元素插入到一个由迭代子（第二个参数由迭代子（第二个参数Iter）指定的元素的前面。）指定的元素的前面。 与之对应的也

21、有三个相关的适配器与之对应的也有三个相关的适配器函数，它们返回特定的插入迭代子：函数，它们返回特定的插入迭代子：back_inserter(Type&)：它使用容器的：它使用容器的push_back()插入操作代替赋值操作符，插入操作代替赋值操作符，实参是容器自己。返回一个实参是容器自己。返回一个back_inserter迭代子。迭代子。front_insertor(Type&)：使用容器的：使用容器的push_front()插入操作代替赋值操作符，插入操作代替赋值操作符，实参也是容器本身。返回一个实参也是容器本身。返回一个front_inserter迭代子。迭代子。inserter（Type

22、&,Iter）：用容器的）：用容器的insert()插入操作符代替赋值操作符。插入操作符代替赋值操作符。inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。就能顺序被插入。 流 迭 代 子 有 输 入 流 迭 代 子 （ 流 迭 代 子 有 输 入 流 迭 代 子 （ i s tr e a m _ i te r a t o r ） 和 输

23、 出 流 迭 代 子） 和 输 出 流 迭 代 子（ostream_iterator）。在）。在、等头文件中定义了流类等头文件中定义了流类库，在库，在STL中为输入中为输入/输出流输出流iostream提供了迭代子，它们可以与标准库容器类型和提供了迭代子，它们可以与标准库容器类型和泛型算法结合起来工作。使用这两个迭代子必须包含头文件泛型算法结合起来工作。使用这两个迭代子必须包含头文件。输入流迭代子（输入流迭代子（istream_iterator）类支持在）类支持在istream及其派生类（如及其派生类（如ifstream）上的迭代子操作。上的迭代子操作。istream_iterator声明方式

24、为：声明方式为：istream_iterator迭代子标识符迭代子标识符(istream&);/Type为已定义了输入操作的类型为已定义了输入操作的类型,实参可以是任意公有派生的实参可以是任意公有派生的istream的子类型的的子类型的对象对象输出流也有对应的输出流也有对应的ostream_iterator类支持，其声明方式为：类支持，其声明方式为：ostream_iterator迭代子标识符迭代子标识符(ostream&)/实参同样可以是公有派生子实参同样可以是公有派生子类型对象类型对象ostream_iterator迭代子标识符迭代子标识符(ostream&,char*)/第二参数为第二参

25、数为C风格字风格字符串符串 下面结合下面结合copy算法和算法和sort算法来介绍算法来介绍istream iterator和和ostream_iterator。【例【例11.3】用】用istream iterator从标准输入读入一个整数集到从标准输入读入一个整数集到vector中。中。#include#include#include#include#includeusing namespace std; void main()istream_iterator input(cin);istream_iterator end_of_stream;vector vec;copy(input,en

26、d_of_stream,inserter(vec,vec.begin();/输入输入Z结束流结束流sort(vec.begin(),vec.end(),greater();/升序排列升序排列ostream_iteratoroutput(cout, );unique_copy(vec.begin(),vec.end(),output); 输入：输入：41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 Z泛型算法泛型算法copy()定义如下：定义如下：templateOutputIterator copy(InputIterator first,InputIte

27、rator last,OutputInterator x)for(;first!=last;+x,+first) *x=*firstreturn (x); end_of_stream是指示文件（流）结束位置，它使用了缺省的构造函数是指示文件（流）结束位置，它使用了缺省的构造函数，输入时输入时必须在最后一个数字后加分隔符，然后加必须在最后一个数字后加分隔符，然后加Ctrl-Z结束结束。拷贝算法要求我们提供一对拷贝算法要求我们提供一对iterator来指示文件（流）内部的开始和结束位置。我们使用由来指示文件（流）内部的开始和结束位置。我们使用由istream对象初始化的对象初始化的istream_

28、iterator提供开始位置，本例中为提供开始位置，本例中为input。本例中插入迭代子本例中插入迭代子inserter作为作为copy的第三个参数，它是输出型的，把流插入的第三个参数，它是输出型的，把流插入vec。泛型算法泛型算法sort()为升序排序算法，声明如下为升序排序算法，声明如下templatevoid sort(RandomAccessIterator first, RandomAccessInterator last, Pr p);第三参数为排序方式，第三参数为排序方式，greater()是预定义的是预定义的“大于大于”函数对象，排序时用它来函数对象，排序时用它来比较数值大小。

29、缺省时为比较数值大小。缺省时为“小于小于”，即升序排序。，即升序排序。例中用输出迭代子例中用输出迭代子output来输出，泛型算法来输出，泛型算法unique_copy（），复制一个序列，（），复制一个序列，并删除序列中所有重复元素。本例中，拷贝到并删除序列中所有重复元素。本例中，拷贝到output迭代子，即用空格分隔各整数的迭代子，即用空格分隔各整数的标准输出。输出为：标准输出。输出为：41 39 37 31 29 23 19 17 13 11 9 7 5 3 流缓冲迭代子。这是流缓冲迭代子。这是STL后添加的一对迭代子，用来后添加的一对迭代子，用来直接从一个流缓冲区（直接从一个流缓冲区（s

30、treambuffer）中插入或提取某）中插入或提取某种类型（通常为种类型（通常为char）的元素。）的元素。 C+标准模板库提供三种顺序容器：标准模板库提供三种顺序容器：vector，list和和deque。vector类和类和deque类是以数组为基础的，类是以数组为基础的，list类是以双向链表为基础类是以双向链表为基础的。的。矢量（矢量（vector）类提供了具有连续内存地址的数据结构。通过下）类提供了具有连续内存地址的数据结构。通过下标运算符标运算符 直接有效地访问矢量的任何元素。与数组不同，直接有效地访问矢量的任何元素。与数组不同，vector的的内存用尽时，内存用尽时，vecto

31、r自动分配更大的连续内存区，将原先的元素复制自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量（到新的内存区，并释放旧的内存区。这是矢量（vector）类的优点。）类的优点。在这里内存分配是由分配子（在这里内存分配是由分配子（allocator）完成。）完成。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，支持随机访问迭代子，vector的迭代子通常实现为的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭元素的指针。所谓选择容器类，实际

32、上很大部分是在选择所支持的迭代子。代子。 使用向量容器的声明如下：#includevector vi;/定义存放整形序列的向量容器对象vi，长度为0的空vectorvector vf;/存放实型序列的向量容器vector vch;/存放字符序列的向量容器vector vstr;/存放字符串（字符指针）序列的向量容器使用方法是典型的函数模板的使用方法。调用缺省的构造函数，创建长度为0的向量。矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的

33、构造函数。这些构造函数还可以显式给出分配子(allocator)对象。对矢量的操作包含了在顺序表中所列出的操作，而且对矢量的操作包含了在顺序表中所列出的操作，而且更多。更多。列表（列表（list）是由双向链表（）是由双向链表（doubly linked list）组成）组成的。我们也已经在有关链表的一节中介绍过了，它有两个的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在我们在7.2节中

34、定义的双链表类模板相似，但通用性更好，节中定义的双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件使用更方便。列表的定义在头文件中。中。 双端队列（双端队列（deque）（）（double-ended queue）类。）类。双端队列允许在队列的两端进行操作。双端队列允许在队列的两端进行操作。支持随机访问迭代支持随机访问迭代子子。也支持通过使用下标操作符也支持通过使用下标操作符“ ”进行访问。进行访问。 当要增加双端队列的存储空间时，可以在内当要增加双端队列的存储空间时，可以在内存块中存块中dequedeque两端进行分配，通常保存为这些块两端进行分配，通常保存为这些块的指针数组。双

35、端队列的指针数组。双端队列利用不连续内存空间利用不连续内存空间，它它的的迭代子比迭代子比vectorvector的迭代子更加智能化的迭代子更加智能化。对双端对双端队列分配存储块后，往往要等删除双端队列时才队列分配存储块后，往往要等删除双端队列时才释放，它释放，它比重复分配（释放和再分配）更有效，比重复分配（释放和再分配）更有效，但也更浪费内存但也更浪费内存。 使用双端队列，必须包含头文件使用双端队列，必须包含头文件deque 。 查找和排序总是查找和排序总是对关键字关键字进行的，函数模板和类模进行的，函数模板和类模板中只介绍了板中只介绍了通用类型（亦称泛型类型）通用类型（亦称泛型类型），并没有

36、涉及并没有涉及关键字。关联容器（关键字。关联容器（associative container）能通过关）能通过关键字（键字（search key）直接访问）直接访问(存储和读取元素存储和读取元素)。四个。四个关联容器为：集合（关联容器为：集合（set），多重集合（），多重集合（multiset），映），映射（射（map），多重映射（），多重映射（multimap）。集合和多重集）。集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，合类提供了控制数值集合的操作，其中数值是关键字，映射和多重映射类提供了操作与关键字相关联的映射值映射和多重映射类提供了操作与关键字相关联的映射值（mappe

37、d value）的方法。）的方法。多重集合关联容器用于快速存储和读取关键字。多重集合关联容器用于快速存储和读取关键字。 multiset和set通常实现为红黑二叉排序树。常用的二叉排序树一般结点有四个域：一个数据域，三个指针域（左孩子指针，右孩子指针和双亲指针）。双亲指针使直接回访成为可能，它使二叉排序树删除节点的算法变的简单。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。 【例11.4】整型多重集合关联容器类

38、的演示。类模板声明:templatetypename Key, typename Pred = less, typename A = allocator class multiset;/模板参数表中的非类型参数同样可有缺省值 #include#include/包含集合头文件#include/包含算法头文件using namespace std; /C+标准库名字空间域typedef multiset INTMS; /特例取名INTMS，整型多重集合按升序排列 void main()const int size=16;int asize=17,11,29,89,73,53,61,37,41,29

39、,3,47,31,59,5,2;INTMS intMultiset(a,a+size);ostream_iterator output(cout, );cout这里原来有intMultiset.count(17)个数值17endl;intMultiset.insert(17); /插入一个重复的数17cout输入后这里有intMultiset.count(17)个数值17endl;INTMS:const_iterator result; result=intMultiset.find(18); if(result=intMultiset.end() cout没找到值18endl;else co

40、ut找到值18endl;coutintMultiset容器中有endl;copy(intMultiset.begin(),intMultiset.end(),output); coutendl; 请注意请注意multiset容器中自动作了升序排列容器中自动作了升序排列。如需要，如需要，可以在可以在VC+帮助中（帮助中（MSDN）由关键字）由关键字multiset查找查找有关迭代子、成员函数的定义和用法。有关迭代子、成员函数的定义和用法。多重映射和映射关联容器类用于快速存储和读取关多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字键字与相关值（关键字/数值对，数值对，key/val

41、ue pair）。）。如果保存学生的简明资料，要求按学号排序，使用映射如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用因姓名可能重复，使用多重映射更为合适。使用时要用头文件头文件。 STL提供了三个容器适配器（提供了三个容器适配器（container adapter）：栈（）：栈（stack），），队列（队列（queue）和优先级队。栈是标准的栈，使用时要用头文件）和优先级队。栈是标准的栈，使用时要用头文件。队也是标准的，使用时要用头文件队也是标准

42、的，使用时要用头文件。所谓适配器并不独立，它。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明：如下声明： stackvector sk;然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如数，它使用其实现类（如vector）的构造和析构函数。就象一个仪器加了）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（一个适配器增加了某些功能一样。队列（queue）缺省用）缺省用deq

43、ue为基础，为基础，栈（栈（stack）可用）可用vector或或deque为基础。为基础。优先级队列（优先级队列（priority_queue）适配器实现优先级队列。元素插入是）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（先级队列（priority_queue）的每个常用操作都实现为内联函数，调用基）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。

44、缺省情况下缺省情况下priority_queue实现时用实现时用vector为基础数据结构。为基础数据结构。 【例【例11.5】优先级队列类演示，头文件用】优先级队列类演示，头文件用，优先级用数表示，数值越大，优先级用数表示，数值越大优先级越高。优先级越高。#include#include#includeusing namespace std; void main()priority_queue prioque;/实例化存放实例化存放int值的优先级队列，并用值的优先级队列，并用deque作为基础数据结构作为基础数据结构prioque.push(7);/压入优先级队列压入优先级队列prioqu

45、e.push(12);prioque.push(9);prioque.push(18);cout从优先级队列中弹出从优先级队列中弹出endl;while(!prioque.empty()coutprioque.top()t;/取最高优先级数据取最高优先级数据prioque.pop();/弹出最高优先级数据弹出最高优先级数据coutendl; 算法表现为一系列的函数模板，它们完整算法表现为一系列的函数模板，它们完整定义在定义在STLSTL头文件中。一般这些函数模板都使头文件中。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作

46、。器（序列）上进行各种操作。 11.6.1 函数对象函数对象 11.6.2 泛型算法泛型算法 每个泛型算法（每个泛型算法（generic algorithm）的实现都独立于单独的容器类型，它消除）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。了算法的类型依赖性。 在在C+中，为了使程序的安全性更好，采用中，为了使程序的安全性更好，采用“引用引用”来代替指针作为函数的参来代替指针作为函数的参数或返回值。在数或返回值。在C+的泛型算法中类似地采用了的泛型算法中类似地采用了“函数对象函数对象”（function object）来代替函数指针。函数对象是一个类，它重载了函数调用操作符（来代替

47、函数指针。函数对象是一个类，它重载了函数调用操作符（operator()）。）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。和传递给泛型算法。和“引用引用”一样，一样，“函数对象函数对象”独立使用比较少。函数对象亦称独立使用比较少。函数对象亦称拟函数对象（拟函数对象（function_like object）和函子（）和函子（functor）。下面给出一个求和函）。下面给出一个求和函数对象的定义：数对象的定义：templateclass SumT res;public:sum(T

48、 i=0):res(i)/构造函数构造函数,即即sum(T i=0)res=i;void operator()(T x)res+=x;/累加累加T result() const return res;/函数对象与函数指针相比较有三个优点：第一，函数指针是间接引函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以缓冲当前数据和结果，象可以拥有任意数量的额外数据，用这些数据可以缓冲当前数据和结果，当然多数情况下不一定使用，

49、上例中当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译就是一个额外数据；第三，编译时对函数对象做类型检查。时对函数对象做类型检查。下面给出采用函数对象作为下面给出采用函数对象作为“数值比较算法数值比较算法”的求序列中最小值的函数模的求序列中最小值的函数模板。板。templateconst Type& min(const Type*p,int size,Comp comp)int minIndex=0;/最小元素下标初值为最小元素下标初值为0,即设即设0号元素最小号元素最小for(int i=1;isize;i+)if(comp(pi,pminIndex) minIndex=i

50、;return pminIndex;函数对象来源。函数对象来源。1标准库预定义的一组算术，关系和逻辑函数对象；标准库预定义的一组算术，关系和逻辑函数对象；2预定义的一组函数适配器，允许对预定义的函数对象进行特预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展；殊化或扩展；自定义函数对象。自定义函数对象。预定义函数对象分为算术、关系和逻辑操作。每个对象都是一个预定义函数对象分为算术、关系和逻辑操作。每个对象都是一个类模板，其中操作数类型作为模板参数。使用时要包含头文件：类模板，其中操作数类型作为模板参数。使用时要包含头文件：#include我们以加法为例，讨论名为我们以加法为例，讨论