C++程序设计教学课件(第7章)

第第7章章 标准模板库标准模板库STL介绍及应用介绍及应用n7.1 标准模板库标准模板库STL的概念的概念 n7.2 命名空间命名空间 n7.3 容器（容器（Container）n7.4 迭代器（迭代器（Iterator）n7.5 算法（算法（Algorithm）n7.6 综合应用实例综合应用实例 5/4/202417.1 标准模板库标准模板库STL的概念的概念 nSTL最初是由惠普实验室开发的一系列组件，是标准最初是由惠普实验室开发的一系列组件，是标准C+库的重要补充之一。库的重要补充之一。n从逻辑层次来看，从逻辑层次来看，STL体现了泛型程序设计的思想，体现了泛型程序设计的思想，引入了多个新的名词，比如容器、算法、迭代器等。引入了多个新的名词，比如容器、算法、迭代器等。n在在STL中，几乎所有的代码都采用了类模板和函数模中，几乎所有的代码都采用了类模板和函数模板的方式，因而，提供了更好的代码重用机会。板的方式，因而，提供了更好的代码重用机会。n从广义上讲，从广义上讲，STL的代码分为三类：容器、迭代器和的代码分为三类：容器、迭代器和算法。这算法。这3类代码被组织为类代码被组织为13个头文件。个头文件。5/4/202427.1.2 STL和和C+标准的关系标准的关系输入输入/输出输出数值数值诊断诊断通用工具通用工具国际化国际化语言支持语言支持容器容器算法算法迭代器迭代器字符串字符串STLC+标准库标准库C标标准准函函数数STL和和C+标准库的关系标准库的关系5/4/202437.1.3 STL组成部分组成部分函数对象函数对象通用算法通用算法assistSTL容器容器迭代器迭代器supportsapply toaccessuseuse STL结构图结构图5/4/202447.1.3 STL组成部分组成部分n1容器容器 能够保存其它类型的对象的类。能够保存其它类型的对象的类。C+的容器可以包含混的容器可以包含混合类型的对象，也就是说容器类可以包含一组相同类型合类型的对象，也就是说容器类可以包含一组相同类型或一组不同类型的对象。当容器类包含相同类型的对象或一组不同类型的对象。当容器类包含相同类型的对象时，称为同类容器类；当容器类包含不同类型的对象时，时，称为同类容器类；当容器类包含不同类型的对象时，称为异类容器类。称为异类容器类。n2迭代器迭代器 迭代器从作用上来说是迭代器从作用上来说是STL最基本的部分，但理解起来最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。迭代序员以相同的方式处理不同的数据结构（容器）。迭代器是算法访问容器的中介。器是算法访问容器的中介。5/4/202457.1.3 STL组成部分组成部分n3算法算法 一个按照一组定义明确的步骤来解决某个问题的处理一个按照一组定义明确的步骤来解决某个问题的处理过程，理论上，它不依赖于任何特定的计算机编程语过程，理论上，它不依赖于任何特定的计算机编程语言。言。STL提供了大约提供了大约70个实现算法的函数模板。个实现算法的函数模板。n4函数对象函数对象 所谓函数对象是定义了函数调用操作符的对象。在使所谓函数对象是定义了函数调用操作符的对象。在使用用STL时，经常需要把函数对象作为算法的输入参数时，经常需要把函数对象作为算法的输入参数或实例化一个容器或实例化一个容器(container)时的输入参数。时的输入参数。5/4/202467.1.4 STL对对C+的影响的影响n在在STL之前，之前，C+支持三种基本的编程样式支持三种基本的编程样式面向过面向过程编程、数据抽象和面向对象编程。程编程、数据抽象和面向对象编程。n在在STL出现之后，出现之后，C+可以支持一种新的编程模式可以支持一种新的编程模式泛型程序设计。泛型程序设计。nSTL并不完美，但是，它开辟了程序设计的新天地，并不完美，但是，它开辟了程序设计的新天地，它拥有的影响力甚至于超过了巨大的它拥有的影响力甚至于超过了巨大的C+群体。群体。5/4/202477.2 命名空间命名空间 n在实际开发过程中，经常需要引入对象、函数、类、在实际开发过程中，经常需要引入对象、函数、类、类型或其它的全局实体。在同一个项目中，即使不在类型或其它的全局实体。在同一个项目中，即使不在同一个文件中定义或声明，这些全局实体也必须有一同一个文件中定义或声明，这些全局实体也必须有一个唯一的名字。个唯一的名字。n这也意味着当程序员使用开发商提供的库时必须保证这也意味着当程序员使用开发商提供的库时必须保证程序中的全局实体不和开发商提供的库中的全局实体程序中的全局实体不和开发商提供的库中的全局实体名字冲突，这将是一件非常枯燥和困难的事情。名字冲突，这将是一件非常枯燥和困难的事情。n为了解决名字冲突的问题，为了解决名字冲突的问题，C+引入命名空间机制。引入命名空间机制。5/4/202487.2.1 命名空间的定义命名空间的定义定义命名空间的语法格式如下：定义命名空间的语法格式如下：namespace 命名空间名命名空间名 声明序列声明序列 其中，其中，namespace是关键字，后面是命名空间名。是关键字，后面是命名空间名。命名空间名必须在它被定义的作用域中具有唯一的名命名空间名必须在它被定义的作用域中具有唯一的名字，否则会产生错误。在命名空间名后一对花括号字，否则会产生错误。在命名空间名后一对花括号“”括起来的是声明序列。所有可以出现在全局作用括起来的是声明序列。所有可以出现在全局作用域的定义或声明都可以放在其中。域的定义或声明都可以放在其中。5/4/202497.2.1 命名空间的定义命名空间的定义n命名空间定义的例子命名空间定义的例子nnamespace myNameSpace n string myStr=myStr;n class myClassn public:n myClass();n /类的其它部分类的其它部分n ;n void myFunc()n int myCount=0;n extern exFun();n /其它实体定义或声明其它实体定义或声明n5/4/2024107.2.1 命名空间的定义命名空间的定义 定义或使用命名空间需要注意下面几个方面：定义或使用命名空间需要注意下面几个方面：n（1）namespace只能在全局范畴定义，但它们之间只能在全局范畴定义，但它们之间可以互相嵌套，即在命名空间定义内容定义一个新的可以互相嵌套，即在命名空间定义内容定义一个新的命名空间。命名空间。n（2）在）在namespace定义的结尾，大括号的后面不必定义的结尾，大括号的后面不必要跟一个分号。要跟一个分号。n（3）一个）一个namespace可以在多个头文件中用一个标可以在多个头文件中用一个标识符来定义。识符来定义。n（4）一个）一个namespace的名字可以用另一个名字做它的名字可以用另一个名字做它的别名。的别名。5/4/202411n（5）不能像类那样去创建一个命名空间的实例。）不能像类那样去创建一个命名空间的实例。n（6）可以通过多次声明和定义同一命名空间，把新的）可以通过多次声明和定义同一命名空间，把新的成员名称加入到已有的命名空间之中去。成员名称加入到已有的命名空间之中去。7.2.1 命名空间的定义命名空间的定义5/4/2024127.2.2 命名空间的使用命名空间的使用 n对命名空间中成员的引用，需要使用命名空间的域操对命名空间中成员的引用，需要使用命名空间的域操作符作符:。n【例【例7.1】使用命名空间的例子。】使用命名空间的例子。n#include n#include nusing namespace std;n/两个在不同命名空间中定义的名字相同的变量两个在不同命名空间中定义的名字相同的变量nnamespace mySpace1/自定义命名空间自定义命名空间n string myStr=myStr1;n nnamespace mySpace2 n string myStr=myStr2;n5/4/2024137.2.2 命名空间的使用命名空间的使用nvoid main()n n/用命名空间域操作符用命名空间域操作符mySpace1:访问变量访问变量myStrn coutHello,mySpace1:myStr.goodbye!endl;n/用命名空间域操作符用命名空间域操作符mySpace2:访问变量访问变量myStrn coutHello,mySpace2:myStr.goodbye!endl;nn程序运行结果为：程序运行结果为：nHello,myStr1.goodbye!nHello,myStr2.goodbye!5/4/202414n为了避免麻烦，可以使用为了避免麻烦，可以使用C+的的using编译指令来简编译指令来简化对命名空间中的名称的使用。语法格式为：化对命名空间中的名称的使用。语法格式为：using namespace 命名空间名命名空间名:命名空间名命名空间名;中括号中的可选部分是指定命名空间中嵌套的子命名中括号中的可选部分是指定命名空间中嵌套的子命名空间时使用的。有了空间时使用的。有了using指令后，在编写程序时就可指令后，在编写程序时就可以使用以使用using指令，而不用每次都使用指令，而不用每次都使用“命名空间名命名空间名:”来限定要访问的实体。来限定要访问的实体。n【例【例7.2】用】用using指令使用命名空间的例子。指令使用命名空间的例子。n#include n#include n using namespace std;7.2.2 命名空间的使用命名空间的使用5/4/202415nnamespace myNameSpace1n string myStr1=myStr1;n /嵌套定义命名空间嵌套定义命名空间myNameSpace2n namespace myNameSpace2n string myStr2=myStr2;n n n/using指令使用命名空间指令使用命名空间myNameSpace1nusing namespace myNameSpace1;n/using指令使用子命名空间指令使用子命名空间myNameSpace2nusing namespace myNameSpace1:myNameSpace2;nvoid main()n n coutHello,myStr1.goodbye!endl;5/4/202416n coutHello,myStr2.goodbye!endl;nn程序运行结果为：程序运行结果为：nHello,myStr1.goodbye!nHello,myStr2.goodbye!n使用了使用了using指令后，访问指令后，访问myStr1不需要用不需要用myNameSpace1:myStr1，访问访问，访问访问myStr2也不需也不需要用要用myNameSpace1:myNameSpace2:myStr1，而直接使用而直接使用myStr1和和myStr2。7.2.2 命名空间的使用命名空间的使用5/4/2024177.2.3 无名空间无名空间 有时，定义的全局实体只在程序的一小段代码中使用，有时，定义的全局实体只在程序的一小段代码中使用，而在其它地方不会使用。为了保证这些全局实体不和而在其它地方不会使用。为了保证这些全局实体不和项目其它地方的全局实体冲突，可以使用无名空间。项目其它地方的全局实体冲突，可以使用无名空间。无名空间声明的语法格式如下：无名空间声明的语法格式如下：namespace 声明序列声明序列 namespace后不跟命名空间名字，直接用一对后不跟命名空间名字，直接用一对“”括住声明序列，就定义了一个无名空间。括住声明序列，就定义了一个无名空间。5/4/2024187.2.3 无名空间无名空间 【例【例7.3】使用无名空间的例子。】使用无名空间的例子。n#include n#include nusing namespace std;nnamespace n void func1()cout调用了调用了func1()endl;n void func2()cout调用了调用了func2()endl;n nvoid main()n n cout测试无名空间的例子测试无名空间的例子!endl;5/4/202419n func1();/无名空间中定义的函数无名空间中定义的函数n func2();/无名空间中定义的函数无名空间中定义的函数n 程序运行结果为：程序运行结果为：测试无名空间的例子测试无名空间的例子!调用了调用了func1()调用了调用了func2()无名空间只在定义它的文件中有效，在其它文件中都无名空间只在定义它的文件中有效，在其它文件中都不可见。不可见。7.2.3 无名空间无名空间5/4/202420n标标准准C+库库中中的的所所有有组组件件都都定定义义在在一一个个称称为为std 的的命命名空间中，因此，名空间中，因此，std又称为标准命名空间。又称为标准命名空间。n在在编编写写程程序序时时，如如果果需需要要使使用用标标准准C+的的组组件件，在在包包含含相相应应的的标标准准C+头头文文件件后后，可可以以采采用用下下面面几几种种方方法法使用头文件中声明的函数对象、类模板等。使用头文件中声明的函数对象、类模板等。n（1）使用域操作符）使用域操作符std:n（2）使用编译指令）使用编译指令using namespace std;n（3）使使用用编编译译指指令令using namespace std:进进行行更更具体的限制，如具体的限制，如using namespace std:string。7.2.3 标准命名空间标准命名空间std5/4/2024217.3 容器（容器（Container）7.3.1 容器简介容器简介 n容器是能够保存其它类型的对象的类。容器是能够保存其它类型的对象的类。nC+的容器可以包含混合类型的对象，也就是说容器的容器可以包含混合类型的对象，也就是说容器类可以包含一组相同类型或一组不同类型的对象。类可以包含一组相同类型或一组不同类型的对象。n容器类包含相同类型的对象时，称为同类容器类；容器类包含相同类型的对象时，称为同类容器类；n容器类包含不同类型的对象时，称为异类容器类。容器类包含不同类型的对象时，称为异类容器类。容器类库共包括十种容器，分为三大类，分别如下：容器类库共包括十种容器，分为三大类，分别如下：n（1）顺序容器：向量、双队列、列表；）顺序容器：向量、双队列、列表；n（2）关联容器：集合、多重集、映射和多重映射；）关联容器：集合、多重集、映射和多重映射；n（3）容器适配器：堆栈、队列和优先队列。）容器适配器：堆栈、队列和优先队列。5/4/2024227.3 容器（容器（Container）根据使用迭代器的不同可以将容器分为根据使用迭代器的不同可以将容器分为4类：类：n（1）前向容器：一种采用前向迭代器的容器，它和容）前向容器：一种采用前向迭代器的容器，它和容器相比没有什么区别，只是前向容器只能使用前向迭器相比没有什么区别，只是前向容器只能使用前向迭代器。代器。n（2）双向容器：双向容器继承于前向容器，它除了具）双向容器：双向容器继承于前向容器，它除了具有前向迭代器外，还具有逆向迭代器。可以双向访问有前向迭代器外，还具有逆向迭代器。可以双向访问容器中的元素。容器中的元素。n（3）序列容器：序列是一种长度可变的容器，向量中）序列容器：序列是一种长度可变的容器，向量中的元素按照线性关系排列和存储。它直接继承于前向的元素按照线性关系排列和存储。它直接继承于前向容器。容器。n（4）关联容器：关联容器也是一种长度可变的容器，）关联容器：关联容器也是一种长度可变的容器，它支持高效的数据查询和数据操作。它由前向容器衍它支持高效的数据查询和数据操作。它由前向容器衍生而来。生而来。5/4/2024237.3 容器（容器（Container）容器名容器名描述描述类型类型头文件头文件向量向量连续存储元素的数组。连续存储元素的数组。顺序顺序容器容器列表列表由结点组成的双向链表，每个结点包含由结点组成的双向链表，每个结点包含一个元素一个元素顺序顺序容器容器双队列双队列连续存储的指向不同元素的指针所组成连续存储的指向不同元素的指针所组成的数组。的数组。顺序顺序容器容器集合集合由节点组成的红黑树，每个节点都包含由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素素对的谓词排列，没有两个不同的元素能够拥有相同的次序。能够拥有相同的次序。关联关联容器容器多重集合多重集合允许存在两个次序相等的元素的集合。允许存在两个次序相等的元素的集合。关联关联容器容器5/4/202424容器名容器名描述描述类型类型头文件头文件栈栈后进先出的值的排列。后进先出的值的排列。容器适容器适配器配器队列队列先进先出的值的排列。先进先出的值的排列。容器适容器适配器配器优先队列优先队列元素的次序是由作用于所存储的值对元素的次序是由作用于所存储的值对上的某种谓词决定的一种队列。上的某种谓词决定的一种队列。容器适容器适配器配器映射映射由由键，值键，值对组成的集合，以某种作对组成的集合，以某种作用于键对上的谓词排列。用于键对上的谓词排列。关联关联容器容器多重映射多重映射允许键对有相等的次序的映射。允许键对有相等的次序的映射。关联关联容器容器7.3容器（容器（Container）5/4/2024257.3.2 容器的结构容器的结构 n所有的所有的STL容器都是定义在命名空间容器都是定义在命名空间std中的一个模板类，中的一个模板类，由由、和和七个头文件给出。主要包括下面七个头文件给出。主要包括下面3个方面。个方面。n1.常用的类型常用的类型n2.常用的函数常用的函数n3.vector和和list基本结构基本结构 5/4/202426类型名类型名值的类型值的类型描述描述value_type值类型值类型容器中存放元素的类型容器中存放元素的类型size_type长度长度用于计算容器中项目数和检索顺序容器的用于计算容器中项目数和检索顺序容器的类型（不能对类型（不能对list检索）检索）difference_type距离距离引用相同容器的两个迭代器相减结果的类引用相同容器的两个迭代器相减结果的类型（型（list和关联容器没有定义和关联容器没有定义operator-）iterator迭代器迭代器指向容器中存放元素类型的迭代器指向容器中存放元素类型的迭代器const_iterator常迭代器常迭代器指向容器中存放元素类型的常量迭代器，指向容器中存放元素类型的常量迭代器，只能读取容器中的元素只能读取容器中的元素7.3.2 容器的结构容器的结构 顺序容器和关联容器中常用的顺序容器和关联容器中常用的typedef 5/4/202427reverse_iterator逆向迭逆向迭代器代器指向容器中存放元素的逆向迭代器，这种指向容器中存放元素的逆向迭代器，这种迭代器在容器中逆向迭代迭代器在容器中逆向迭代const_reverse_iterator常逆向常逆向迭代器迭代器指向容器中存放元素类型的常逆向迭代指向容器中存放元素类型的常逆向迭代器，只能读取容器中的元素器，只能读取容器中的元素pointer指针指针容器中存放元素类型的指针容器中存放元素类型的指针const_pointer常指针常指针容器中存放元素类型的常量指针，这种指容器中存放元素类型的常量指针，这种指针只能读取容器中的元素和进行针只能读取容器中的元素和进行const操作操作reference引用引用容器中存放元素类型的引用容器中存放元素类型的引用const_reference常引用常引用容器中存放元素类型的常量引用，这种引容器中存放元素类型的常量引用，这种引用只能读取容器中的元素和进行用只能读取容器中的元素和进行const操作操作7.3.2 容器的结构容器的结构 5/4/2024287.3.2 容器的结构容器的结构 容器中共用的函数容器中共用的函数 函数名函数名功能描述功能描述备注备注默认构造函数默认构造函数提供容器默认初始化的构造函数提供容器默认初始化的构造函数拷贝构造函数拷贝构造函数将容器初始化为现有同类容器副本的构造函数将容器初始化为现有同类容器副本的构造函数析构函数析构函数不再需要容器时进行内存整理的析构函数不再需要容器时进行内存整理的析构函数empty（）（）容器中没有元素时返回容器中没有元素时返回true,否则返回否则返回falsemax_size（）（）返回容器中最大元素个数返回容器中最大元素个数size（）（）返回容器中当前元素个数返回容器中当前元素个数operator=将一个容器赋给另一个容器将一个容器赋给另一个容器5/4/202429operator如果第一个容器小于第二个容器，返回如果第一个容器小于第二个容器，返回true，否则返回，否则返回false不适用于不适用于priority_queueoperator如果第一个容器大于第二个容器，返回如果第一个容器大于第二个容器，返回true，否则返回，否则返回false不适用于不适用于priority_queueoperator=如果第一个容器大于或等于第二个容如果第一个容器大于或等于第二个容器，返回器，返回true，否则返回，否则返回false不适用于不适用于priority_queueoperator=如果第一个容器等于第二个容器，返回如果第一个容器等于第二个容器，返回true，否则返回，否则返回false不适用于不适用于priority_queueoperator!=如果第一个容器不等于第二个容器，返如果第一个容器不等于第二个容器，返回回true，否则返回，否则返回false不适用于不适用于priority_queueswap（b）交换两个容器的元素交换两个容器的元素7.3.2 容器的结构容器的结构 5/4/202430顺序容器和关联容器共用的函数顺序容器和关联容器共用的函数 函数名函数名功能描述功能描述备注备注begin（）（）有两个版本返回有两个版本返回iterator或或const_ iterator，引用容器第一个元素引用容器第一个元素不适用于不适用于容器适配器容器适配器end（）（）有两个版本返回有两个版本返回iterator或或const_ iterator,引用容器最后一个元素后面一位引用容器最后一个元素后面一位不适用于不适用于容器适配器容器适配器rbegin（）（）有两个版本返回有两个版本返回reverse_iterator或或const_reverse_iterator,引用容器最后一个元素引用容器最后一个元素不适用于不适用于容器适配器容器适配器rend（）（）有两个版本返回有两个版本返回reverse_iterator或或const_reverse_ iterator，引用容器第一个元素前面一位，引用容器第一个元素前面一位不适用于不适用于容器适配器容器适配器erase(p,q)erase（p）从容器中清除一个或几个元素从容器中清除一个或几个元素不适用于不适用于容器适配器容器适配器clear（）（）清除容器中所有元素清除容器中所有元素不适用于容器不适用于容器适配器适配器5/4/2024317.3.2 容器的结构容器的结构n（1）向量）向量vector定义定义ntemplate class T,class A=allocator nclass vectornnpublic:n /构造函数构造函数n vector();/构造一个空的被控序列构造一个空的被控序列n /构造一个由构造一个由n个值为个值为x的元素组成的序列的元素组成的序列n vector(size_type n,const T&x);n vector(const vector&x);/构造一个由构造一个由x控制序列的拷贝控制序列的拷贝 n /常用函数常用函数n iterator begin();/返回指向序列中第一个元素双向迭代器返回指向序列中第一个元素双向迭代器n iterator end();/返回指向序列末端下一个位置的双向迭代器返回指向序列末端下一个位置的双向迭代器5/4/202432n size_type size()const;/返回序列的长度返回序列的长度n bool empty()const;/序列为空返回序列为空返回true，否则返回，否则返回falsen iterator end();/返回指向序列末端下一个位置的双向迭代器返回指向序列末端下一个位置的双向迭代器n size_type size()const;/返回序列的长度返回序列的长度n bool empty()const;/序列为空返回序列为空返回true，否则返回，否则返回falsen /返回序列中位置为返回序列中位置为pos元素的引用元素的引用n reference at(size_type pos);n /返回序列中位置为返回序列中位置为pos元素的引用元素的引用n reference operator(size_type pos);n /返回指向序列第一个元素的引用，序列不能为空返回指向序列第一个元素的引用，序列不能为空n reference front();n /返回序列最后一个元素的引用，序列不能为空返回序列最后一个元素的引用，序列不能为空n reference back();5/4/202433n /将值为将值为x的元素插入序列末端的元素插入序列末端n void push_back(const T&x);n /删除序列最后一个元素，执行操作前序列不能为空删除序列最后一个元素，执行操作前序列不能为空n void pop_back();n /在序列中在序列中it所指元素前插入一个值为所指元素前插入一个值为x的元素，返回的元素，返回n /指向刚插入元素的迭代器指向刚插入元素的迭代器n iterator insert(iterator it,const T&x);n /在序列中在序列中it所指元素前连续插入所指元素前连续插入n个值为个值为x的元素的元素n void insert(iterator it,size_type n,const T&x);n /删除序列中删除序列中it所指的元素，返回指向被删除元素下一个所指的元素，返回指向被删除元素下一个n /元素的迭代器元素的迭代器n iterator erase(iterator it);n /删除区间删除区间first,last)的所有元素，返回指向的所有元素，返回指向last的迭代器的迭代器n iterator erase(iterator first,iterator last);n void clear();/清除被控序列的所有元素清除被控序列的所有元素n vector();/析构函数析构函数n;5/4/2024347.3.2 容器的结构容器的结构n（2）列表）列表list定义定义ntemplate class T,class A=allocatornclass listnnpublic:n /构造函数构造函数n list();/构造一个空的被控序列构造一个空的被控序列n /构造一个由构造一个由n个值为个值为x的元素组成的序列的元素组成的序列n list(size_type n,const T&x);n list(const list&x);/构造一个由构造一个由x控制序列的拷贝控制序列的拷贝n /常用函数常用函数n iterator begin();/返回指向序列中第一个元素双向迭代器返回指向序列中第一个元素双向迭代器n iterator end();/返回指向序列末端下一个位置的双向迭代器返回指向序列末端下一个位置的双向迭代器5/4/202435n size_type size()const;/返回序列的长度返回序列的长度n bool empty()const;/序列为空返回序列为空返回true，否则返回，否则返回falsen /返回指向序列第一个元素的引用，序列不能为空返回指向序列第一个元素的引用，序列不能为空n reference front();n /返回序列最后一个元素的引用，序列不能为空返回序列最后一个元素的引用，序列不能为空n reference back();n /把一个值为把一个值为x的元素插入到被控序列的开始处的元素插入到被控序列的开始处n void push_front(const T&x);n /删除序列的第一个元素，执行操作前序列不能为空删除序列的第一个元素，执行操作前序列不能为空n void pop_front();n /将值为将值为x的元素插入序列末端的元素插入序列末端n void push_back(const T&x);n /删除序列最后一个元素，执行操作前序列不能为空。删除序列最后一个元素，执行操作前序列不能为空。n void pop_back();n /在序列中在序列中it所指元素前插入一个值为所指元素前插入一个值为x的元素，的元素，n /返回指向刚插入元素的迭代器返回指向刚插入元素的迭代器n iterator insert(iterator it,const T&x);5/4/202436n /在序列中在序列中it所指元素前连续插入所指元素前连续插入n个值为个值为x的元素的元素n void insert(iterator it,size_type n,const T&x);n /从序列中删除从序列中删除it所指的元素，返回指向被删除元素的所指的元素，返回指向被删除元素的n /下一个元素的迭代器。下一个元素的迭代器。n iterator erase(iterator it);n /从序列中删除区间从序列中删除区间first,last)的所有元素，的所有元素，n /返回指向返回指向last的迭代器的迭代器n iterator erase(iteraotr first,iterator last);n void clear();/清除被控序列的所有元素清除被控序列的所有元素n void remove(const T&x);/在队列中删除值为在队列中删除值为x的元素的元素n void unique();/删除序列中所有与前面元素相等的元素删除序列中所有与前面元素相等的元素n void sort();/将序列排序将序列排序n void reverse();/反转序列中的所有元素反转序列中的所有元素n list();/析构函数析构函数n;5/4/2024377.3.3 容器的使用容器的使用n使用容器就像使用一个类模板一样，只不过这个类模使用容器就像使用一个类模板一样，只不过这个类模板是属于板是属于C+标准库的。标准库的。【例【例7.4】list容器完整的程序。本例子初始化一个容器完整的程序。本例子初始化一个list的非空实例，然后将的非空实例，然后将list中的元素值打印出来。中的元素值打印出来。n#includen#includenusing namespace std;nvoid main()nn /初始化一个长度为初始化一个长度为8，元素值都为，元素值都为9的的list类型列表类型列表n list seq(8,9);n /i指向指向seq的第一个元素的第一个元素n list:const_iterator i=seq.begin();5/4/202438n int count=seq.size();/count为为seq的元素个数的元素个数n while(count)n /从头到尾输出从头到尾输出seq的每一个元素的每一个元素n /*i为位置是为位置是i的元素的值的元素的值n coutlist元素元素count：*iendl;n count-;n i+;n nn程序运行结果为：程序运行结果为：nlist元素元素8：9nlist元素元素7：9nlist元素元素6：95/4/2024397.3.3 容器的使用容器的使用nlist元素元素5：9nlist元素元素4：9nlist元素元素3：9nlist元素元素2：9nlist元素元素1：95/4/2024407.4迭代器（迭代器（Iterator）n迭代器从作用上来说是迭代器从作用上来说是STL最基本的部分，但理解起来最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。序员以相同的方式处理不同的数据结构（容器）。n迭代器部分主要由头文件迭代器部分主要由头文件、和和组成。组成。随机存取迭代器随机存取迭代器双向迭代器双向迭代器前向迭代器前向迭代器输出迭代器输出迭代器输入迭代器输入迭代器迭代器关系迭代器关系5/4/2024417.4.1 输入迭代器输入迭代器n输入迭代器只能够从一个序列中读取数值，它可以被输入迭代器只能够从一个序列中读取数值，它可以被修改、引用和进行比较。输入迭代器支持修改、引用和进行比较。输入迭代器支持6种操作。种操作。n（1）+i：前置自增迭代器。：前置自增迭代器。n（2）i+：后置自增迭代器。：后置自增迭代器。n（3）*i：引用迭代器，作为右值。：引用迭代器，作为右值。n（4）i1=i2：将一个迭代器赋值给另一个迭代器。：将一个迭代器赋值给另一个迭代器。n（5）i1=i2：比较迭代器相等性。：比较迭代器相等性。n（6）i1!=i2：比较迭代器不等性。：比较迭代器不等性。5/4/202442元素元素n元素n1 元素n2 元素n3 元素n4输入迭代器工作原理输入迭代器工作原理i+7.4.1 输入迭代器输入迭代器5/4/202443 输入迭代器的例子输入迭代器的例子ntemplate nInputIterator find(InputIterator first,InputIterator last,const T&value)nnwhile(first!=last&*first!=value)n+first;nreturn first;nn上面模板函数上面模板函数find()在容器中查找值为在容器中查找值为value的元素，的元素，然后返回一个指向对象然后返回一个指向对象iterator的指针。的指针。7.4.1 输入迭代器输入迭代器5/4/202444n输出迭代器只能够向一个序列写入数据，它可以被修输出迭代器只能够向一个序列写入数据，它可以被修改和引用。通常用于将数据从一个位置拷贝到另一个改和引用。通常用于将数据从一个位置拷贝到另一个位置。位置。n除了具有输入迭代器的所有功能外，输出迭代器还具除了具有输入迭代器的所有功能外，输出迭代器还具有一个操作有一个操作*i：复引用迭代器，作为左值。：复引用迭代器，作为左值。7.4.2 输出迭代器输出迭代器元素n元素元素n1元素元素n2元素元素n3元素n4输出迭代器工作原理输出迭代器工作原理i+5/4/202445n【例【例7.5】一个关于输出迭代器的例题】一个关于输出迭代器的例题。n#include n#include n#include nusing namespace std;ndouble darray10=1.0,1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9;nvector vdouble(10);/double型型vectornvoid main()nn vector:iterator outputIterator=vdouble.begin();/输出迭代器输出迭代器n /将将darray复制到容器复制到容器vdouble中中n copy(darray,darray+10,outputIterator);n while(outputIterator!=vdouble.end()5/4/202446n n cout *outputIterator ;n outputIterator+;n nn程序运行结果如下：程序运行结果如下：n1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 n例例7.5使用通用算法使用通用算法copy()将将double数组数组darray复复制到容器制到容器vdouble中，然后使用输出迭代器从头到中，然后使用输出迭代器从头到尾将容器中的元素值输出。尾将容器中的元素值输出。n这里，这里，copy()是是STL的通用算法，它的作用是将一的通用算法，它的作用是将一个序列从头到尾复制到另外一个序列中。个序列从头到尾复制到另外一个序列中。7.4.2 输出迭代器输出迭代器5/4/202447n前向迭代器（前向迭代器（forward iterators）既可以用来读也可）既可以用来读也可以用来写，并能够保存迭代器的值，以便从其原先位以用来写，并能够保存迭代器的值，以便从其原先位置开始重新遍历。它能够向前推进到下一个值，但不置开始重新遍历。它能够向前推进到下一个值，但不能递减，它包含了输入和输出迭代器的所有操作。能递减，它包含了输入和输出迭代器的所有操作。7.4.3 前向迭代器前向迭代器 元素元素n元素元素n1元素元素n2元素元素n3元素元素n4前向迭代器工作原理前向迭代器工作原理i+5/4/2024487.4.3 前向迭代器前向迭代器n前向迭代器的例子前向迭代器的例子ntemplate nvoid fill(ForwardIterator first,ForwardIterator last,const T&x);nlong*p=new int100;nfill(p,p+10,0);nfill(p+11,p+100,10);n上面代码使用前向迭代器将数组上面代码使用前向迭代器将数组p的前的前10个元素赋值个元素赋值为为0，后，后90个元素赋值为个元素赋值为10。5/4/2024497.4.4 双向迭代器双向迭代器n双向迭代器（双向迭代器（bidirection iterators）既可以读又可以）既可以读又可以写，它与前向迭代器类似，除了具有前向迭代器的所写，它与前向迭代器类似，除了具有前向迭代器的所有操作外，双向迭代器还具有下面两种操作。有操作外，双向迭代器还具有下面两种操作。n（1）-i：前置自减迭代器；：前置自减迭代器；n（2）i-：后置自减迭代器。：后置自减迭代器。元素元素n元素元素n1元素元素n2元素元素n3元素元素n4双向迭代器工作原理双向迭代器工作原理i+i-5/4/2024507.4.5 随机存取迭代器随机存取迭代器 n随机存取迭代器（随机存取迭代器（random access iterator）可以通）可以通过跳跃的方式访问容器种的任意数据，从而使数据的过跳跃的方式访问容器种的任意数据，从而使数据的访问非常灵活。它除了具有双向迭代器的所有操作外，访问非常灵活。它除了具有双向迭代器的所有操作外，还具有还具有9种操作：种操作：n（1）i+=x：将迭代器：将迭代器i递增递增x位；位；n（2）i-=x：将迭代器：将迭代器i递减递减x位；位；n（3）i+x：在：在i位加位加x位后的迭代器；位后的迭代器；n（4）i-x：在：在i位减位减x位后的迭代器；位后的迭代器；n（5）ix：返回偏离：返回偏离i位元素位元素x位的元素引用；位的元素引用；n（6）i1i2：如果迭代器：如果迭代器i1小于小于i2（即容器中迭代器（即容器中迭代器i1在迭代器在迭代器i2之前），则返回之前），则返回true，否则返回，否则返回false；5/4/2024517.4.5 随机存取迭代器随机存取迭代器n（7）i1i2：如果迭代器：如果迭代器1i大于大于i2（即容器中迭代器（即容器中迭代器i1在迭代器在迭代器i2之后），则返回之后），则返回true，否则返回，否则返回false；n（9）i1=i2：如果迭代器：如果迭代器i1大于或等于大于或等于i2，则返回，则返回true，否则返回，否则返回false；元素元素n元素元素n1元素元素n2元素元素n3 元素元素n4随机存取迭代器工作原理随机存取迭代器工作原理i+=xi-=x5/4/2024527.4.6 迭代器的使用迭代器的使用 【例【例7.6】从标准输入读入】从标准输入读入5个整数，使用输出迭代器输个整数，使用输出迭代器输出这出这5个整数。然后使用个整数。然后使用STL通用算法通用算法sort()对对vector中的元素排序，再输出排序后中的元素排序，再输出排序后vector中元素。中元素。n#include n#include n#include nusing namespace std;nconst int ReadLine=5;nvoid main()nnvector myList;nint temp;5/4/202453n /读取读取ReadLine个整数并将结果存到个整数并将结果存到myList中中n for(int i=0;iReadLine;i+)n n cout temp;/读入整数读入整数n /将读入的整数存到将读入的整数存到myList的最后面的最后面n myList.push_back(temp);n n cout从头到尾输出容器中元素：从头到尾输出容器中元素：endl;n vector:iterator outputIterator=myList.begin();n while(outputIterator!=myList.end()n n cout *outputIterator ;n outputIterator+;n 5/4/202454n /将将myList中元素排序中元素排序n sort(myList.begin(),myList.end();n coutendl排序后输出结果：排序后输出结果：endl;n outputIterator=myList.begin();n while(outputIterator!=myList.end()n n cout *outputIterator ;n outputIterator+;n n coutendl;nn程序运行结果为：程序运行结果为：n请输入一个整数：请输入一个整数：32n请输入一个整数：请输入一个整数：235/4/2024557.4.6 迭代器的使用迭代器的使用n请输入一个整数：请输入一个整数：78n请输入一个整数：请输入一个整数：85n请输入一个整数：请输入一个整数：56n从头到尾输出容器中元素：从头到尾输出容器中元素：n32 23 78 85 56n排序后输出结果：排序后输出结果：n23 32 56 78 85 5/4/2024567.5算法（算法（Algorithm）7.5.1算法和函数对象算法和函数对象n广义上讲，算法是一个按照一组定义明确的步骤来解广义上讲，算法是一个按照一组定义明确的步骤来解决某个问题的处理过程。决某个问题的处理过程。n所有算法的前两个变量都是一对迭代器，通常称为首所有算法的前两个变量都是一对迭代器，通常称为首（first）和末（）和末（last）迭代器，用来表明算法对容器进）迭代器，用来表明算法对容器进行操作的元素范围。元素范围是一个区间行操作的元素范围。元素范围是一个区间fist,last)，它表示范围从，它表示范围从first（包含（包含first指向的元素）开指向的元素）开始，到始，到last结束（不包含结束（不包含last指向的元素）指向的元素）n函数对象是函数的一般形式。实际上函数对象是一个函数对象是函数的一般形式。实际上函数对象是一个重载了重载了operator()的类。的类。5/4/2024577.5.1 算法和函数对象算法和函数对象函数对象函数对象类型类型函数对象函数对象类型类型函数对象函数对象类型类型divides算术算术less_equal关系关系modulus算术算术equal_to关系关系logical_and逻辑逻辑negate算术算术greater关系关系logical_not逻辑逻辑not_equal_to关系关系greater_equal关系关系logical_or逻辑逻辑plus算术算术less关系关系minus算术算术multiplies算术算术STL中的函数对象中的函数对象 5/4/2024587.5.1 算法和函数对象算法和函数对象 【例【例7.7】函数对象的使用方法例题。函数对象的使用方法例题。n#includenusing namespace std;nclass CAdd /函数对象函数对象nnpublic:n int operator()(int x,int y)n n return x+y;n n /程序其它部分程序其它部分n;5/4/2024597.5.1 算法和函数对象算法和函数对象nvoid main()nn CAdd add;/定义函数对象的实例定义函数对象的实例n cout输出结果：输出结果：add(3,2)endl;n CAdd sum;n cout再输出一次：再输出一次：sum(3,2)endl;nn程序运行结果为：程序运行结果为：n输出结果：输出结果：5n再输出结果：再输出结果：5n可以看出，函数对象与函数指针比较类似，实际上它可以看出，函数对象与函数指针比较类似，实际上它们除了定义方式不同外，使用方法几乎一样。们除了定义方式不同外，使用方法几乎一样。5/4/2024607.5.2 算法分类介绍算法分类介绍nSTL提供了提供了70个算法，按照不同的分类方法可以将这个算法，按照不同的分类方法可以将这些算法分成不同的类别：些算法分成不同的类别：n（1）按照算法所做工作的不同，可以将算法分成）按照算法所做工作的不同，可以将算法分成8个个种类：查找、排序、数值计算、比较、集合、容器管种类：查找、排序、数值计算、比较、集合、容器管理、统计和堆操作。理、统计和堆操作。n（2）按照算法对容器的影响，可以将算法分成）按照算法对容器的影响，可以将算法分成4个种个种类：非修正算法、修正算法、排序算法和数值计算算类：非修正算法、修正算法、排序算法和数值计算算法。法。n下面按照第二种分类分别介绍。下面按照第二种分类分别介绍。5/4/2024617.5.2 算法分类介绍算法分类介绍n1非修正算法非修正算法 非修正算法的操作不对变容器中的元素进行任何修改，这非修正算法的操作不对变容器中的元素进行任何修改，这类算法包括类算法包括adjacent_find()、find()、find_end()、find_first()、count()、mismatch()、equal()、for_each()和和search()等，这些算法都包含在头文件等，这些算法都包含在头文件中。中。n【例【例7.8】非修正算法例题。】非修正算法例题。n#include n#include n#include n#include nusing namespace std;5/4/202462nvoid print(string&str)nn cout str endl;nnvoid main()nn list fruit;/定义一个定义一个list t列表列表fruitn fruit.push_back(桔子桔子);/将元素放入列表末端将元素放入列表末端n fruit.push_back(苹果苹果);n fruit.push_back(香蕉香蕉);n fruit.push_front(菠萝菠萝);n fruit.push_front(西瓜西瓜);n /对列表中的元素逐个进行对列表中的元素逐个进行print操作操作n for_each(fruit.begin(),fruit.end(),print);n5/4/2024637.5.2 算法分类介绍算法分类介绍n程序运行结果为：程序运行结果为：n西瓜西瓜n菠萝菠萝n桔子桔子n苹果苹果n香蕉香蕉n2修正算法修正算法 在实际应用中，经常需要对容器中的元素进行修改和在实际应用中，经常需要对容器中的元素进行修改和写操作，这类能够对容器中元素进行修改的算法称为修写操作，这类能够对容器中元素进行修改的算法称为修正算法。修正算法正算法。修正算法包括包括copy()、copy_back