导入 STL的概念与组成 Iterator（迭代器） Container（容器） Algorithm（算法） Adaptors（配接器）

Presentation on theme: "导入 STL的概念与组成 Iterator（迭代器） Container（容器） Algorithm（算法） Adaptors（配接器）"— Presentation transcript:

1 导入 STL的概念与组成 Iterator（迭代器） Container（容器） Algorithm（算法） Adaptors（配接器）

2 导入　 抽象的重要性 计算机科学的重要进步，许多是由于发掘了新的抽象性质而促成的 面向过程－＞基于对象－＞面向对象　　　－＞泛型

3 导入 面向过程(Procedure-Oriented)的抽象
导入　 面向过程(Procedure-Oriented)的抽象 抽象出Procedure（Function）的概念，把程序分成若干个子过程。将事物的方法隐藏于各个函数内－－C语言。 适用于处理小型的程序。对大型程序， 子程序之间关系复杂，不易处理变化的需求－－引发软件危机的原因－－需要新的抽象。 变化总是存在的 耦合度

4 导入　 面向过程示例 调用子过程时不用考虑其实现细节。

5 导入 基于对象(Object-Based)的抽象
导入　 基于对象(Object-Based)的抽象 引入抽象数据类型（ADT，Abstract Data Type）。C++的类，将事物的属性与方法紧密地结合在一起－－VB、带类的C。 与面向过程相比，可以更好地处理变化，一定程度上化解了软件危机。但各个类之间的关系不容易处理，而且程序代码数量比面向过程时更大－－需要新的抽象。

6 导入　 示例 Person是一个抽象数据类型 强内聚，低耦合。

7 导入 面向对象(Object-Oriented)的抽象 抽象出封装、继承、多态( polymorphic )的概念。
导入　 面向对象(Object-Oriented)的抽象 抽象出封装、继承、多态( polymorphic )的概念。 与基于对象相比，有更多的间接性。运用多态，我们可以调用某种方法，而不用指定此方法所属的类型。因而达到更进一步的抽象性。 它为我们带来了什么？－－MFC（用面向对象技术封装Windows　API，抽象出一个类体系）

8 对用户封装了具体的类型，用户只需和抽象类打交道
导入　 示例 对用户封装了具体的类型，用户只需和抽象类打交道

9 Application Framework
MFC类体系图 物体类 Application Framework 窗口类 视图类 边框类

10 导入 泛型（Generic）的概念 Generic是一种抽象 就如 OO是一种抽象。
还没有语法与之相对应－－正在开发中。　（Function、Class、D : public B） 它为我们带来了什么？－－STL。

11 STL的概念　 何为STL？ STL(Standard Template Library)是C＋＋标准庫的一部分（80%），是用C＋＋ Template机制来表达泛型的庫。 STL(Standard Template Library)是用泛型技术来设计完成的实例 就如 MFC(Microsoft Foundational Classes)是用面向对象技术来设计完成的实例

12 STL的概念 STL抽象的是什么？ 有些算法并不依赖于数据结构的特定实现，而只是依赖于该结构的几个基本的语义属性.
STL抽象出这些基本属性（Concept），成功的将算法与数据结构分离，在没有效率损失的前提下，得到了及大的弹性。

13 用一个泛型算法可以处理多种数据结构。而且在获得弹性的同时运行效率上和以前相比没有损失。
STL的概念　 示例 用一个泛型算法可以处理多种数据结构。而且在获得弹性的同时运行效率上和以前相比没有损失。

14 STL的六大组件全都是抽象出来的Concepts
容器（Container） 算法（Algorithm） 迭代器（Iterator） 仿函数（Function object） 适配器（Adaptor） 空间配制器（allocator） STL的六大组件全都是抽象出来的Concepts

15 STL的组成 STL在哪里？ 后缀名？ Namespace std

16 定义并初始化一个list容器 对区间内每个元素调用传入的操作pfi

17 Copy是一个泛型算法，它将文件中的内容显示到屏幕上

18 相关资料 STL之父访谈录 －－详细介绍了STL的历史，点明了STL的设计宗旨以及它与OO的关系。 复习C++ Template机制。
习题： STL example1、STL example2

19 Namespace（名字空间） Template的新特性 新的类型转换运算符
新的语言特性 Namespace（名字空间） Template的新特性 新的类型转换运算符

20 命名空间（Namespace） 现在的软件多以程序庫、模块、组件拼凑而成，名称冲突问题越来越严重。Namespace就是用来解决此问题的。

21 命名空间（Namespace） Namespace的名字和标识符号间以 : :分隔 （类似于Class 与 members之间）

22 可以在不同模块之间定义和扩展namespace。因此可以用namespace来定义模块、程序庫或组件。

23 命名空间（Namespace） using declaration，我们可以避免一再写出冗长的namespace名称
using directive 这就是一个using declaration，它使I成为当前范围内代表Renwind::I的同义词。 这就是一个using directive，它使Renwind内的所有名字曝光。

24 这种写法只适用于写示例程序或相对小的程序
命名空间（Namespace） using directive会再度引发名称冲突 这种写法只适用于写示例程序或相对小的程序 调用哪一个 i 呢？

25 Template的新特性 类模板显示特化(class template explicit specialization )

26 Template的新特性 类模板偏特化(class template partial specialization)

27 根据前一个模板参数T，设定下一个模板参数
Template的新特性 默认模板参数 根据前一个模板参数T，设定下一个模板参数

28 Template的新特性 成员模板(member template) 模板类的成员函数可以是一个模板

29 Template的新特性 关键字 typename 做为类型前的标识符号。
指出SubType是T中定义的一个类型，因此ptr是一个指向T:SubType的指针。 如果不加typename，表达式被认为是T中的静态成员SubType和ptr的乘积。

30 Template的新特性 关键字 typename
C＋＋的一般规则是，除了以typename修饰以外，template内的任何标识符号都被视为一个值（value），而非一个类型（type）。 typename的第二个作用：在模板声明中替换关键字class。

31 新的类型转换运算符 static_cast 只有当类型转换有所定义，整个转换才会成功。 由float转换到int有所定义
由char*转换到string有所定义

32 新的类型转换运算符 dynamic_cast 将多态类型向下转型(downcast)为其实际类型 多态类型 运行期进行检验

33 新的类型转换运算符 const_cast、reinterpret_cast
C语言中的转型（用小圆括号）可替换dynamic_cast之外的其它三种类型。也因此无法明确显示使用它的确切理由。 新的转型操作符给了编译器更多信息，让编译器清楚知道转型的理由。

34 Container（容器） 容器的概念 用来管理一组元素。

35 Container（容器） 容器的分类 序列式容器（Sequence containers）
每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。 vector、deque、list 关联式容器（Associated containers） 元素位置取决于特定的排序准则，和插入顺序无关 set、multiset、map、multimap

36 序列式容器 Vectors 将元素置于一个动态数组中加以管理。 可以随机存取元素（用索引直接存取）。
数组尾部添加或移除元素非常快速。但是在中部或头部安插元素比较费时。

37 用vector前，必须包含头文件<vector>
序列式容器 Vectors　示例 用vector前，必须包含头文件<vector>　

38 序列式容器 Deques deque，是“double-ended queue”的缩写。 可以随机存取元素（用索引直接存取）。
数组头部和尾部添加或移除元素都非常快速。但是在中部或头部安插元素比较费时。

39 用deque前，必须包含头文件<deque>
序列式容器 Deques　示例 用deque前，必须包含头文件<deque>　

40 序列式容器 Lists 双向链表。 不提供随机存取（按顺序走到需存取的元素，O(n)）。
在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。

41 用list前，必须包含头文件<list>
序列式容器 Lists　示例 用list前，必须包含头文件<list>　

42 迭代器（Iterator）简述 指针与数组 指针与其它数据结构呢？比如说链表？
存储空间是非连续的。不能通过对指向这种数据结构的指针做累加来遍历。 能不能提供一个行为类似指针的类，来对非数组的数据结构进行遍历呢？这样我们就能够以同样的方式来遍历所有的数据结构（所有容器）。 用指针遍历数组

43 容器提供一些函数以获得迭代器并以之遍历所有元素。
迭代器（Iterator）简述 迭代器与容器 通过迭代器，我们可以用相同的方式来访问、遍历容器。 泛型抽象 用迭代器遍历容器 容器提供一些函数以获得迭代器并以之遍历所有元素。 每种容器都必须提供自己的迭代器

44 迭代器（Iterator）简述 迭代器的概念 迭代器是一个“可遍历STL容器内全部或部分元素”的对象。 一个迭代器指出容器中的一个特定位置。
具有遍历复杂数据结构的能力。

45 迭代器（Iterator）简述 用法和指针一样，其实指针就是一种迭代器 迭代器的基本操作 运算符重载

46 迭代器（Iterator）简述 迭代器示例

47 关联式容器 Sets/Multisets 内部的元素依据其值自动排序
Set内的相同数值的元素只能出现一次，Multisets内可包含多个数值相同的元素。 内部由二叉树实现，便于查找。

48 关联式容器 Sets/Multisets 用set/multiset前，必须包含头文件<set>
不能用push_back…因为是自动排序的。

49 关联式容器 Maps/Multimaps Map的元素是成对的键值/实值，内部的元素依据其值自动排序。
Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素。 内部由二叉树实现，便于查找。

50 用map/multimap前，必须包含头文件<map>
关联式容器 Maps/Multimaps 用map/multimap前，必须包含头文件<map>　 便捷函数，返回一个pair对象

51 容器的共通能力 所有容器提供的都是value语意，而非reference语意。容器执行插入元素的操作时，内部实施拷贝动作。所以STL容器内存储的元素必须能够被拷贝（必须提供拷贝构造函数）。 每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。 通常STL不会丢出异常。要求使用运行者对确保传入正确的参数。

52 容器的共通操作 初始化－－每个容器都提供了一个默认构造函数，一个拷贝构造函数 以某个容器的元素为初值完成初始化。
以某个数组的元素为初值完成初始化。

53 容器的共通操作 与大小相关的操作函数 返回迭代器的函数

54 容器的共通操作 比较操作

55 Vector容器详解 大小（Size）和容量（Capacity） 如果capacity不够用，则重新分配内存
capacity()，传回vector能够容纳的元素个数。 size()，传回vector内现有元素的个数。 如果capacity不够用，则重新分配内存 使和vector相关联的pointer,reference,iterator全部失效。 很费时间。

56 Vector容器详解 赋值操作 元素存取

57 Vector容器详解 插入和删除操作

58 各个容器的使用时机

59 Iterator（迭代器） 迭代器的作用 能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来。
重载了＊，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构。 容器提供迭代器，算法使用迭代器。

60 Iterator（迭代器） 容器提供迭代器 一个简单的例子 算法使用迭代器

61 因此List提供了自己的sort成员函数
Iterator（迭代器） 迭代器的分类 不同容器提供自己的迭代器，所以不同迭代器具有不同的能力。 不同的算法需要不同的迭代器的能力；相同的算法需要根据迭代器的能力不同而做相应的优化。 Vector的内部是数组 List的内部是双向链表 因此List提供了自己的sort成员函数

62 Iterator（迭代器） 迭代器的分类 write only read only不能改变iterator所指对象 单向迭代器，iter++
所有指针的运算能力，p+n, p-n, p[n], p1-p2, p1<p2 双向迭代器，iter++、iter--

63 Iterator（迭代器） 一个例子－－advance()

64 Iterator（迭代器） 迭代器的相关类型 迭代器的traits编程技法 用来扩充容器与算法。
有些算法内部需要用到迭代器所代表元素的类型，这个就是迭代器的相关类型。 迭代器的traits编程技法 用来扩充容器与算法。

65 Iterator adaptor（迭代器配接器）
概念 提供和iterator相同的接口，但是改变内部的实现方法。 分类 Insert iterator Stream iterator Reverse iterator 接口还是迭代器的接口，前缀描述了迭代器的内部实现

66 Iterator adaptor（迭代器配接器）
Insert（安插型）iterator

67 设计模式 Iterator与adaptor是设计模式中的两种。
尽管Alexander所指的是城市和建筑模式，但他的思想也同样适用于面向对象设计模式。只是在面向对象的解决方案里，我们用对象和接口代替了墙壁和门窗。两者的核心都在于提供了相关问题的解决方案。 ——Gang of Four，《设计模式》 Iterator与adaptor是设计模式中的两种。

68 设计模式 管理模式——Don S. Olson, Carol L. Stimmel, The Manager Pool
分析模式——Martin Fowler, Analysis 　　Patterns 设计模式 实现模式——Scott Meyers, Effective C++ 重构模式——Martin Fowler, Refactoring

69 设计模式 我们需要这样一种语言：它让我们高效地交流、讨论那些常见的、重复出现的设计概念，并在这些概念上建立起我们的系统。
不要仅仅把模式当作解决方案，而要把它们当作设计的词汇，这些词汇可以根据一定的规则组合起来形成句子（也就是系统设计）。 ——Brandon Goldfedder，《模式之乐》

70 Iterator模式 定义：提供一种方法，使用按顺序访问某个容器所含的各个元素，而无需曝露该容器的内部表述方法。

71 Adaptor模式 定义：将一个类的界面转换为另一个类的界面，使原本因界面不相容而不能合作的classes，可以一起运作。

72 Adaptor模式 在STL中，改变iterator界面的叫做iterator adaptor
改变container界面的叫做container adaptor， 改变function object界面的叫做function adaptor

73 Container Adaptor STL提供的另两种容器queue、stack，其实都只不过是一种adaptor，它们简单地修饰deque的界面而成为另外的容器类型 STL的源码

74 Algorithm（算法） 泛型算法通则 所有算法的前两个参数都是一对iterators：[first，last)，用来指出容器内一个范围内的元素。 每个算法的声明中，都表现出它所需要的最低层次的iterator类型。

75 Algorithm（算法） 泛型算法通则 大部分算法都可以用functioin object 来更改准则。function object又称functor。

76 Algorithm（算法） 70个 算法列表

77 Algorithm（算法） 算法列表

78 Algorithm（算法） 算法列表

79 Algorithm（算法） 算法列表

80 Ending and Begining 总论： ＜＜大局观：泛型程序设计与STL＞＞ 参考手册 ＜＜C++标准程序库＞＞ MSDN

81 Ending and Begining Ogre引擎 大量运用STL 大量运用OOA、OOD 设计模式 图形API 图形学算法
ActiveX控件、COM 网络支持