标准模板库STL课件

第十一章第十一章 标准模板库（标准模板库（STL）库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，为程序员提供大量实用的库是C+的又一特色。标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包 含 了 容 器 类（container）、迭 代 子（iterator）和算法（algorithm）三个部分。第十一章标准模板库（STL）库（library）是一系1 1第十一章第十一章 标准模板库（标准模板库（STL）11.1标准模板库简介标准模板库简介11.3顺序容器顺序容器11.2迭代子类迭代子类11.5容器适配器容器适配器11.7VC+中的中的STL11.6泛型算法与函数对象泛型算法与函数对象11.4关联容器关联容器第十一章标准模板库（STL）11.1标准模板库简介2 211.1 标准模板库简介标准模板库简介STL提提供供了了一一个个标标准准化化的的模模板板化化的的对对象象容容器器库库，包包含含多多种种数数据据结结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。构及其算法，可以节省大量的时间和精力，而且程序是高质量的。容器类是管理序列的类，是容纳一组对象或对象集的对象，甚容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器至可以包含混合的对象，包含一组不同类型的对象，称为异类容器（heterogeneouscontainer），一组相同类型的对象，称为同），一组相同类型的对象，称为同类容器类容器(homogenouscontainer)。通过由容器类提供的成员函数，。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。这样就可以把算法用于容器所管理的序列。11.1标准模板库简介STL提供了一个标准化的模板化的对3 311.1 标准模板库简介标准模板库简介容器分为三大类：容器分为三大类：顺序容器（顺序容器（sequencecontainerorsequentialcontainer）关联容器（关联容器（associativecontainer）容器适配器（容器适配器（containeradopter）顺顺 序序 容容 器器 和和 关关 联联 容容 器器 称称 为为 第第 一一 类类 容容 器器（first-classcontainer）。另另外外有有四四种种容容器器称称为为近近容容器器（nearcontainer）：C语语言言风风格格数数组组、字字符符串串string、操操作作1/0标标志志值值的的bitset和和进进行行高速数学矢量运算的高速数学矢量运算的valarray。11.1标准模板库简介容器分为三大类：4 411.1 标准模板库简介标准模板库简介标准库容器类标准库容器类说明说明顺序容器顺序容器vector（参量）（参量）deque（双端队列）（双端队列）list（列表）（列表）从后面快速插入与删除，直接访问任何元素从后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从前面或后面快速插入与删除，直接访问任何元素从任何地方快速插入与删除，双链表从任何地方快速插入与删除，双链表关联容器关联容器set（集合）（集合）multiset（多重集合）（多重集合）map（映射）（映射）multimap（多重映射）（多重映射）快速查找，不允许重复值快速查找，不允许重复值快速查找，允许重复值快速查找，允许重复值一对一映射，基于关键字快速查找，不允许重复值一对一映射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器容器适配器stack（栈）（栈）queue（队列）（队列）priority_queue（优优先先级级队列）队列）后进先出（后进先出（LIFO）先进先出（先进先出（FIFO）最高优先级元素总是第一个出列最高优先级元素总是第一个出列表表11.1标准库容器类标准库容器类11.1标准模板库简介标准库容器类说明顺序容器关联容器5 511.1 标准模板库简介标准模板库简介STLSTL也也使使容容器器提提供供接接口口。许许多多基基本本操操作作是是所所有有容容器器都都适适用用的的，而而有有些些操操作作则则适适用用于于类类似似容容器器的的子子集集。可可以以用用新新的的类类来来扩扩展展STLSTL。参参见见表表11.211.2。这这些些函函数数和和运运算算符符可可通通称称为为容容器器的的接接口口。各容器具体接口参见附录各容器具体接口参见附录C C。使用使用STLSTL容器或容器适配器，要包含定义容器或容器适配器，要包含定义该容器模板类头文件。参见表该容器模板类头文件。参见表11.311.3。这些头文头文件的内容都在件的内容都在stdstd名字空间域（名字空间域（namespace namespace stdstd）中）中，程序中必须加以说明程序中必须加以说明。11.1标准模板库简介STL也使容器提供接口。许多基本6 611.1 标准模板库简介标准模板库简介在有关数组、链表和二叉树等线性表和非线性表的讨论中，在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访）。访问方法最终要归于内存地址的获得，所以说问方法最终要归于内存地址的获得，所以说迭代子是面向对象版迭代子是面向对象版本的指针本的指针。迭代子与指针有许多相同之处，但迭代子与指针有许多相同之处，但迭代子保存所操作的特定迭代子保存所操作的特定容器需要的状态信息容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如而且有些迭代子操作在所有容器中是一致的，如+运算符总是返运算符总是返回容器下一个元素的迭代子，间接引用符回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子，总是表示迭代子指向的容器元素。指向的容器元素。迭代子用来将迭代子用来将STL的各部分结合在一起。从本质上说，的各部分结合在一起。从本质上说，STL提提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。11.1标准模板库简介在有关数组、链表和二叉树等线性表7 711.1 标准模板库简介标准模板库简介STL最最大大的的优优点点是是提提供供能能在在各各种种容容器器中中通通用用的的算算法法，例例如如插插入入、删除、查找、排序等等。删除、查找、排序等等。STL提供提供70种左右的标准算法。算法只是间接通过迭代子操作种左右的标准算法。算法只是间接通过迭代子操作容器元素。容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（所以称为泛型算法（genericalgorithm）。）。算法分为：算法分为：修改容器的算法，即变化序列算法（修改容器的算法，即变化序列算法（mutating-sequencealgorithm），如），如copy()、remove()、replace()、swap()等。等。不修改容器的算法，即非变化序列算法（不修改容器的算法，即非变化序列算法（non-mutating-sequencealgorithm），如），如count()、find()等。等。数字型算法。数字型算法。11.1标准模板库简介STL最大的优点是提供能在各种容8 811.2迭代子类迭代子类C+标准库中有五种预定义迭代子，其功能最强最标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。灵活的是随机访问迭代子。标准库定义迭代子类型说明输入（InputIterator）输出（OutputIterator）正向（ForwardIterator）双向（BidirectionalIterator）随机访问（RandomAccessIterator）从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始。向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。表表11.4迭代子类别迭代子类别11.2迭代子类C+标准库中有五种预定义迭代子，9 911.2迭代子类迭代子类标标准准库库定定义义迭迭代代子子的的层层次次结结构构，按按这这个个层层次次，从从上上到到下，功能越来越强。但不是继承！下，功能越来越强。但不是继承！inputoutputforwardbidirectionalrandomaccess图图11.1迭代子层次迭代子层次11.2迭代子类标准库定义迭代子的层次结构，按这个101011.2迭代子类迭代子类只有第一类容器能用迭代子遍历。表只有第一类容器能用迭代子遍历。表11.5给出各种不同容器所支持的给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表迭代子类别。标准库定义的各种迭代子可进行的操作参见表11.6，容器支持的迭代子类别顺序容器vectordequelist随机访问（randomaccess）随机访问（randomaccess）双向（bidirection）关联容器setmultisetmapmultimap双向（bidirection）双向（bidirection）双向（bidirection）双向（bidirection）容器适配器stackqueuepriority_queue不支持迭代子不支持迭代子不支持迭代子11.2迭代子类只有第一类容器能用迭代子遍历。表1111111.2迭代子类迭代子类下下面面结结合合find()算算法法讨讨论论迭迭代代子子与与泛泛型型算算法法的的关关系系。find()定定义义如下：如下：templateInputIteratorfind(InputIteratorfirst,InputIteratorlast,countTvalue)for(;first!=last;+first)if(value=*first)returnfirst;returnlast可可见见，泛泛型型算算法法不不直直接接访访问问容容器器的的元元素素，与与容容器器无无关关。元元素素的的全全部部访访问问和和遍遍历历都都通通过过迭迭代代子子实实现现。并并不不需需要要预预知知容容器器类类型型。find()算法也支持系统内置的数组类型：算法也支持系统内置的数组类型：11.2迭代子类下面结合find()算法讨论迭代子与121211.2迭代子类迭代子类【例【例11.1】寻找数组元素。】寻找数组元素。#include#includeusingnamespacestd;voidmain()intsearch_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迭代子类【例11.1】寻找数组元素。131311.2迭代子类迭代子类【例【例11.2】寻找】寻找vector容器元素。容器元素。#include#include#includeusingnamespacestd;voidmain()intsearch_value,ia9=47,29,37,23,11,7,5,31,41;vectorvec(ia,ia+9);/数据填入数据填入vectorcout请输入需搜索的数：请输入需搜索的数：search_value;vector:iteratorpresult;/定义迭代子定义迭代子presult=find(vec.begin(),vec.end(),search_value);cout数数 值值 search_value(presult=vec.end()?不不 存存 在在:存存 在在)endl;11.2迭代子类【例11.2】寻找vector容器元素141411.2迭代子类迭代子类在在头文件中还定义了一些专用迭代子：头文件中还定义了一些专用迭代子：反转迭代子反转迭代子(reverseiterator)；插入型迭代子插入型迭代子(insertioniterator)；流迭代子流迭代子(streamiterator)；流缓冲迭代子流缓冲迭代子(streambufferiterator)；11.2迭代子类在头文件中还定义了151511.2迭代子类迭代子类反转型迭代子（反转型迭代子（reverseiterator）把一切都颠倒过来）把一切都颠倒过来vectorveco;vector:reverse_iteratorr_iter;for(r_iter=veco.rbegin();/将将r_iter指向到末元素指向到末元素r_iter!=veco.rend();/不等于首元素的前导不等于首元素的前导r_iter+)/实际是上是递减实际是上是递减/循环体循环体如果要把升序的序列改为降序的序列，只要使用反转迭代子就如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。可以了。反转迭代子定义为随机迭代子。11.2迭代子类反转型迭代子（reverseit161611.2迭代子类迭代子类插插入入型型迭迭代代子子（insertioniterator）：可可以以用用输输出出迭迭代代子子来来产产生生一一个个元元素素序序列列。可以添加元素而不必重写。有三种插入迭代子：可以添加元素而不必重写。有三种插入迭代子：back_insert_iterator是是输输出出迭迭代代子子，用用来来将将产产生生的的元元素素添添加加到到类类型型为为Type的容器对象的末端。就象在一个字符串末尾加一个串（的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。）。front_insert_iterator是是输输出出迭迭代代子子，用用来来将将产产生生的的元元素素添添加加到到容容器器的的前前端，就是，产生出来的元素以逆序方式结束于被控序列前端。端，就是，产生出来的元素以逆序方式结束于被控序列前端。insert_iterator也也是是输输出出迭迭代代子子，它它用用来来将将产产生生的的元元素素插插入入到到一一个个由由迭代子（第二个参数迭代子（第二个参数Iter）指定的元素的前面。）指定的元素的前面。与与之之对对应应的的也也有有三三个个相相关关的的适适配配器器函数，它们返回特定的插入迭代子：函数，它们返回特定的插入迭代子：back_inserter(Type&)：它它使使用用容容器器的的push_back()插插入入操操作作代代替替赋赋值值操操作作符符，实参是容器自己。返回一个实参是容器自己。返回一个back_inserter迭代子。迭代子。front_insertor(Type&)：使使用用容容器器的的push_front()插插入入操操作作代代替替赋赋值值操操作作符符，实实参也是容器本身。返回一个参也是容器本身。返回一个front_inserter迭代子。迭代子。inserter（Type&,Iter）：用容器的）：用容器的insert()插入操作符代替赋值操作符。插入操作符代替赋值操作符。inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。被插入。11.2迭代子类插入型迭代子（insertion171711.2迭代子类迭代子类 流流 迭迭 代代 子子 有有 输输 入入 流流 迭迭 代代 子子（istream_iterator）和和 输输 出出 流流 迭迭 代代 子子（ostream_iterator）。在在、等等头头文文件件中中定定义义了了流流类类库库，在在STL中中为为输输入入/输输出出流流iostream提提供供了了迭迭代代子子，它它们们可可以以与与标标准准库库容容器器类类型型和和泛型算法结合起来工作。使用这两个迭代子必须包含头文件泛型算法结合起来工作。使用这两个迭代子必须包含头文件。输输 入入 流流 迭迭 代代 子子（istream_iterator）类类 支支 持持 在在 istream及及 其其 派派 生生 类类（如如ifstream）上的迭代子操作。）上的迭代子操作。istream_iterator声明方式为：声明方式为：istream_iterator迭代子标识符迭代子标识符(istream&);/Type为为已已定定义义了了输输入入操操作作的的类类型型,实实参参可可以以是是任任意意公公有有派派生生的的istream的的子子类类型型的的对对象象输出流也有对应的输出流也有对应的ostream_iterator类支持，其声明方式为：类支持，其声明方式为：ostream_iterator迭迭代代子子标标识识符符(ostream&)/实实参参同同样样可可以以是是公公有有派派生生子子类类型对象型对象ostream_iterator迭代子标识符迭代子标识符(ostream&,char*)/第二参数为第二参数为C风格字符风格字符串串11.2迭代子类流迭代子有输入流迭代子（istre181811.2迭代子类迭代子类下面结合下面结合copy算法和算法和sort算法来介绍算法来介绍istreamiterator和和ostream_iterator。【例【例11.3】用】用istreamiterator从标准输入读入一个整数集到从标准输入读入一个整数集到vector中。中。#include#include#include#include#includeusingnamespacestd;voidmain()istream_iteratorinput(cin);istream_iteratorend_of_stream;vectorvec;copy(input,end_of_stream,inserter(vec,vec.begin();/输入输入Z结束流结束流sort(vec.begin(),vec.end(),greater();/升序排列升序排列ostream_iteratoroutput(cout,);unique_copy(vec.begin(),vec.end(),output);11.2迭代子类下面结合copy算法和sort算法来介191911.2迭代子类迭代子类输入：输入：4139572317191311373123294139Z泛型算法泛型算法copy()定义如下：定义如下：templateOutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputInteratorx)for(;first!=last;+x,+first)*x=*firstreturn(x);11.2迭代子类输入：202011.2迭代子类迭代子类end_of_stream是是指指示示文文件件（流流）结结束束位位置置，它它使使用用了了缺缺省省的的构构造造函函数数，输输入入时时必必须须在在最最后后一一个个数数字字后后加加分分隔隔符符，然然后后加加Ctrl-Z结结束束。拷拷贝贝算算法法要要求求我我们们提提供供一一对对iterator来来指指示示文文件件（流流）内内部部的的开开始始和和结结束束位位置置。我我们们使使用用由由istream对对象象初初始始化化的的istream_iterator提供开始位置，本例中为提供开始位置，本例中为input。本例中插入迭代子本例中插入迭代子inserter作为作为copy的第三个参数，它是输出型的，把流插入的第三个参数，它是输出型的，把流插入vec。泛泛 型型 算算 法法 sort()为为 升升 序序 排排 序序 算算 法法，声声 明明 如如 下下 templatevoidsort(RandomAccessIteratorfirst,RandomAccessInteratorlast,Prp);第第三三参参数数为为排排序序方方式式，greater()是是预预定定义义的的“大大于于”函函数数对对象象，排排序序时时用用它它来来比较数值大小。缺省时为比较数值大小。缺省时为“小于小于”，即升序排序。，即升序排序。例例中中用用输输出出迭迭代代子子output来来输输出出，泛泛型型算算法法unique_copy（），复复制制一一个个序序列列，并并删删除除序序列列中中所所有有重重复复元元素素。本本例例中中，拷拷贝贝到到output迭迭代代子子，即即用用空空格格分分隔隔各各整整数数的的标标准输出。输出为：准输出。输出为：41393731292319171311975311.2迭代子类end_of_stream是指示212111.2迭代子类迭代子类流缓冲迭代子。这是流缓冲迭代子。这是STL后添加的一对迭代子，用来后添加的一对迭代子，用来直接从一个流缓冲区（直接从一个流缓冲区（streambuffer）中插入或提取某种）中插入或提取某种类型（通常为类型（通常为char）的元素。）的元素。11.2迭代子类流缓冲迭代子。这是STL后添加的一222211.3顺序容器顺序容器C+标准模板库提供三种顺序容器：标准模板库提供三种顺序容器：vector，list和和deque。vector类和类和deque类是以数组为基础的，类是以数组为基础的，list类是以双向链表为基础的。类是以双向链表为基础的。矢矢量量（vector）类类提提供供了了具具有有连连续续内内存存地地址址的的数数据据结结构构。通通过过下下标标运运算算符符直直接接有有效效地地访访问问矢矢量量的的任任何何元元素素。与与数数组组不不同同，vector的的内内存存用用尽尽时时，vector自自动动分分配配更更大大的的连连续续内内存存区区，将将原原先先的的元元素素复复制制到到新新的的内内存存区区，并并释释放放旧旧的的内内存存区区。这这是是矢矢量量（vector）类类的的优优点点。在这里内存分配是由分配子（在这里内存分配是由分配子（allocator）完成。）完成。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，支持随机访问迭代子，vector的迭代子通常实现为的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。代子。11.3顺序容器C+标准模板库提供三种顺序容器：232311.3顺序容器顺序容器使用向量容器的声明如下：#includevectorvi;/定义存放整形序列的向量容器对象vi，长度为0的空vectorvectorvf;/存放实型序列的向量容器vectorvch;/存放字符序列的向量容器vectorvstr;/存放字符串（字符指针）序列的向量容器使用方法是典型的函数模板的使用方法。调用缺省的构造函数，创建长度为0的向量。矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。这些构造函数还可以显式给出分配子(allocator)对象。11.3顺序容器使用向量容器的声明如下：242411.3顺序容器顺序容器对矢量的操作包含了在顺序表中所列出的操作，而且对矢量的操作包含了在顺序表中所列出的操作，而且更多。更多。列表（列表（list）是由双向链表（）是由双向链表（doublylinkedlist）组成）组成的。我们也已经在有关链表的一节中介绍过了，它有两个的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在我们在7.2节中定义的双链表类模板相似，但通用性更好，节中定义的双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件使用更方便。列表的定义在头文件中。中。双端队列（双端队列（deque）（）（double-endedqueue）类。）类。双端队列允许在队列的两端进行操作。双端队列允许在队列的两端进行操作。支持随机访问迭代支持随机访问迭代子子。也支持通过使用下标操作符也支持通过使用下标操作符“”进行访问。进行访问。11.3顺序容器对矢量的操作包含了在顺序表中所列出的252511.3顺序容器顺序容器当当要要增增加加双双端端队队列列的的存存储储空空间间时时，可可以以在在内内存存块块中中dequedeque两两端端进进行行分分配配，通通常常保保存存为为这这些些块块的的指指针针数数组组。双双端端队队列列利利用用不不连连续续内内存存空空间间，它它的的迭迭代代子子比比vectorvector的的迭迭代代子子更更加加智智能能化化。对对双双端端队队列列分分配配存存储储块块后后，往往往往要要等等删删除除双双端端队队列列时时才才释释放放，它它比比重重复复分分配配（释释放放和和再再分分配配）更更有有效效，但也更浪费内存但也更浪费内存。使用双端队列，必须包含头文件使用双端队列，必须包含头文件。11.3顺序容器当要增加双端队列的存储空间时，可以在262611.4关联容器关联容器查找和排序总是查找和排序总是对关键字关键字进行的，函数模板和类模进行的，函数模板和类模板中只介绍了板中只介绍了通用类型（亦称泛型类型）通用类型（亦称泛型类型），并没有涉及并没有涉及关键字。关联容器（关键字。关联容器（associativecontainer）能通过关）能通过关键字（键字（searchkey）直接访问）直接访问(存储和读取元素存储和读取元素)。四个。四个关联容器为：集合（关联容器为：集合（set），多重集合（），多重集合（multiset），映），映射（射（map），多重映射（），多重映射（multimap）。集合和多重集）。集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，合类提供了控制数值集合的操作，其中数值是关键字，映射和多重映射类提供了操作与关键字相关联的映射值映射和多重映射类提供了操作与关键字相关联的映射值（mappedvalue）的方法。）的方法。多重集合关联容器用于快速存储和读取关键字。多重集合关联容器用于快速存储和读取关键字。11.4关联容器查找和排序总是对关键字进行的，函数272711.4关联容器关联容器multiset和set通常实现为红黑二叉排序树。常用的二叉排序树一般结点有四个域：一个数据域，三个指针域（左孩子指针，右孩子指针和双亲指针）。双亲指针使直接回访成为可能，它使二叉排序树删除节点的算法变的简单。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。11.4关联容器multiset和set通常实现为282811.4关联容器关联容器【例11.4】整型多重集合关联容器类的演示。类模板声明:templatetypename Key,typename Pred=less,typename A=allocatorclassmultiset;/模板参数表中的非类型参数同样可有缺省值#include#include/包含集合头文件#include/包含算法头文件usingnamespacestd;/C+标准库名字空间域typedefmultisetINTMS;/特例取名INTMS，整型多重集合按升序排列11.4关联容器【例11.4】整型多重集合关联容器类的292911.4关联容器关联容器voidmain()constintsize=16;intasize=17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2;INTMSintMultiset(a,a+size);ostream_iteratoroutput(cout,);cout这里原来有intMultiset.count(17)个数值17endl;intMultiset.insert(17);/插入一个重复的数17cout输入后这里有intMultiset.count(17)个数值17endl;INTMS:const_iteratorresult;result=intMultiset.find(18);if(result=intMultiset.end()cout没找到值18endl;elsecout找到值18endl;coutintMultiset容器中有endl;copy(intMultiset.begin(),intMultiset.end(),output);coutendl;11.4关联容器voidmain()const303011.4关联容器关联容器请请注注意意multiset容容器器中中自自动动作作了了升升序序排排列列。如如需需要要，可可以以在在VC+帮帮助助中中（MSDN）由由关关键键字字multiset查查找找有关迭代子、成员函数的定义和用法。有关迭代子、成员函数的定义和用法。多重映射和映射关联容器类用于快速存储和读取关多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字键字与相关值（关键字/数值对，数值对，key/valuepair）。）。如果保存学生的简明资料，要求按学号排序，使用映射如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用因姓名可能重复，使用多重映射更为合适。使用时要用头文件头文件。11.4关联容器请注意multiset容器中自动作313111.5容器适配器容器适配器STL提供了三个容器适配器（提供了三个容器适配器（containeradapter）：栈（）：栈（stack），），队列（队列（queue）和优先级队。栈是标准的栈，使用时要用头文件）和优先级队。栈是标准的栈，使用时要用头文件。队也是标准的，使用时要用头文件队也是标准的，使用时要用头文件。所谓适配器并不独立，它依。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明：下声明：stackvectorsk;然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如数，它使用其实现类（如vector）的构造和析构函数。就象一个仪器加了）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（一个适配器增加了某些功能一样。队列（queue）缺省用）缺省用deque为基础，为基础，栈（栈（stack）可用）可用vector或或deque为基础。为基础。优先级队列（优先级队列（priority_queue）适配器实现优先级队列。元素插入是）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（先级队列（priority_queue）的每个常用操作都实现为内联函数，调用基）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。缺省情况下缺省情况下priority_queue实现时用实现时用vector为基础数据结构。为基础数据结构。11.5容器适配器STL提供了三个容器适配器（co323211.5容器适配器容器适配器【例例11.5】优优先先级级队队列列类类演演示示，头头文文件件用用，优优先先级级用用数数表表示示，数数值值越越大大优优先级越高。先级越高。#include#include#includeusingnamespacestd;11.5容器适配器【例11.5】优先级队列类演示，头文333311.5容器适配器容器适配器voidmain()priority_queueprioque;/实例化存放实例化存放int值的优先级队列，并用值的优先级队列，并用deque作为基础数据结构作为基础数据结构prioque.push(7);/压入优先级队列压入优先级队列prioque.push(12);prioque.push(9);prioque.push(18);cout从优先级队列中弹出从优先级队列中弹出endl;while(!prioque.empty()coutprioque.top()t;/取最高优先级数据取最高优先级数据prioque.pop();/弹出最高优先级数据弹出最高优先级数据coutendl;11.5容器适配器voidmain()343411.6泛型算法与函数对象泛型算法与函数对象算法表现为一系列的函数模板，它们完整算法表现为一系列的函数模板，它们完整定义在定义在STLSTL头文件中。一般这些函数模板都使头文件中。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。（序列）上进行各种操作。11.6.1函数对象函数对象 11.6.2泛型算法泛型算法 11.6泛型算法与函数对象算法表现为一系列的函数模353511.6.1函数对象函数对象每个泛型算法（每个泛型算法（genericalgorithm）的实现都独立于单独的容器类型，它消除）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。了算法的类型依赖性。在在C+中中，为为了了使使程程序序的的安安全全性性更更好好，采采用用“引引用用”来来代代替替指指针针作作为为函函数数的的参参数数或或返返回回值值。在在C+的的泛泛型型算算法法中中类类似似地地采采用用了了“函函数数对对象象”（functionobject）来来代代替替函函数数指指针针。函函数数对对象象是是一一个个类类，它它重重载载了了函函数数调调用用操操作作符符（operator()）。该该操操作作符符封封装装了了应应该该被被实实现现为为一一个个函函数数的的操操作作。典典型型情情况况下下，函函数数对对象象被被作作为为实实参参传传递递给给泛泛型型算算法法。和和“引引用用”一一样样，“函函数数对对象象”独独立立使使用用比比较较少少。函函数数对对象象亦亦称称拟拟函函数数对对象象（function_likeobject）和和函函子子（functor）。下下面给出一个求和函数对象的定义：面给出一个求和函数对象的定义：templateclassSumTres;public:sum(Ti=0):res(i)/构造函数构造函数,即即sum(Ti=0)res=i;voidoperator()(Tx)res+=x;/累加累加Tresult()constreturnres;/11.6.1函数对象每个泛型算法（generica363611.6.1函数对象函数对象函函数数对对象象与与函函数数指指针针相相比比较较有有三三个个优优点点：第第一一，函函数数指指针针是是间间接接引引用用，不不能能作作为为内内联联函函数数，而而函函数数对对象象可可以以，这这样样速速度度更更快快；第第二二，函函数数对对象象可可以以拥拥有有任任意意数数量量的的额额外外数数据据，用用这这些些数数据据可可以以缓缓冲冲当当前前数数据据和和结结果果，当当然然多多数数情情况况下下不不一一定定使使用用，上上例例中中res就就是是一一个个额额外外数数据据；第第三三，编编译译时时对函数对象做类型检查。对函数对象做类型检查。下下面面给给出出采采用用函函数数对对象象作作为为“数数值值比比较较算算法法”的的求求序序列列中中最最小小值值的的函函数数模模板。板。templateconstType&min(constType*p,intsize,Compcomp)intminIndex=0;/最小元素下标初值为最小元素下标初值为0,即设即设0号元素最小号元素最小for(inti=1;isize;i+)if(comp(pi,pminIndex)minIndex=i;returnpminIndex;11.6.1函数对象函数对象与函数指针相比较有三个373711.6.1函数对象函数对象函数对象来源。函数对象来源。1标准库预定义的一组算术，关系和逻辑函数对象；标准库预定义的一组算术，关系和逻辑函数对象；2预预定定义义的的一一组组函函数数适适配配器器，允允许许对对预预定定义义的的函函数数对对象象进进行行特特殊化或扩展；殊化或扩展；自定义函数对象。自定义函数对象。预预定定义义函函数数对对象象分分为为算算术术、关关系系和和逻逻辑辑操操作作。每每个个对对象象都都是是一一个个类模板，其中操作数类型作为模板参数。使用时要包含头文件：类模板，其中操作数类型作为模板参数。使用时要包含头文件：#include11.6.1函数对象函数对象来源。383811.6.1函数对象函数对象我我们们以以加加法法为为例例，讨讨论论名名为为plus的的类类模模板板，对对整整数数的的用用法法实实例如下：例如下：plusintAdd;intival1=30,ival2=15;intsum=intAdd(ival1,ival2);/等效于等效于:sum=ival1+inval2但但是是函函数数对对象象主主要要是是作作为为泛泛型型算算法法的的实实参参使使用用，通通常常用用来来改改变缺省的操作，比如在【例变缺省的操作，比如在【例11.3】中有】中有sort(vec.begin(),vec.end(),greater();这这就就是是把把整整数数的的大大于于关关系系函函数数对对象象作作为为实实参参，得得降降序序排排列列。如果是字符串，则有：如果是字符串，则有：sort(svec.begin(),svec.end(),greater();11.6.1函数对象我们以加法为例，讨论名为plu393911.6.1函数对象函数对象比较算法在内置类型比较算法在内置类型int，字符串类，字符串类string中定义。还可以自定义整数类中定义。还可以自定义整数类Int:classIntpublic:Int(intival=0):_val(ival)intoperator_()return-_val;/负数符号重载负数符号重载intoperator%(intval)return_val%ival;/求余符号重载求余符号重载booloperator(intval)return_valival;/小于符号重载小于符号重载booloperator!()return_val=0;/逻辑非符号重载逻辑非符号重载private:int_val;每个类对象都可以作为有名或无名对象传给函数，同时也把所需重载的算法传每个类对象都可以作为有名或无名对象传给函数，同时也把所需重载的算法传过去了。过去了。11.6.1函数对象比较算法在内置类型int，字符404011.6.1函数对象函数对象下下面面给给出出各各种种函函数数对对象象及及其其使使用用方方法法：参参数数和和返返回回值值。为为方便，定义以下变量（对象）方便，定义以下变量（对象）vectorsvec;stringsval1,sval2,sres;complexcval1,cval2,cres;intival1,ival2,ires;IntIval1,Ival2,Ires;doubledval1,dval2,dres;11.6.1函数对象下面给出各种函数对象及其使用方414111.6.1函数对象函数对象为为了了用用实实例例来来说说明明使使用用方方法法，定定义义一一个个可可用用单单参参数数函函数数对对象象(一一元元函函数数对对象象)的的函函数数模模板板和和一一个个可可用用双双参参数数函函数数对对象象（二二元元函函数对象）的函数模板：数对象）的函数模板：templateTypeUnaryFunc(FuncObjectfob,constType&val)returnfob(val);templateTypeBinaryFunc(FuncObjectfob,constType&val1,constType&val2)returnfob(val1,val2);11.6.1函数对象为了用实例来说明使用方法，定义424211.6.1函数对象函数对象算术函数对象：算术函数对象：加法：加法：plusminusintSub;ires=intSub(ival1,ival2);dres=BinaryFunc(plus(),dval1,dval2);sres=BinaryFunc(plus(),sval1,sval2);减法：减法：minus/同加法同加法乘法：乘法：multiplies/对串类无定义对串类无定义,不能用串，可用于复数和浮点数等不能用串，可用于复数和浮点数等cres=BinaryFunc(multiplies(),cal1,cal2);dres=BinaryFunc(multiplies(),dval1,dval2);除法：除法：divides/同乘法同乘法求余：求余：modulus/不能用于复数不能用于复数,浮点数浮点数,只能用于整数只能用于整数modulusImtModulus;Ires=IntModulusIval1,Ival2);/自自定定义义类类型型ires=BinaryFunc(modulus(),ival1,ival2);11.6.1函数对象算术函数对象：434311.6.1函数对象函数对象取反：取反：negate/同取余同取余,但为单参数但为单参数ires=UnaryFunc(negate(),Ival1);逻辑函数对象，这里逻辑函数对象，这里Type必须支持逻辑运算，有两个参数。必须支持逻辑运算，有两个参数。逻辑与：逻辑与：/对应对应&逻辑或：逻辑或：/对应对应|逻辑非：逻辑非：/对应对应!关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二参数相比：关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二参数相比：等于：等于：equal_to不等于：不等于：not_equal_to大于：大于：great大于等于：大于等于：great_equal小于：小于：less小于等于：小于等于：less_equal11.6.1函数对象取反：negate/444411.6.1函数对象函数对象返返回回布布尔尔值值的的函函数数对对象象称称为为谓谓词词（predicate），默默认认的的二二进进制制谓谓词词是是小小于于比比较较操操作作符符“”，所所以以默默认认的的排排序序方方式式都都是是升升序序排列，它采用小于比较形式。排列，它采用小于比较形式。和和容容器器类类一一样样，函函数数对对象象也也可可以以由由函函数数适适配配器器来来特特殊殊化化或或扩扩展展一元（单参数）或二元（双参数）函数对象：一元（单参数）或二元（双参数）函数对象：1绑绑定定器器（binder）：把把二二元元函函数数对对象象中中的的一一个个参参数数固固定定（绑绑定定），使使之之转转为为一一元元函函数数，C+标标准准库库提提供供两两种种预预定定义义的的binder适配器：适配器：bind1st和和bind2nd，分别绑定了第一或第二个参数。，分别绑定了第一或第二个参数。取反器（取反器（negator）：把函数对象的值翻转的适配器，如原来）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。为小于，用了它后就变成了大于。C+标准库也提供了两种标准库也提供了两种negator适配器：适配器：not1和和not2。not1用于一元预定义函数对象；用于一元预定义函数对象；not2用于二元预定义函数对象。用于二元预定义函数对象。11.6.1函数对象返回布尔值的函数对象称为谓词（454511.6.2泛型算法泛型算法在在C+标标准准库库中中给给出出了了70余余种种算算法法，泛泛型型算算法法函函数数名都加有后缀，这些后缀的意思如下：名都加有后缀，这些后缀的意思如下：_if表表示示函函数数采采用用的的操操作作是是在在元元素素上上，而而不不是是对对元元素素的的值值本本身身进进行行操操作作。如如find_if算算法法表表示示查查找找一一些些值满足函数指定条件的元素，而值满足函数指定条件的元素，而find查找特定的值。查找特定的值。_copy表表示示算算法法不不仅仅操操作作元元素素的的值值，而而且且还还把把修修改改的的值值复复制制到到一一个个目目标标范范围围中中。reverser算算法法颠颠倒倒范范围围中中元元素素的的排排列列顺顺序序，而而reverse_copy算算法法同同时时把把结结果果复复制到目标范围中。制到目标范围中。其它的后缀从英文意思上立即可以认出其意义，对其它的后缀从英文意思上立即可以认出其意义，对照附录照附录C11.6.2泛型算法在C+标准库中给出了70余种464611.6.2泛型算法泛型算法其其次次我我们们介介绍绍泛泛型型算算法法的的构构造造与与使使用用方方法法。所所有有泛泛型型算算法法的的前前两两个个实实参参是是一一对对iterator，通通常常称称为为first和和last，它它们们标标出出要要操操作作的的容容器器或或内内置置数数组组中中的的元元素素范范围围。元元素素的的范范围围，包包括括first，但但不不包包含含last的的左左闭闭合合区区间间。即：即：first,last)当当first=last成立，则范围为空。成立，则范围为空。对对iterator的类则要求在每个算法声明中指出（的类则要求在每个算法声明中指出（5个基个基本类别），所声明的是最低要求。本类别），所声明的是最低要求。11.6.2泛型算法其次我们介绍泛型算法的构造与使474711.6.2泛型算法泛型算法泛型算法分以下几类：泛型算法分以下几类：查查找找算算法法：有有13种种查查找找算算法法用用各各种种策策略略去去判判断断容容器器中中是是否否存存在在一一个个指指定定值值。equal_range()、low