《chap12_标准模板库》-课件设计（公开）.ppt

入门篇 主讲：龙满生 内容提要 STL概述 Iterator（迭代器） Container（容器） Algorithm（算法） Adaptor（适配器） Function Object（函数对象） Allocator（分配器） 12.1 STL概述 抽象是面向对象程序设计的重要特性 面向过程：算法→函数，隐藏实现细节 基于对象：对象属性和方法→类，高内聚、低耦合 面向对象：封装、继承、多态、泛型 重用是面向对象程序设计的主要目标 继承机制支持派生类重用基类的代码 多态机制使得同一层次的派生类可以重用基类中定义的虚函数接口 模板机制使得可以重用函数定义或类定义来处理不同类型的数据 12.1 STL概述 标准模板库（Standard Template Library, STL）基于模板机制定义了常用的数据结构和算法 通过抽象，使得算法与数据结构分离，同一泛型算法可以处理多种数据结构。 STL主要包括迭代器（iterator）、容器（container）、算法（algorithm）、适配器（adaptor）、函数对象（function object）和分配器（allocator）。 STL是标准库的主要组成部分，名称空间为std。 12.1 STL概述 容器：包含数据序列的数据结构，定义为类模板 迭代器：访问容器元素的抽象指针，定义为类模板 算法：对元素序列的通用操作，定义为函数模板 泛型算法通过迭代器对容器元素进行操作 适配器：改变某种对象工作方式的对象，定义为类模板，依赖基础类的接口实现自身接口 函数对象：可用作函数的对象，需要在类中重载()操作符 12.1 STL概述 12.2 迭代器 12.2 迭代器 12.2 迭代器 12.2 迭代器 迭代器的类别 不同的容器有各自的迭代器类型，属于不同的类别 vector和deque的迭代器是随机访问迭代器； list的迭代器是双向迭代器； 所有关联容器的迭代器都是双向迭代器； 容器适配器不支持迭代器； istream_iterator是输入迭代器； ostream_iterator是输出迭代器。 不同的算法要求有不同的迭代器类别 12.2 迭代器 12.2 迭代器 迭代器适配器 Insert iterator 三种插入迭代器对象 insert_iterator：调用容器的insert front_insert_iterator：调用容器的push_front back_insert_iterator：调用容器的push_back 三个用于从容器创建插入迭代器的函数 inserter, front_inserter, back_inserter 12.2 迭代器 12.2 迭代器 迭代器适配器 Stream iterator istream_iterator：用于从流中输入数据 ostream_iterator：用于向流中输出数据 istreambuf_iterator ：用于从流缓冲中输入数据 ostreambuf_iterator：用于向流缓冲中输出数据 Reverse iterator reverse_iterator：使双向迭代器或随机迭代器反向 12.2 迭代器 12.2 迭代器 12.2 迭代器 12.2 迭代器 12.2 迭代器 12.3 容器 向容器插入元素时，实施对象拷贝操作。因此，容器元素类型必须支持复制及赋值操作。 引用类型不支持赋值操作，因此不能用作容器元素类型 I/O库类型也不支持赋值和复制操作，因此也不能用作容器元素类型 容器具有各自的迭代器类型，提供返回迭代器的函数，通过迭代器就可以访问元素。 容器可以分为顺序容器和关联容器两大类。 12.3 容器 顺序容器（Sequence Container） 按照元素在容器中的位置顺序进行访问 元素位置与元素值无关，取决于插入时点 vector、deque、list 关联容器（Associated Container） 按照元素的键值（key）排序 元素位置取决于特定的排序准则，和插入顺序无关 set、multiset、map、multimap 拟容器：vectorbool、bitset、valarray 12.3 容器 12.3 容器 12.3 容器 容器中定义的比较操作符 用于比较两个容器对象 ==和!=调用equal算法实现比较，当两个容器对象的大小及对应元素均相等时才相等。 、=、、=调用lexicographical_compare算法实现比较，比较结果取决于第一对不相等元素的结果。 lexicographical_compare算法要求参与比较的元素支持操作。 容器对象的比较操作类似于按字母顺序的字符串比较。 12.3.1 顺序容器 顺序容器的构造函数形式 explicit Seq(const