C++电子(下)第十一章

1、整理课件第十一章第十一章 标准模板库（选读）标准模板库（选读） 库（库（library）是一系列程序组件的集合，它们）是一系列程序组件的集合，它们可以在不同的程序中重复使用。可以在不同的程序中重复使用。 库函数设计的第一位的要求就是通用性库函数设计的第一位的要求就是通用性，模板，模板（template）为通用性带来了不可估量的前景。）为通用性带来了不可估量的前景。 标准模板库（标准模板库（Standard Template Library）是）是ANSI/ISO C+最有特色、最实用的部分之一最有特色、最实用的部分之一。STL包含包含:容器类（容器类（container）迭代子（迭代子（ite

2、rator）算法（算法（algorithm） 泛型算法（泛型算法（generic algorithm）和函数对象）和函数对象（function object）的概念与使用使算法摆脱了对不同）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖。类型数据个性操作的依赖。 标准模板库的引入：标准模板库的引入：整理课件11.1 标准模板库简介标准模板库简介 11.3 顺序容器顺序容器 11.2 迭代子类迭代子类 11.6 容器适配器容器适配器 11.4 泛型算法与函数对象泛型算法与函数对象 11.5 关联容器关联容器 第十一章第十一章 标准模板库（标准模板库（选读选读）整理课件 标准模板库简介标准模

3、板库简介容器类容器类（Container）容器类是管理序列的类，是容纳一组对象或对象集的类。通过容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回素，删除元素，查找元素等操作，这些成员函数通过返回迭代子迭代子来指定元素在序列中的位置。来指定元素在序列中的位置。容器分为三大类：容器分为三大类：顺序容器（顺序容器（Sequence Container or Sequential Container）关联容器（关联容器（Associative Co

4、ntainer）容器适配器（容器适配器（Container Adopter）参见。参见。整理课件 标准模板库简介标准模板库简介顺序容器和关联容器称为第一类容器（顺序容器和关联容器称为第一类容器（first-class container）。）。STL也使容器提供类似的接口。许多也使容器提供类似的接口。许多基本操作是所有容基本操作是所有容器都适用的器都适用的，可以用有类似操作的新类来扩展，可以用有类似操作的新类来扩展STL。这。这些函数和运算符可通称为容器的接口。些函数和运算符可通称为容器的接口。表表11.2 所有标准库容器共有的函数所有标准库容器共有的函数整理课件 标准模板库简介标准模板库简介

5、(2) 泛型算法（泛型算法（Generic Algorithm）：）：在模板中算法不依赖于具体的数据类型，而泛型算法更进一在模板中算法不依赖于具体的数据类型，而泛型算法更进一步不依赖于具体的容器。泛型算法中采用函数对象步不依赖于具体的容器。泛型算法中采用函数对象（Function ObjectFunction Object）引入不同情况下同一算法的差异。它没）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使有使用继承和多态，避免了虚函数的开销，使STLSTL效率更高。效率更高。 迭代子把算法与容器连接起来。注意算法只是间接通过迭代子迭代子把算法与容器连接起来。注意算法

6、只是间接通过迭代子操作容器元素，算法本身与容器无关。算法通常返回迭代子。操作容器元素，算法本身与容器无关。算法通常返回迭代子。 (3) 迭代子（迭代子（Iterator）：）：迭代子是指针概念的泛型化，它指向容器中的元素，它能象迭代子是指针概念的泛型化，它指向容器中的元素，它能象指针一样增减，轮流指示容器中每个元素。所以说迭代子是指针一样增减，轮流指示容器中每个元素。所以说迭代子是面向对象版本的指针。迭代子可以包括指针，但迭代子又不面向对象版本的指针。迭代子可以包括指针，但迭代子又不仅仅是一个指针。仅仅是一个指针。整理课件11.2 迭代子类迭代子类迭代子属性：迭代子属性：C+C+标准库中对普通

7、类型迭代子按照基本访问功能分类，标准库中对普通类型迭代子按照基本访问功能分类，有五种四级（输入有五种四级（输入/ /输出为同一级）预定义迭代子，其功能输出为同一级）预定义迭代子，其功能最强最灵活的是随机访问迭代子。最强最灵活的是随机访问迭代子。表表11.3 迭代子属性迭代子属性表表11.4 各种迭代子可执行的操作各种迭代子可执行的操作【例【例11.1】寻找数组元素。】寻找数组元素。由本例演示可见，由本例演示可见，泛型算法不直接访问容器的元素，所泛型算法不直接访问容器的元素，所以与容器无关。元素的全部访问和遍历都通过迭代子实以与容器无关。元素的全部访问和遍历都通过迭代子实现，并不需要预知容器类型

8、。现，并不需要预知容器类型。整理课件11.3 顺序容器顺序容器顺序容器：顺序容器：vector，list和和deque。vector类和类和deque类是以数组为基础的，类是以数组为基础的，list类是以双向链表类是以双向链表为基础的。为基础的。11.3.1 矢量类矢量类11.3.2 列表类列表类11.3.3 双端队列类双端队列类整理课件11.3. 1 矢量类矢量类矢量类的概念：矢量类的概念： 矢量（矢量（vectorvector）类提供了具有连续内存地址的数据结构。）类提供了具有连续内存地址的数据结构。它可通过下标运算符它可通过下标运算符 直接有效地访问矢量的任何元素。直接有效地访问矢量的任

9、何元素。 与数组不同，与数组不同，vectorvector的内存用尽时，的内存用尽时，vectorvector自动分配更大自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。内存区。这是矢量类的优点。 内存分配由分配子（内存分配由分配子（AllocatorAllocator）完成。分配子也是类，）完成。分配子也是类，它运用了它运用了newnew和和deletedelete运算符，本教材不作进一步讨论。运算符，本教材不作进一步讨论。矢量类的矢量类的迭代子迭代子：每个容器都有自己所支持的迭代子类型，迭代子

10、决定了可采用每个容器都有自己所支持的迭代子类型，迭代子决定了可采用哪种算法。哪种算法。vectorvector支持随机访问迭代子，具有最强的功能。支持随机访问迭代子，具有最强的功能。vectorvector的迭代子通常实现为的迭代子通常实现为vectorvector元素的指针。元素的指针。所谓选择容器所谓选择容器类，实际上很大部分是选择所支持的迭代子类，实际上很大部分是选择所支持的迭代子。整理课件11.3. 1 矢量类矢量类矢量容器的声明：矢量容器的声明：#includevector vi; /定义存放整形序列的向量容器对象定义存放整形序列的向量容器对象vi，长度为，长度为0的空的空vecto

11、rvector vf;/存放实型序列的向量容器存放实型序列的向量容器vector vch; /存放字符序列的向量容器存放字符序列的向量容器vectorvstr; /存放字符串序列的向量容器存放字符串序列的向量容器整理课件11.3.1 矢量类矢量类矢量容器的构造函数：矢量容器的构造函数：vector(size_t n); /构造一个有构造一个有n个元素的矢量，个元素的矢量，/每个元素都是由默认的构造函数所建立的每个元素都是由默认的构造函数所建立的vector(size_t n,T& V); /T表示矢量的基本类型，如表示矢量的基本类型，如int；/为每个元素用同一个对象为每个元素用同一个对象V来

12、赋初值来赋初值vector(first,last);/元素的初值由区间元素的初值由区间first,last)指定的序列中的元素复制而来指定的序列中的元素复制而来 vector(vector& X) /复制构造函数复制构造函数这些构造函数还可以显式给出分配子这些构造函数还可以显式给出分配子(allocator)对象。对象。【例【例11.2】寻找寻找vector容器元素。容器元素。对矢量的操作包含了第六章在顺序表中所列出的操作，甚至对矢量的操作包含了第六章在顺序表中所列出的操作，甚至更丰富。每种操作都是成员函数。对用户自定义的元素类，更丰富。每种操作都是成员函数。对用户自定义的元素类，要重载要重载

13、“= =”= =”和和“”等比较运算符。等比较运算符。整理课件11.3.1 矢量类矢量类特殊类型迭代子：特殊类型迭代子： *它们本身也具有五种四级迭代子属性之一它们本身也具有五种四级迭代子属性之一反转型迭代子（反转型迭代子（Reverse Iterator）：）：它是把一切都颠倒过来。正向遍历一个第一类容器时，如果它是把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上实现的是反向遍历。用了反转迭代子，实际上实现的是反向遍历。begin()和和end()，分别返回指向容器首元素和容器的末元素的后继的迭代子；，分别返回指向容器首元素和容器的末元素的后继的迭代子；而而rbegin

14、()和和rend()，分别返回指向容器末元素和容器的首元素的前导的普，分别返回指向容器末元素和容器的首元素的前导的普通迭代子。后一对操作用于支持反转型迭代子。通迭代子。后一对操作用于支持反转型迭代子。：vector veco;vector:reverse_iterator r_iter;for(r_iter=veco.rbegin(); /将将r_iter指向到末元素指向到末元素r_iter!=veco.rend(); /不等于首元素的前导不等于首元素的前导r_iter+) /实际上是递减实际上是递减/循环体循环体如果需要把升序的序列改为降序的序列时，并不需要真正去逆序一个序列，如果需要把升序

15、的序列改为降序的序列时，并不需要真正去逆序一个序列，只要使用反转迭代子就可以了。只要使用反转迭代子就可以了。反转迭代子属性为随机迭代子。反转迭代子属性为随机迭代子。整理课件11.3.1 矢量类矢量类插入型迭代子（插入型迭代子（Insertion Iterator）：）：当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全重写。例如普通输出迭代子可以把一个矢量重写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量的内容复制到另一个矢量b中，中，复制可以从矢量复制可以从矢量b任一元素开始，矢量任一元素开始，矢量b对

16、应位置上的元素被覆盖，相当于对应位置上的元素被覆盖，相当于改写。插入迭代子则可以添加元素，复制时它可以把矢量改写。插入迭代子则可以添加元素，复制时它可以把矢量a插入到矢量插入到矢量b任任一位置。同一个一位置。同一个copy()算法用不同类型迭代子，结果是不同的。算法用不同类型迭代子，结果是不同的。 有三种插入迭代子，属性均为输出迭代子：有三种插入迭代子，属性均为输出迭代子：insert_iterator用来将新元素插入到一个由迭代子（第二个参数用来将新元素插入到一个由迭代子（第二个参数Iter）指定的元素）指定的元素的前面（所谓插在的前面（所谓插在a10之前，即在之前，即在a9和和a10之间添

17、加）。之间添加）。back_insert_iterator用来将新元素添加到类型为用来将新元素添加到类型为Type的容器对象的末端；的容器对象的末端；front_insert_iterator用来将新元素添加到容器的前端（注意：新添加的元素以逆序方式用来将新元素添加到容器的前端（注意：新添加的元素以逆序方式结束于被控序列前端结束于被控序列前端,即最后添加的元素放在最前面）。即最后添加的元素放在最前面）。 整理课件11.3.1 矢量类矢量类插入型迭代子使用方法：插入型迭代子使用方法：标准库定义了一组（标准库定义了一组（3个）插入型迭代子适配器函数。它们返回对应的插入个）插入型迭代子适配器函数。它

18、们返回对应的插入迭代子：迭代子：Inserter(Type&,Iter)它使用容器的它使用容器的insert()插入操作符代替赋值操作符。插入操作符代替赋值操作符。inserter()函数要求两个函数要求两个实参：容器本身和它的一个指示起始插入位置的迭代子。标记起始插入位实参：容器本身和它的一个指示起始插入位置的迭代子。标记起始插入位置的迭代子并不是保持不变，而是随每个被插入的元素而递增，这样每个置的迭代子并不是保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。元素就能顺序被插入。注意是注意是“插入插入”而不是而不是“改写改写”，back_inserter(Type&)它使用

19、容器的它使用容器的push_back()插入操作代替赋值操作符，将新元素添加到容器插入操作代替赋值操作符，将新元素添加到容器对象的末端。实参是容器本身。返回一个对象的末端。实参是容器本身。返回一个back_inserter迭代子。迭代子。front_inserter(Type&)它使用容器的它使用容器的push_front()插入操作代替赋值操作符，将新元素添加到容器插入操作代替赋值操作符，将新元素添加到容器的前端，同样，新添加的元素以逆序方式结束于被控序列前端的前端，同样，新添加的元素以逆序方式结束于被控序列前端,即最后添加即最后添加的元素放在最前面。实参也是容器本身。返回一个的元素放在最前

20、面。实参也是容器本身。返回一个front_inserter迭代子。迭代子。front_inserter不能用于矢量不能用于矢量vector，因为，因为vector没有成员函数没有成员函数push_front()。整理课件11.3.1 矢量类矢量类流迭代子流迭代子(Stream Iterator)：包括输入流迭代子（包括输入流迭代子（Istream_Iterator）和输出流迭代子）和输出流迭代子（Ostream_Iterator） 输入流迭代子类支持在输入流迭代子类支持在istream、ifstream等输入流类上的迭代子操作。等输入流类上的迭代子操作。istream_iterator声明方式

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

22、二参数为C风格字符串风格字符串【例【例11.3】用用istream_iterator从标准输入读入一个整从标准输入读入一个整数集到数集到vector中。中。 整理课件11.3.2 列表类列表类列表类（列表类（list）的引入：）的引入：是由双向链表组成的。它有两个指针域，可以向前也可以向后是由双向链表组成的。它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。列表类不能使用下标运算符子。列表类不能使用下标运算符。它定义在头文件。它定义在头文件中。中。列表类容器也有多种构造函数，与矢量类形式相同列表类容

23、器也有多种构造函数，与矢量类形式相同。【例【例11.4】展示列表类怎样进行链表操作。展示列表类怎样进行链表操作。在本例中建立了两个已排序好的列表类对象，然后归并。在本例中建立了两个已排序好的列表类对象，然后归并。全部用列表类的成员函数。不能使用泛型算法全部用列表类的成员函数。不能使用泛型算法sort()对无对无序的列表类对象排序，因为序的列表类对象排序，因为sort()要求随机迭代子要求随机迭代子，list仅支持双向迭代子仅支持双向迭代子。整理课件11.3.3 11.3.3 双端队列类双端队列类双端队列（双端队列（Double-Ended Queue）类的引入：）类的引入：双端队列允许在队列的

24、两端进行操作。它以顺序表为基础，所双端队列允许在队列的两端进行操作。它以顺序表为基础，所以能利用下标提供有效的索引访问，它支持随机访问迭代子。以能利用下标提供有效的索引访问，它支持随机访问迭代子。使用双端队列，必须包含头文件使用双端队列，必须包含头文件。双端队列类容器也有多种构造函数，与矢量类或列表类形式相同。双端队列类容器也有多种构造函数，与矢量类或列表类形式相同。【例【例11.5】双端队列类与矢量类一样，有一个成员函数双端队列类与矢量类一样，有一个成员函数insert()，注意不是插入迭代子适配器函数，注意不是插入迭代子适配器函数inserter()。本例演。本例演示该函数的使用，最后输出

25、字符串：示该函数的使用，最后输出字符串：“STL功能强使用方便。功能强使用方便。”deque类重载了多个成员函数类重载了多个成员函数insert()：insert (it,x); /在迭代子在迭代子it指定元素前插入一个值为指定元素前插入一个值为x的元素，返回指向新元素的迭代子的元素，返回指向新元素的迭代子insert (it,n,x); /在迭代子在迭代子it指定元素前插入指定元素前插入n个值为个值为x的元素的元素insert (it,first,last); /在迭代子在迭代子it指定元素前插入由区间指定元素前插入由区间first,last)指定的序列指定的序列整理课件11.4 泛型算法与

26、函数对象泛型算法与函数对象算法表现为一系列的函数模板。它们完整定义在算法表现为一系列的函数模板。它们完整定义在STL头文头文件中。使用者可以用很多方式来件中。使用者可以用很多方式来特化每一个模板函数特化每一个模板函数，大大提，大大提高了它作为通用型程序组件的适用性。这些函数模板使用迭代高了它作为通用型程序组件的适用性。这些函数模板使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操子作为它的参数和返回值，以此在容器（序列）上进行各种操作。本节进一步讨论作。本节进一步讨论算法的通用性算法的通用性。11.4.1 函数对象函数对象 11.4.2 泛型算法泛型算法 整理课件11.4.1 函数

27、对象函数对象函数对象的基本概念：函数对象的基本概念：每个泛型算法（每个泛型算法（Generic Algorithm）的实现都独立于容器类）的实现都独立于容器类型，它消除了算法对类型的依赖性。型，它消除了算法对类型的依赖性。在在STL的泛型算法中采用的泛型算法中采用“函数对象函数对象”（Function Object）来解决该问题。函数对象是一个类，通常它仅有一个成员函数，来解决该问题。函数对象是一个类，通常它仅有一个成员函数，该函数该函数重载了函数调用操作符重载了函数调用操作符（operator()）。该操作符封装）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作了应该被实

28、现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。为实参传递给泛型算法。和和“引用引用”一样，一样，“函数对象函数对象”很少独立使用。函数对象亦称很少独立使用。函数对象亦称拟函数对象（拟函数对象（Function_Like Object）和函子（）和函子（Functor）。）。 整理课件11.4.1 函数对象函数对象【例【例11.6】求和函数对象的定义和测试。求和函数对象的定义和测试。注意函数对象注意函数对象Sum能实例化为有限种类型，如：整型、实型、字符型等等，能实例化为有限种类型，如：整型、实型、字符型等等，也能用于也能用于string类型，因为类型，因为string重载了

29、重载了operator +。函数对象的应用：函数对象的应用：函数对象主要是作为泛型算法的函数对象主要是作为泛型算法的实参实参使用，通常用来改变默认使用，通常用来改变默认的操作，如：的操作，如：sort(vec.begin(),vec.end(),greater();这就是把整数的这就是把整数的大于关系函数对象大于关系函数对象作为实参，得降序排列。如作为实参，得降序排列。如果是字符串，则有：果是字符串，则有：sort(svec.begin(),svec.end(),greater();只要改一下参数就又可用于字符串的排序。只要改一下参数就又可用于字符串的排序。greater中所包含的比较算法实际

30、上在内置类型中所包含的比较算法实际上在内置类型int，字，字符串类符串类string中定义。由此可见函数对象并没有新东西，只是中定义。由此可见函数对象并没有新东西，只是一个固定格式，用起来更方便。一个固定格式，用起来更方便。 整理课件11.4.1 函数对象函数对象例如，自定义整数类例如，自定义整数类Int，其中重载了比较算法，其中重载了比较算法“”运算符：运算符：class Intpublic: Int(int ival=0):_val(ival) int operator-()return -_val; /负数符号重载负数符号重载 int operator%(int ival)return

31、_val%ival; /求余符号重载求余符号重载 bool operator(int ival)return _valival; /大于符号重载大于符号重载 bool operator!()return _val=0; /逻辑非符号重载逻辑非符号重载private: int _val;Int类可以作为类型参数传递给函数对象类可以作为类型参数传递给函数对象greater()，同时把，同时把重载的运算符也传递过去了。重载的运算符也传递过去了。整理课件11.4.1 函数对象函数对象 以函数对象作为求序列中最小值的函数模板的以函数对象作为求序列中最小值的函数模板的“数值数值比较算法比较算法”参数：参数

32、：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; return pminIndex; 例中例中Comp为比较函数对象（类模板），对不同的数据为比较函数对象（类模板），对不同的数据类型，可以产生不同的比较函数，以类型，可以产生不同的比较函数，以实现泛型算法实现泛型算法。使用函数对象实现泛型算法：使用函数对象实现泛型算

33、法：整理课件11.4.1 函数对象函数对象函数对象与函数指针相比较有函数对象与函数指针相比较有三个优点三个优点：第一，函数：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检就是一个额外数据；第三，编译时对

34、函数对象作类型检查。查。函数对象来源：函数对象来源：1. 标准库预定义的一组算术，关系和逻辑函数对象；标准库预定义的一组算术，关系和逻辑函数对象；2. 预定义的一组函数适配器，允许对预定义的函数对象进预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展；行特殊化或扩展；3. 自定义函数对象。自定义函数对象。函数对象的优点：函数对象的优点：整理课件11.4.1 函数对象函数对象预定义函数对象及其使用方法：预定义函数对象及其使用方法：使用时要包含头文件：使用时要包含头文件：#include 算术函数对象：算术函数对象：加法：加法：plus(x,y) /返回返回x+y,可用于可用于stri

35、ng、复数和浮点数等、复数和浮点数等减法：减法：minus(x,y) /返回返回x-y,不能用串不能用串,可用于复数和浮点数等可用于复数和浮点数等乘法：乘法：multiplies(x,y) /返回返回x*y,不能用串不能用串,可用于复数和浮点数等可用于复数和浮点数等除法：除法：divides(x,y) /返回返回x/y,不能用串不能用串,可用于复数和浮点数等可用于复数和浮点数等求余：求余：modulus(x,y) /返回返回x%y,只能用于整数只能用于整数取反：取反：negate(x) /返回返回-x,补码补码,只能用于整数只能用于整数整理课件11.4.1 函数对象函数对象逻辑函数对象：逻辑函

36、数对象：这里这里Type必须支持逻辑运算，有两个参数。必须支持逻辑运算，有两个参数。逻辑与：逻辑与：logical_and(x,y) /对应对应“&”逻辑或：逻辑或：logical_or(x,y) /对应对应“|”逻辑非：逻辑非：logical_not(x) /对应对应“!”关系函数对象：关系函数对象：它们的返回值为布尔量，两个参数，第一参数和第二参数相比：它们的返回值为布尔量，两个参数，第一参数和第二参数相比：等于：等于：equal_to(x,y) /对应对应x=y不等于：不等于：not_equal_to(x,y) /对应对应x!=y大于：大于：great(x,y) /对应对应xy大于等于：

37、大于等于：great_equal(x,y) /对应对应x=y小于：小于：less(x,y) /对应对应xy小于等于：小于等于：less_equal(x,y) /对应对应x=y整理课件11.4.1 函数对象函数对象返回布尔值的函数对象称为返回布尔值的函数对象称为谓词谓词（predicate），默认的二进），默认的二进制制谓词谓词是小于比较操作符是小于比较操作符“”，所以默认的排序方式都是升，所以默认的排序方式都是升序排列，它采用小于比较形式。序排列，它采用小于比较形式。函数适配器特化或扩展一元或二元函数对象：函数适配器特化或扩展一元或二元函数对象：绑定器（绑定器（Binder）：）：把二元函数对

38、象中的一个参数固定（绑定），使之转为一元函把二元函数对象中的一个参数固定（绑定），使之转为一元函数，数，C+标准库提供两种预定义的标准库提供两种预定义的binder适配器：适配器：bind1st和和bind2nd，分别绑定了第一或第二个参数。格式：，分别绑定了第一或第二个参数。格式：bind2st(plus(x),3.0) 取反器（取反器（Negator）：）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。成了大于。C+标准库也提供了两种标准库也提供了两种negator适配器：适配器：not1和和not2。not1用于一元

39、预定义函数对象；用于一元预定义函数对象；not2用于二元预用于二元预定义函数对象。格式同绑定器。定义函数对象。格式同绑定器。整理课件11.4.2 泛型算法泛型算法范型算法分类为：范型算法分类为：(1)修改容器的算法修改容器的算法，即，即变化序列算法变化序列算法（mutating-sequence algorithm），如），如copy()、remove()、replace()、swap()等；等；(2)不修改容器的算法不修改容器的算法，即，即非变化序列算法非变化序列算法（non-mutating-sequence algorithm），如），如count()、find()等；以及等；以及数字型

40、算法数字型算法。*在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足指定二进制指定二进制谓词谓词规则的元素，因为谓词是返回布尔值的函数对象，规则的元素，因为谓词是返回布尔值的函数对象，满足则返回满足则返回true，即与满足指定条件是同样意思。，即与满足指定条件是同样意思。 泛型算法函数名后缀：泛型算法函数名后缀：_if表示函数采用的操作是在元素上，而不是对元素的值表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如本身进行操作。如find_if算法表示查找一些值满足函数指定算法表示查找一些值满足函数指定条件的元素，而条

41、件的元素，而find查找特定的值。查找特定的值。_copy表示算法不仅操作元素的值，而且还把修改的值表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。复制到一个目标范围中。reverser算法颠倒范围中元素的排算法颠倒范围中元素的排列顺序，而列顺序，而reverse_copy算法同时把结果复制到目标范围中。算法同时把结果复制到目标范围中。其它的后缀从英文意思上立即可以认出其意义。其它的后缀从英文意思上立即可以认出其意义。整理课件11.4.2 泛型算法泛型算法泛型算法的构造与使用方法泛型算法的构造与使用方法: :所有泛型算法的前两个实参是一对所有泛型算法的前两个实参是一对itera

42、tor，通常称为，通常称为first和和last，它们标出要操作的容器或内置数组中的元素范围。元素，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括的范围，包括first，但不包含，但不包含last的左闭合区间。即：的左闭合区间。即：first,last)当当first=last成立，则范围为空。成立，则范围为空。对对iterator的属性，则要求在每个算法声明中指出，的属性，则要求在每个算法声明中指出，所声明的所声明的是最低要求是最低要求。如如find()最低要求为：最低要求为：InputIterator，可以传递，可以传递更高级别的迭代子。如：更高级别的迭代子。如：Forwar

43、dIterator、BidirectonalIterator及及RandomAccessInterator。但不能用。但不能用OutputInterator。 整理课件11.4.2 泛型算法泛型算法泛型算法分类：泛型算法分类：1查找算法查找算法：有：有13种查找算法用各种策略去判断容器中是否种查找算法用各种策略去判断容器中是否存在一个指定值。存在一个指定值。equal_range()、lower_bound()和和upper_bound()提供对半查找形式。提供对半查找形式。2排序和通用整序算法排序和通用整序算法：共有：共有14种排序（种排序（sorting）和通用整）和通用整序（序（orde

44、ring）算法，为容器中元素的排序提供各种处理方法。）算法，为容器中元素的排序提供各种处理方法。所谓整序，是按一定规律分类，如分割（所谓整序，是按一定规律分类，如分割（partition）算法把容）算法把容器分为两组，一组由满足某条件的元素组成，另一组由不满足器分为两组，一组由满足某条件的元素组成，另一组由不满足某条件的元素组成。某条件的元素组成。3删除和代替算法删除和代替算法：有：有15种删除和代替算法。种删除和代替算法。4排列组合算法排列组合算法：有：有2种算法。排列组合是指全排列。如：三种算法。排列组合是指全排列。如：三个字符个字符a，b，c组成的序列有组成的序列有6种可能的全排列：种可

45、能的全排列：abc，acb，bac，bca，cab，cba；并且六种全排列按以上顺序排列，认；并且六种全排列按以上顺序排列，认为为abc最小，最小，cba最大，因为最大，因为abc是全顺序（从小到大）而是全顺序（从小到大）而cba是全逆序（从大到小）。是全逆序（从大到小）。 整理课件11.4.2 泛型算法泛型算法5生成和改变算法生成和改变算法：有：有6种，包含生成（种，包含生成（generate），填充（），填充（fill）等）等等。等。6关系算法关系算法：有：有7种关系算法，为比较两个容器提供了各种策略，包括种关系算法，为比较两个容器提供了各种策略，包括相等（相等（equal()），最大（）

46、，最大（max()），最小（），最小（min()）等等。）等等。 7集合算法集合算法：4种集合（种集合（set）算法提供了对任何容器类型的通用集合）算法提供了对任何容器类型的通用集合操作。包括并（操作。包括并（union），交（），交（intersection），差（），差（difference）和）和对称差（对称差（symmetric difference）。）。 8. 堆算法堆算法：有：有4种堆算法。堆是以数组来表示二叉树的一种形式。标准种堆算法。堆是以数组来表示二叉树的一种形式。标准库提供大根堆（库提供大根堆（max_heap），它的每个结点的关键字大于其子结点的），它的每个结点的关键字

47、大于其子结点的关键字。关键字。9. 算术算法算术算法：该类算法有：该类算法有4种，使用时要求包含头文件种，使用时要求包含头文件。整理课件11.5 关联容器关联容器关联容器关联容器( (associative container)的引入：的引入：它们能通过关键字（它们能通过关键字（search key）直接访问）直接访问(存储和读取元素存储和读取元素)。四个关联容器为：集合（四个关联容器为：集合（set），多重集合（），多重集合（multiset），映），映射（射（map）和多重映射（）和多重映射（multimap）。）。11.5.1 集合和多重集合类集合和多重集合类11.5.2 映射和多重映射

48、类映射和多重映射类整理课件11.5.1 集合和多重集合类集合和多重集合类集合和多重集合类引入：集合和多重集合类引入：它们提供了控制数值集合的操作，其中数值是关键字，即不必另有它们提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。集合与多重集合类的主要差别在于多一组值与每个关键字相关联。集合与多重集合类的主要差别在于多重集合允许重复的关键字，而集合不允许重复的关键字。重集合允许重复的关键字，而集合不允许重复的关键字。 集合和多重集合类提供了控制数值集合的操作，其中数集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。值是关

49、键字，即不必另有一组值与每个关键字相关联。 多重集合允许重复的关键字（多重集合允许重复的关键字（key），而集合不允许。），而集合不允许。 元素的顺序由元素的顺序由比较器函数对象比较器函数对象（comparator function object）确定。如对整型）确定。如对整型multiset，只要用比较器函数对象，只要用比较器函数对象less排序关键字，元素即可按升序排列。排序关键字，元素即可按升序排列。set类模板声明为：类模板声明为：templatetypename Key, typename Pred = less, typename A = allocator class set;

50、/模板参数表中的非类型参数同样可有默认值模板参数表中的非类型参数同样可有默认值整理课件11.5.1 集合和多重集合类集合和多重集合类set容器的构造函数：容器的构造函数：set (); /构造一个空的按默认次序排列的集合构造一个空的按默认次序排列的集合set (pr); /构造一个空的按函数对象构造一个空的按函数对象pr排序的集合排序的集合set (first,last); /构造一个默认次序排列的集合，构造一个默认次序排列的集合， /元素值由区间元素值由区间first,last)指定的序列复制指定的序列复制set (first,last,pr); /同上，但按函数对象同上，但按函数对象pr排

51、序排序这些构造函数还可以显式给出分配子这些构造函数还可以显式给出分配子(Allocator)对象。对象。集合和多重集合类支持双向迭代子。集合和多重集合类支持双向迭代子。 multiset和和set通常实现为通常实现为红黑二叉排序树。红黑二叉排序树。红黑二叉排序树红黑二叉排序树是实现平衡二叉排序树的方法之一。是实现平衡二叉排序树的方法之一。 【例【例11.7】整型多重集合关联容器类整型多重集合关联容器类整理课件11.5.2 映射和多重映射类映射和多重映射类映射和多重映射类引入：映射和多重映射类引入： 它们提供了操作与关键字相关联的映射值（它们提供了操作与关键字相关联的映射值（mapped val

52、ue）的方法。映射和多重映射的主要差别在于多重映射允）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存储和读取关键字多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字与相关值（关键字/数值对，数值对，key/value pair）。如果保存学生）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓

53、名排序，因姓名可能重复，使用多重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件重映射更为合适。使用时要用头文件。 整理课件11.5.2 映射和多重映射类映射和多重映射类mapmap类模板声明：类模板声明：templatetypename Key,typename T,typename Pred = less, typename A = allocatorpair class map; map容器有多种容器有多种构造函数构造函数：map (); /构造一个空的按默认次序排列的映射构造一个空的按默认次序排列的映射map (pr); /构造一个空的按函数对象构造

54、一个空的按函数对象pr排序的映射排序的映射map (first,last); /构造按默认次序排列的映射，构造按默认次序排列的映射， /元素值由区间元素值由区间first,last)指定的有序序列复制指定的有序序列复制map (first,last,pr); /同上，但按函数对象同上，但按函数对象pr排序排序这些构造函数还可以显式给出分配子这些构造函数还可以显式给出分配子(allocator)对象。对象。整理课件11.5.2 映射和多重映射类映射和多重映射类映射的使用：映射的使用：映射和多重映射类映射和多重映射类支持双向迭代子支持双向迭代子。映射定义了成员操作符映射定义了成员操作符：T& op

55、eratorconst Key& key这样映射的使用是非常方便的，就如同一个数组，关键字作为这样映射的使用是非常方便的，就如同一个数组，关键字作为下标，相关值作为元素值。下标，相关值作为元素值。【例【例11.8】我国部分省份与面积映射关联容器类的演示。我国部分省份与面积映射关联容器类的演示。 整理课件11.6 容器适配器容器适配器容器适配器容器适配器（container adapter）：栈，队列和优先级队。所谓适配器并不独立，它依附在一个栈，队列和优先级队。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，声明顺序容器上。如要声明一个用矢量实现的字符型堆栈，声

56、明如下：如下： stackvector sk;然后它可以象顺序容器一样使用。但它没有自己的构造和析然后它可以象顺序容器一样使用。但它没有自己的构造和析构函数，它使用其实现类（如构函数，它使用其实现类（如vector）的构造和析构函数。）的构造和析构函数。队列（队列（queue）默认用）默认用deque为基础，栈（为基础，栈（stack）可用）可用vector或或deque为基础。为基础。11.5.1 栈类栈类 11.5.2 队列类队列类11.5.3 优先级队列类优先级队列类整理课件 栈类栈类 栈并不独立，它依附在一个顺序容器上。栈并不独立，它依附在一个顺序容器上。栈（栈（stack）可用可用v

57、ector或或deque为基础。为基础。声明一个用矢量实现的字符型堆栈，格式如下：声明一个用矢量实现的字符型堆栈，格式如下： stackvector sk;【例【例11.9】演示堆栈的压入和弹出。演示堆栈的压入和弹出。栈类的引入：栈类的引入：整理课件11.5.2 队列类队列类队列（队列（queue）：）： 默认以默认以deque为基础为基础【例【例11.10】演示队列的入队和出队。演示队列的入队和出队。整理课件11.5.3 优先级队列类优先级队列类优先级队列（优先级队列（priority_queue）适配器：）适配器：用以实现优先级队列。元素插入是自动按优先级顺序插入，使用以实现优先级队列。元

58、素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。常用矢量为基础容最高优先级元素首先从优先级队列中取出。常用矢量为基础容器。默认时器。默认时priority_queue用用vector为基础数据结构。为基础数据结构。 【例【例11.11】 优先级队列类演示，头文件用优先级队列类演示，头文件用，优先级用数表示，数值越大优先级越高。，优先级用数表示，数值越大优先级越高。整理课件第十一章第十一章 标准模板库（标准模板库（选读选读）课程全部结束课程全部结束祝同学们有一个好成绩！祝同学们有一个好成绩！整理课件表表11.1 标准库容器类标准库容器类标准库容器类标准库容器类说明说明顺序容

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

60、射，基于关键字快速查找，不允许重复值一对多映射，基于关键字快速查找，允许重复值一对多映射，基于关键字快速查找，允许重复值容器适配器容器适配器stack（栈）（栈）queue（队列）（队列）priority_queue（优先级队列）（优先级队列）后进先出（后进先出（LIFO）先进先出（先进先出（FIFO）最高优先级元素总是第一个出列最高优先级元素总是第一个出列整理课件表表11.2 所有标准库容器共有的函数（所有标准库容器共有的函数（1）提供容器默认初始化的构造函数。通常每个容提供容器默认初始化的构造函数。通常每个容器都有几个不同的构造函数，提供容器不同器都有几个不同的构造函数，提供容器不同的初始