模板(六)：抽象接口

发表于

1994年7月，安大略基奇纳召开的C++标准会议
通过Alex Stepanov提出的提议:
将他和他的同事们在Hewlett-Packard实验室开发的一系列泛型算法作为一部分收录到标准C++库中
标准模板库(Standard Template Library, STL)

  • 泛型算法: 一种以对它所作用的数据结构尽可能少的假设的方式表达的算法

  • 模板使某种程度的泛型(genericity)更加容易

  • 编写与所排序的值的类型无关的程序的一种典型方法

1
2
3
4
template <class T>
void sort(T* ptr, int size) {
    // ....
}
  • STL库中，某个程序表述的算法既能够使用多种数据结构有能获得高效的运行(与为单个类型设计的手写代码一样快)
  • 与內建类型结合的非常好

一个特例

  • 找到整数数组中的第一个等于某个给定值的元素
1
2
3
4
5
6
7
8
const int* find1(const int* array, int n, int x) {
    const int* p = array;
    for (int i = 0; i < n; i++) {
        if (*p == x) return p;
        ++p;
    }
    return 0;
}
  • 必须知道的情况:
    • 正在查找的某个类型为int的值
    • 正在一个int对象数组中查找
    • 已经预先知道数组中元素的数目
    • 知道第一个元素的地址

  • 尽可能去除假设条件提高算法通用性(泛型化)

泛型化元素类型

  • 采用模板去除对int的依赖性(前两个要求)
1
2
3
4
5
6
7
8
9
template <class T>
T* find2(T* array, int n, const T& x) {
    T* p = array;
    for (int i = 0; i < n; i++) {
        if (*p == x) return p;
        ++p;
    }
    return 0;
}
  • const T& x:
    • 复制一个类型位置的对象的代价可能很昂贵
    • T对象甚至不允许复制(私有的拷贝构造函数)

  • 可以用find2处理任何支持operator==的数据结构

推迟计数

抽象数据存储方面的信息: 生成一个搜索数组或者链表、文件的函数

  • 避免必须预先知道有多少个元素
    • 通用性越好的数据结构预先计算元素个数的代价就越昂贵

  • 接受指向第一个元素和最后一个元素的两个指针

    • 直接引用最后一个元素是很危险的: 根本没有元素存在，指向最后一个元素的指针在指向第一个元素之前
    • 将指向位于最后一个元素之后的元素的指针作为参数
1
2
3
4
5
6
7
8
9
template <class T>
T* find3(T* array, T* beyond, const T& x) {
    T* p = array;
    while (p != beyond) {
        if (*p == x) return p;
        ++p;
    }
    return 0;
}
  • 使用!=而不是< : 以后替代指针的类型可能能够很好定义!=而不能定义<

  • 对指针所作假设 : 可以把0转换成一个与其他所有的值不同的指针值(return 0)

  • 改进: 找不到元素返回一个beyond而不是0

1
2
3
4
5
6
7
8
9
template <class T>
T* find4(T* array, T* beyond, const T& x) {
    T* p = array;
    while (p != beyond) {
        if (*p == x) return p;
        ++p;
    }
    return beyond;
}
  • 简化代码
1
2
3
4
5
6
7
template <class T>
T* find5(T* array, T* beyond, const T& x) {
    T* p = array;
    while (p != beyond && *p != x)
        ++p;
    return beyond;
}

地址独立性

  • 程序仍依赖传入的指针(指向要查找的数据的开头)

  • 但只依赖于指针的某些保留特性

    • 把指针当作参数接受，作为结构返回
    • 可以比较指针相不相等
    • 解引用(dereference)指针得到一个值: *p
    • 递增指针以指向下一个元素

  • 传入的指针可以用满足以上特性但非內建指针的类型替换

1
2
3
4
5
6
template <class P, class T>
T* find6(P array, P beyond, const T& x) {
    while (start != beyond && *start != x)
        ++start;
    return start;
}
  • 变得更通用

查找非数组

  • 一个包含类String的元素的单向链表(不成熟的实现):
1
2
3
4
struct Node {
    String value;
    Node* next;
}
  • 找出包含某个特定值的结点:
1
2
3
4
5
Node* listfind(Node* p, const String& x) {
    while (p && *p != x)
        p = p->next;
    return p;
}
  • 定义辅助类可以调用用find6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Nodep {
public:
    Nodep(Node* p): pt(p) { }
    String& operator*() {
        return pt->value;
    }
    void operator++() {
        pt = pt->next;
    }
    friend int operator==(const Nodep&, const Nodep&);
    friend int operator!=(const Nodep&, const Nodep&);
    operator Node*() {
        return pt;
    }
private:
    Node* pt;
}
int operator==(const Nodep& p, const Nodep& q) {
    return p.pt == q.pt;
}
int operator!=(const Nodep& p, const Nodep& q) {
    return p.pt != q.pt;
}
  • 可以直接调用find6: find6(Nodep(p), Nodep(0), x);

Summary

  • Nodep结构使任何泛型算法都能够运用到正在使用特定链表结构中
    • 即使泛型算法的设计者从没见过这个链表结构

任何实际的列表类都有一个配套的迭代器类

《C++沉思录(Cplusplus Thinking)》笔记