C++ 第十一章课件.ppt

1、第11章标准模板库(STL)，一个库是程序组件的集合，可以在不同的程序中重用。图书馆功能设计的首要要求是通用性，而模板为通用性带来了不可估量的前景。标准模板库是ANSI/ISO C最具特色和实用性的部分之一，STL包含：容器、迭代器算法、通用算法和函数对象，使算法摆脱了对不同类型数据操作的依赖。11.1标准模板库简介，11.3序列容器，11.2迭代子类，11.5容器适配器，11.7 VC中的STL，11.6通用算法和函数对象，11.4关联容器，XI标准模板库章，11.1标准模板库简介，容器类是一个管理序列并保存一组对象或一组对象的类。通过容器类提供的成员函数，可以执行向序列中插入元素、删除元素

2、、查找元素等操作。这些成员函数通过返回迭代器来指定元素在序列中的位置。STL提供了一个标准化的模板化对象容器库，其中包含了各种数据结构及其算法：迭代器是面向对象的版本指针，它提供访问容器或序列中每个对象的方法。这样，该算法可以应用于由容器管理的序列。通用算法不依赖于特定的容器，通用算法更容易扩展。通用算法使用函数对象来介绍同一算法在不同环境下的差异。它不使用继承和多态，避免了虚拟函数的开销，使STL更加高效。11.1标准模板库简介，容器分为三类：表11.1，11.1标准模板库简介，顺序容器和关联容器称为一级容器。还有四种容器被称为近容器：c语言风格的数组、字符串、用于操作1/0标志值的位集和用

3、于高速数学矢量运算的valarray。尽管它们提供了与第一类容器相似的功能，但它们并不具备所有的功能。STL还使容器能够提供类似的接口。许多基本操作适用于所有容器，而一些操作适用于相似容器的子集。这样，STL可以用新的类来扩展。这些函数和操作符可以被称为容器的接口。表11.2所有标准库容器共有的函数，表11.3仅在第一类中的函数，表11.4标准容器库的头文件，和11.1标准模板库的介绍。在讨论线性表和非线性表(如数组、链表和二叉树)时，如果想访问其中一个元素(节点)，访问方法最终应该归结为获取内存地址(指针)，它可以抽象为面向对象版本的指针迭代器(指针)。迭代器和指针有很多相似之处，但是迭代器

4、保存了特定容器操作所需的状态信息，从而实现了适合每种容器类型的迭代器。一些迭代器操作在所有容器中都是一致的。例如，运算符总是返回容器的下一个元素的迭代器，间接引用符号*总是指示迭代器指向的容器元素。迭代器用于组合STL的所有部分。本质上，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代器来实例化这些模板。迭代器可以包含指针，但不仅仅是指针。11.1标准模板库简介，STL的最大优势是在各种容器中提供通用算法，如插入、删除、搜索、排序等。STL提供了大约70种标准算法。该算法仅通过迭代间接操作容器元素。算法通常返回迭代器。一个算法通常可以用于许多不同的容器，所以它被称为通用算法。算法分

5、为：容器修改算法，即变异序列算法，如复制()、删除()、替换()、交换()等。不修改容器的算法，即非变异序列算法，如count()、find()等。数字算法。、11.2迭代子类，标准库定义了迭代器的层次结构，根据这个层次，从上到下，函数越来越强大。但不是遗产！图11.1迭代子级，标准库中有五个预定义的迭代器，最强大和灵活的是随机访问迭代器。表11.5迭代子类别，表11.6 STL容器支持的迭代子类别，表11.7可由各种迭代器执行的操作，迭代器只能遍历第一类容器。结合find()算法，讨论了迭代器与遗传算法的关系。find()的定义如下：模板输入迭代器find(首先输入迭代器，最后输入迭代器，计

6、数t值)为(；首先！=最后一个。first)如果(值=*first)先返回；Return last表明通用算法不直接访问容器的元素，与容器无关。元素的所有访问和遍历都是通过迭代器实现的。没有必要预测容器类型。11.2迭代子类，示例11.1查找数组元素。示例11.2查找向量容器元素。11.2迭代子类，特殊迭代器：反向迭代器将一切颠倒过来。当向前遍历第一个类容器时，如果使用反向迭代器，实际上实现了反向遍历。第一种容器支持两对操作：begin()和end()，它们分别返回指向容器的第一个元素和最后一个元素的后续迭代器；而rbegin()和rend()支持逆变换迭代器，并返回分别指向容器的最后一个元素

7、和第一个元素的前导元素的迭代器。向量向量。vector : reverse _ iterator r _ ITER；for(r _ ITER=veco . rbe gin()；/将r_iter指向最后一个元素r_iter！=veco . rend()；/它不等于第一个元素的前导ITER。/实际上正在减少。如果你想把升序改为降序，只需使用逆迭代器。逆迭代器被定义为随机迭代器。11.2迭代子类、插入迭代器：您可以使用输出迭代器来生成元素序列。您可以添加元素而不覆盖它们。有三种类型的插入迭代器：back_insert_iterator是输出迭代器，用于将生成的元素添加到类型为的容器对象的末尾。这就像

8、在字符串的末尾添加一个字符串(strcat()。front_insert_iterator是一个输出迭代器，用于将生成的元素添加到容器的前端，也就是说，生成的元素以相反的顺序在受控序列的前端结束。Insert_iterator也是一个输出迭代器，用于将生成的元素插入到迭代器(第二个参数迭代器)指定的元素之前。相关适配器函数，11.2迭代子类，流迭代器：输入流迭代器(istream_iterator)类支持对istream及其派生类(如ifstream)的迭代子操作。声明方式为：istream_iterator迭代子标识符(istream /Type为已定义输入操作的类型，/实际参数可以是公共派

9、生istream的任何子类型对象，输出流也由相应的ostream_iterator类支持，声明方式为：ostream_iterator迭代子标识符(ostream /定义用于存储整形序列的向量容器对象vi，/vector vch，用于存储实序列的向量容器)；/vectorvstr，用于存储字符序列的向量容器；/用于存储字符串序列的向量容器。向量容器有多种构造函数，包括用n个元素构造一个向量。您也可以为具有相同对象的每个元素分配一个初始值。它还包括一个复制构造函数，可以从现有的向量容器对象中初始化新容器的每个元素的构造函数。这些构造函数也可以显式地给分配器对象。11.3顺序容器，2 .列表由双链

10、表组成。它有两个指针字段，支持的迭代子类型是双向迭代器。它类似于双链表模板，但它更通用和方便使用。列表在头文件中定义。3。deque(双端队列)类。Deque允许在队列的两端进行操作。基于序列表，支持随机访问迭代器。德克尔放松了对他访问的限制，目标可以从队伍的头，从队伍的末端，或从任何一端进入队伍。支持下标运算符“”。增加存储空间可以在内存块中分配出队列的两端。新分配的内存空间被保存为指向这些块的指针数组，并且可以利用不连续的内存空间。因此，它的迭代器比向量的更智能。当de quee被删除时，为de quee分配的存储块被释放。要使用deque，必须包含一个头文件。11.4关联容器、关联容器可

11、以通过搜索键直接访问(存储和读取元素)。四个相关的容器是：集合、多集合、映射和多映射。集合和多个集合类提供了控制数值集合的操作，其中数值是关键字，也就是说，不需要将另一组值与每个关键字相关联。多个集合允许重复的键，而集合不允许。元素的顺序由比较器函数对象决定。对于整数多集，只要使用比较器函数对象less来排序关键字，元素就可以按升序排列。多集和集合通常被实现为红色和黑色的二进制排序树。红黑二进制排序树是实现平衡二进制排序树的方法之一。示例11.4整数多集合关联容器类、11.4关联容器、映射和多映射类提供了操作与关键字关联的映射值的方法。映射和多重映射的主要区别在于多重映射允许存储与映射值相关联

12、的重复关键字，而映射只允许逐个存储对应于映射值的单个关键字。多个映射和映射关联容器类用于快速存储和读取关键字和相关值(键/值对)。如果保存了学生的简明信息，则需要按学生编号进行排序，最合适的是使用映射关联容器(因为它不会重复编号)。如果按名称排序，因为名称可能重复，所以使用多个映射更合适。使用时使用头文件。11.5容器适配器，STL提供了三个容器适配器：堆栈、队列和优先级队列。所谓的适配器不是独立的，它连接到一个顺序容器。如果你想声明一个由向量实现的字符堆栈，声明如下：堆栈sk；优先级队列(priority_queue)适配器实现优先级队列。元素插入是按优先级顺序自动插入的，因此优先级最高的元

13、素首先从优先级队列中取出。通常使用基于向量的容器。默认情况下，priority_queue的数据结构基于向量。然后它可以像顺序容器一样使用。但是它没有自己的构造函数和析构函数。它用它来实现类的构造函数和析构函数(比如向量)。默认情况下，队列基于de quee，堆栈可以基于vector或de quee。示例11.5优先级队列类演示，11.6通用算法和函数对象，算法表示为一系列函数模板。它们完全在STL头文件中定义。用户可以以多种方式专门化每个模板函数，这极大地提高了它作为通用程序组件的适用性。这些函数模板使用迭代器作为它们的参数和返回值来对容器(序列)执行各种操作。本节进一步讨论算法的一般性。1

14、1.6.1功能对象、11.6.2通用算法、11.6.1功能对象。在C语言中，为了使程序更安全，使用“引用”代替指针作为函数的参数或返回值。在C语言的通用算法中，“函数对象”被类似地用来代替函数指针。函数对象是重载函数调用运算符(运算符()的类。这个运算符封装了应该作为函数实现的操作。通常，函数对象作为参数传递给通用算法。像“引用”一样，“功能对象”很少单独使用。函数对象也称为类函数对象和函子。为了消除算法的类型依赖性，可以使用函数指针作为参数，类似于第6.8节附录中库函数快速排序的处理方法。这种方法更适合于函数模板。11.6.1函数对象、示例11.6求和函数对象的定义和测试。函数对象作为求“数

15、值比较算法”序列中最小值的函数模板：模板常量类型示例中的Comp是比较函数对象类，不同的数据类型可以定义不同的函数对象。重载()，参数表可以有任意数量的参数。11.6.1与函数指针相比，函数对象有三个优点：第一，函数指针是间接引用，不能用作内联函数，而函数对象可以，这更快；第二，函数对象可以有任意数量的额外数据，可以用来缓冲当前数据和结果，提高操作质量。当然，在大多数情况下不一定使用它。在上例中，res是一个额外的数据；第三，在编译时检查函数对象的类型。函数对象1有许多来源。由标准库预定义的一组算术、关系和逻辑函数对象；2.一组预定义的函数适配器，允许预定义函数对象的专门化或扩展；3.自定义函数对象。11.6.1功能对象，预定义的功能对象分为算术、关系和逻辑运算。每个对象都是一个类模板，操作数类型作为模板参数。使用时，应包含头文件：#包含以加法为例，讨论名为加号的类模板，并使用如下整数：加号添加；int ival1=30，ival2=15int sum=intAdd(ival1，ival 2)；/相当于：sum=ival1invar2，但函数对象主要用作泛型算法的参数，通常用于更改默认操作。例如，在示例11.3中，有：开始()，vec。结束()、更大()；也就是说，将整数的大于关系函数对象作