软件工程面向对象编程第二次课泛型编程风格.ppt

面向对象的程序设计第二讲 泛型编程风格——STL容器和泛型算法 华中科技大学CAD中心 吴义忠 wuyz@ 主要内容 2.1 泛型指针 2.2 容器的共同操作 2.3 序列容器 2.4 关联容器 2.5 泛型算法 2.6 STL小结 2.7 其他 C++标准库内容 · 标准C库。它还在，你还可以用它。虽然有些地方有点小的修修补补，但无论怎么说，还是那个用了多年的C库。 · Iostream。和 “传统” Iostream的实现相比，它已经被模板化了，继承层次结构也做了修改，增强了抛出异常的能力，可以支持string（通过stringstream类）和国际化。当然，你期望Iostream库所具有的东西几乎全都继续存在。如cin，cout，cerr对象。 · String。string对象在大多数应用中被用来消除对char*指针的使用。它们支持你所期望的那些操作（例如，字符串连接，通过operator[]对单个字符进行常量时间级的访问，等等），它们可以转换成char*，以保持和现有代码的兼容性，它们还自动处理内存管理。 · 容器。不要再写你自己的基本容器类！标准库提供了下列高效的实现：vector（就象动态可扩充的数组），list（双链表），queue， stack，deque，map，set和bitset。唉，竟然没有hash table（虽然很多制造商作为扩充提供），但多少可以作为补偿的一点是， string是容器。这很重要，因为它意味着对容器所做的任何操作（见下文）对string也适用。 C++标准库 · 算法。标准容器当然好，如果存在易于使用它们的方法就更好。标准库就提供了大量简易的方法（即，预定义函数，官方称为算法(algorithm) ---- 实际上是函数模板），其中的大多数适用于库中所有的容器 ---- 以及内建数组（built-in arrays）！ · 对国际化的支持。支持国际化最主要的构件是facets和locales。facets描述的是对一种文化要处理哪些特性，包括排序规则（即，某地区字符集中的字符应该如何排序），日期和时间应该如何表示，数字和货币值应该如何表示，怎样将信息标识符映射成（自然的）明确的语言信息，等等。 C++标准库 · 对数字处理的支持。C++库为复数类（实数和虚数部分的精度可以是float，double或long double）和专门针对数值编程而设计的特殊数组提供了模板。例如，valarray类型的对象可用来保存可以任意混叠(aliasing)的元素。并提供了算法计算内积(inner product)，部分和(partial sum)，临差(adjacent difference)等。 · 诊断支持。标准库支持三种报错方式：C的断言（参见条款7），错误号，例外。为了有助于为例外类型提供某种结构，标准库定义了下面的例外类（exception class）层次结构。 C++精华部分－－STL STL是标准库中最具创新的部分，这并不是因为它提供了容器和算法（虽然它们非常有用），而是因为它的体系结构。 简单来说，它的体系结构具有扩展性：你可以对STL进行添加。当然，标准库中的组件本身是固定的，但如果遵循STL构建的规范，你可以写出自己的容器，算法和迭代子，使它们可以和标准STL组件一起工作，就象标准组件自身之间相互工作一样。你还可以利用别人所写的符合STL规范的容器，算法和迭代子，就象别人利用你的一样。使得STL具有创新意义的原因在于它实际上不是软件，而是一套规范（convention）。标准库中的STL组件只是具体体现了遵循这种规范所能带来的好处。 STL = 抽象容器 + 泛型算法程序=数据结构+算法 抽象容器：包括vector, list, deque, set/multiset, map/multimap, hash_map等，其中vector, list，deque等是序列式容器，set, map为关联式，使用关键字进行索引查询 泛型算法：针对不同容器进行的公共操作行为。它是通过函数模板或对象模板技术实现与数据类型和容器类型无关的操作 迭代器：实现容器与算法的连接，也称泛型指针，指向容器中的元素 2.1.1 查找的几个版本进化 V2: 从一个地址到另一个地址之间进行查找（不用size） 指针算术运算的适用范围 内存空间中连续的数据结构 数组array 向量vector，如find(v1[0], v1[10], v1[5]); 对于list, map等其他的容器不适合!!! 那么，我们如何设计适合所有容器的泛型算法呢？ 2.1.2 泛型指针-迭代器 对于不同的容器，各自有这样的泛型指针 则，只需要定义这些对象的（*, !=, ++;