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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

容器的共通操作 比较操作

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

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

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

各个容器的使用时机

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Algorithm（算法） 70个 算法列表

Algorithm（算法） 算法列表

Algorithm（算法） 算法列表

Algorithm（算法） 算法列表

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

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