C++程序设计--标准模板库STL介绍及应用(第7章)

C/C++程序设计教程郑秋生主编2020/2/242第7章标准模板库STL介绍及应用本章学习重点掌握内容：标准模板库STL的基本概念标准模板库STL的组成部分命名空间的概念及使用容器的概念和使用迭代器的概念和使用算法的概念和使用标准模板库STL的应用2020/2/243第7章标准模板库STL介绍及应用7.1标准模板库STL的概念7.2容器（Container）7.3迭代器（Iterator）7.4算法（Algorithm）7.5综合应用实例2020/2/2447.1标准模板库STL的概念STL最初是由惠普实验室开发的一系列组件，是标准C++库的重要补充之一。从逻辑层次来看，STL体现了泛型程序设计的思想，引入了多个新的名词，比如容器、算法、迭代器等。在STL中，几乎所有的代码都采用了类模板和函数模板的方式，因而，提供了更好的代码重用机会。从广义上讲，STL的代码分为三类：容器、迭代器和算法。这3类代码被组织为13个头文件。2020/2/2457.1.2STL和C++标准的关系输入/输出数值诊断通用工具国际化语言支持容器算法迭代器字符串STLC++标准库C标准函数STL和C++标准库的关系2020/2/2467.1.3STL组成部分函数对象通用算法assistSTL容器迭代器supportsapplytoaccessuseuseSTL结构图2020/2/2474STL组成部分容器用来容纳对象或对象组的组合。STL的容器包括向量（vector）、链表(list)等2类7种。迭代器是一种面向对象的广义指针，用于指向容器中或流中的对象，提供访问方法。算法是STL的核心，是普通算法的泛化形式。算法通过迭代器的指向与容器分离，从而具有通用性。函数对象的主要作用是作为参数传递给某些通用算法，从而进一步提高算法的通用性。STL中预定义了3大类15个函数对象，用户也可根据需要自行设计。2020/2/248STL对C++的影响在STL之前，C++支持三种基本的编程样式—面向过程编程、数据抽象和面向对象编程。在STL出现之后，C++可以支持一种新的编程模式—泛型程序设计。STL并不完美，但是，它开辟了程序设计的新天地，它拥有的影响力甚至于超过了巨大的C++群体。2020/2/2497.2容器（Container）7.2.1容器简介容器是能够保存其它类型的对象的类。C++的容器可以包含混合类型的对象，也就是说容器类可以包含一组相同类型或一组不同类型的对象。容器类包含相同类型的对象时，称为同类容器类；容器类包含不同类型的对象时，称为异类容器类。容器类库共包括十种容器，分为三大类，分别如下：（1）顺序容器：向量、双队列、列表；（2）关联容器：集合、多重集、映射和多重映射；（3）容器适配器：堆栈、队列和优先队列。2020/2/24107.2容器（Container）容器名描述类型头文件向量连续存储元素的数组。顺序容器vector列表由结点组成的双向链表，每个结点包含一个元素顺序容器list双队列连续存储的指向不同元素的指针所组成的数组。顺序容器deque集合由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序。关联容器set多重集合允许存在两个次序相等的元素的集合。关联容器set2020/2/2411容器名描述类型头文件栈后进先出的值的排列。容器适配器stack队列先进先出的值的排列。容器适配器queue优先队列元素的次序是由作用于所存储的值对上的某种谓词决定的一种队列。容器适配器queue映射由{键，值}对组成的集合，以某种作用于键对上的谓词排列。关联容器map多重映射允许键对有相等的次序的映射。关联容器map7.2容器（Container）2020/2/24127.2.2容器的结构所有的STL容器都是定义在命名空间std中的一个模板类，由vector、list、deque、set、map、stack和queue七个头文件给出。主要包括下面3个方面。1.常用的类型2.常用的函数3.vector和list基本结构2020/2/2413类型名值的类型描述value_type值类型容器中存放元素的类型size_type长度用于计算容器中项目数和检索顺序容器的类型（不能对list检索）difference_type距离引用相同容器的两个迭代器相减结果的类型（list和关联容器没有定义operator-）iterator迭代器指向容器中存放元素类型的迭代器const_iterator常迭代器指向容器中存放元素类型的常量迭代器，只能读取容器中的元素7.2.2容器的结构2020/2/2414reverse_iterator逆向迭代器指向容器中存放元素的逆向迭代器，这种迭代器在容器中逆向迭代const_reverse_iterator常逆向迭代器指向容器中存放元素类型的常逆向迭代器，只能读取容器中的元素pointer指针容器中存放元素类型的指针const_pointer常指针容器中存放元素类型的常量指针，这种指针只能读取容器中的元素和进行const操作reference引用容器中存放元素类型的引用const_reference常引用容器中存放元素类型的常量引用，这种引用只能读取容器中的元素和进行const操作7.3.2容器的结构2020/2/24157.3.2容器的结构容器中共用的函数函数名功能描述备注默认构造函数提供容器默认初始化的构造函数拷贝构造函数将容器初始化为现有同类容器副本的构造函数析构函数不再需要容器时进行内存整理的析构函数empty（）容器中没有元素时返回true,否则返回falsemax_size（）返回容器中最大元素个数size（）返回容器中当前元素个数operator=将一个容器赋给另一个容器2020/2/2416operator如果第一个容器小于第二个容器，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器小于或等于第二个容器，返回true，否则返回false不适用于priority_queueoperator如果第一个容器大于第二个容器，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器大于或等于第二个容器，返回true，否则返回false不适用于priority_queueoperator==如果第一个容器等于第二个容器，返回true，否则返回false不适用于priority_queueoperator!=如果第一个容器不等于第二个容器，返回true，否则返回false不适用于priority_queueswap（b）交换两个容器的元素7.3.2容器的结构2020/2/2417顺序容器和关联容器共用的函数函数名功能描述备注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（）清除容器中所有元素不适用于容器适配器2020/2/24187.3.2容器的介绍（1）向量vector是个能够存放任意类型的动态数组，但是能够自动分配内存，随机存取能在常数时间完成，像数组一样可以使用下标访问元素，小心，不要数组越界在尾端增删元素具有较佳的性能其他位置的增删操作和插入操作都不好需要把待插入元素右边的每个元素都拷贝一遍使用vector包含头文件„#includevector名字空间(namespace)vector属于std命名域的„usingstd::vector;或者连在一起，使用全„std::vectorintvInts建议使用全局的名字空„usingnamespacestd;2020/2/2419使用vector数组创建一个int型的vectorvectorintintarray;//定义一个整型数组，可以是任意类型向vector添加一个数据vector添加数据的缺省方法是push_back()„push_back()函数表示将数据添加到vector的尾部„并按需要来分配内存for(inti=0;i10;i++)intarray.push_back(i);2020/2/2420向vector插入一个数据insert()；//需要从插入点开始后移所有元素，并按需分配存储空间删除vector中的数据pop_back();//最有位置删除一个erase(iteratorfirst,iteratorlast);//迭代器指定位置clear()//清楚所有元素，判断数据个数empty()„判断vector是否为空size()„返回vector的数据个数2020/2/2421预先分配内存空间reserve(intn);//reserve只是预先划分一块内存给vector使用，主要是为了提高效率：避免在不断push_back的过程中，由于容量变动导致的重新分配,注意：仅是分配空间，新元素还没有构造,不能引用resize(intn);//是改变容器的大小，并且创建对象，可以引用注意：vector和普通数组的区别，只有调用了构造函数，才可以引用，如果析构后则不可以引用2020/2/2422获得存储空间大小size();//已经包含的数组元素的个数，注意构造过的，对应于resize(intn)capacity();//容器的存储能力，对应于reserve(intn)2020/2/2423vector的元素访问使用三种方法来访问vector中的数据„vector::at(intidx)„vector::operator[intidx]迭代器，通用方法，所有容器适用„前两者区别„operator[]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。容易造成越界访问，尽量少用„at()是首选，因为at()进行了边界检查，如果访问超过了vector的范围，将抛出一个例外。2020/2/2424vector的元素访问利用迭代器访问vectorint::iteratoriter;//定义迭代器for(iter=intarry.begin();iter!=intarray.end();iter++)*iter=100；//类似于指针2020/2/24252020/2/24267.3.2容器的结构（2）列表list定义链表结构：链表的使用和vector基本相同，只是存储结构不同，使用略微不同。算法效率不同，插入数据线性，访问数据效率不高（数据结构）a1a2…...an^2020/2/24277.3.3容器的使用使用容器就像使用一个类模板一样，只不过这个类模板是属于C++标准库的。【例7.4】list容器完整的程序。本例子初始化一个list的非空实例，然后将list中的元素值打印出来。2020/2/24287.4迭代器（Iterator）迭代器从作用上来说是STL最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。迭代器部分主要由头文件utility、iterator和memory组成。iterator类的对象就成为一种指向链表结点的广义指针，