1994年7月,安大略基奇纳召开的C++标准会议
通过Alex Stepanov提出的提议:
将他和他的同事们在Hewlett-Packard实验室开发的一系列泛型算法作为一部分收录到标准C++库中
标准模板库(Standard Template Library, STL)
泛型算法: 一种以对它所作用的数据结构尽可能少的假设的方式表达的算法
模板使某种程度的泛型(genericity)更加容易
编写与所排序的值的类型无关的程序的一种典型方法
|
|
- STL库中,某个程序表述的算法既能够使用多种数据结构有能获得高效的运行(与为单个类型设计的手写代码一样快)
- 与內建类型结合的非常好
一个特例
- 找到整数数组中的第一个等于某个给定值的元素
|
|
- 必须知道的情况:
- 正在查找的某个类型为int的值
- 正在一个int对象数组中查找
- 已经预先知道数组中元素的数目
- 知道第一个元素的地址
尽可能去除假设条件提高算法通用性(泛型化)
泛型化元素类型
- 采用模板去除对int的依赖性(前两个要求)
|
|
const T& x
:- 复制一个类型位置的对象的代价可能很昂贵
- T对象甚至不允许复制(私有的拷贝构造函数)
可以用find2处理任何支持
operator==
的数据结构
推迟计数
抽象数据存储方面的信息: 生成一个搜索数组或者链表、文件的函数
- 避免必须预先知道有多少个元素
- 通用性越好的数据结构预先计算元素个数的代价就越昂贵
接受指向第一个元素和最后一个元素的两个指针
- 直接引用最后一个元素是很危险的: 根本没有元素存在,指向最后一个元素的指针在指向第一个元素之前
- 将指向位于最后一个元素之后的元素的指针作为参数
|
|
- 使用
!=
而不是<
: 以后替代指针的类型可能能够很好定义!=
而不能定义<
对指针所作假设 : 可以把0转换成一个与其他所有的值不同的指针值(return 0)
改进: 找不到元素返回一个beyond而不是0
|
|
- 简化代码
|
|
地址独立性
程序仍依赖传入的指针(指向要查找的数据的开头)
但只依赖于指针的某些保留特性
- 把指针当作参数接受,作为结构返回
- 可以比较指针相不相等
- 解引用(dereference)指针得到一个值: *p
- 递增指针以指向下一个元素
传入的指针可以用满足以上特性但非內建指针的类型替换
|
|
- 变得更通用
查找非数组
- 一个包含类String的元素的单向链表(不成熟的实现):
|
|
- 找出包含某个特定值的结点:
|
|
- 定义辅助类可以调用用find6
|
|
- 可以直接调用find6:
find6(Nodep(p), Nodep(0), x);
Summary
- Nodep结构使任何泛型算法都能够运用到正在使用特定链表结构中
- 即使泛型算法的设计者从没见过这个链表结构
任何实际的列表类都有一个配套的迭代器类
《C++沉思录(Cplusplus Thinking)》笔记