模板(七)：泛型迭代器

发表于
  • 了解其他的算法，分析各自对相应模板参数类型强加的行为
  • 区分各类不同的泛型算法所要求的不同泛型迭代器

一个不同的算法

  • 颠倒一个序列中的所有元素的顺序
1
2
3
4
5
6
7
8
9
10
11
// 不是很正确
template <class P, class T>
void reverse(P start, P beyond) {
    while (start < beyond) {
        T t = *start;
        --beyond;
        *start = *beyond;
        *beyond = t;
        ++start;
    }
}
  • 需要定义++p, p != beyond和*p

  • 需要定义p < beyond和``–p

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    - 比较难以保证: ``p < beyond``
    - - 判断两个值是否相等和判断两者的先后次序之间存在很大的差别
    - - 例如 在一个单向链表之中
    - 用 ``p != beyond`` 替换 ``p < beyond``
    ```C++
    template <class P, class T>
    void reverse2(P start, P beyond) {
        while (start != beyond) {
            --beyond;
            if (start != beyond) {
                T t = *start;
                *start = *beyond;
                *beyond = t;
                ++start;
            }
        }
    }

  • 用两个(不)等于检查替换了一个次序检查

    • 输入有效的前提下，start与beyond不会擦肩而过

  • 双重检查消耗资源，但所耗不多，且使得该算法能在更多种类的数据结构中使用

  • 考虑对类型P的递减操作要求

  • 两种方法不用递减(辅助存储区、开销大)
    • 分配一个辅助的T数组，把数据复制到这个数组中，按逆序复制回去
    • 分配一个辅助的P数组

需求的分类

  • 针对不同算法，可行的数据结构面临的问题不同
    • 在一个不同向后读取(逆向读取)的顺序文件中找出一条特定的记录，支持operator--的要求显得过于苛刻

  • 不能对不同目标使用同一套需求

  • 必须对需求进行适当的分类: 找出一套能很好的适合某个算法集的需求以及另一套适合另一个算法集的需求

输入迭代器

  • 一个对象希望完全模拟指向序列的指针，能够使用p取出序列元素，使p指向序列下一个元素，能够判断是否到达最后一个元素
    • 需要*p, ++P, p != q
    • p++, p == q
    • 复制p

  • 满足这些需求的类型允许按照某个预先规定的顺序读(但不是写)序列中的元素

    • 输入迭代器(input iterator): 一类迭代器

输出迭代器

可以读取一个序列，能够对该序列进行读写操作

  • 输出迭代器

  • 输入迭代器和输出迭代器之间的唯一区别在*p的行为

    • 输入迭代器可以读取但不一定允许修改
    • 输出迭代器允许改变但不一定允许读取(p在改变前定位的存储空间可能包括一个不能被合法复制的无效值)

  • 使用输入和输出迭代器可以写出泛型复制函数

1
2
3
4
5
6
7
8
template <class In, class Out>
void copy(In start, In beyond, Out result) {
    while (start != beyond) {
        *result = *start;
        ++result;
        ++start;
    }
}
  • 精简版
1
2
3
4
5
template <class In, class Out>
void copy(In start, In beyond, Out result) {
    while (start != beyond)
        *result++ = *start++;
}

前向迭代器

能够遍历序列的元素，以某种方式改变每个元素，一旦接触某个元素之后就再也不能访问这个元素

  • 将输入迭代器和输出迭代器的操作结合在一起的迭代器

  • 前向迭代器(forward iterator)

1
2
3
4
5
6
7
template <class Iter, class Function>
void apply(Iter start, Iter beyond, Function f) {
    while (start != beyond) {
        *start = f(*start);
        ++start;
    }
}
  • 使用*start进行读取和写入: 前向迭代器
  • 类型Function: 可以使任何能够像函数一样运行的对象的类型
    • 函数对象: 重载了函数调用操作符operator()

双向迭代器

  • 支持operator--

随机存取迭代器

  • p指向序列第一个元素，到达第1000个元素的方式
    • 执行1000次++p？
    • p += 1000
    • p指向数组元素或者行为类似于指向链表元素的指针的类
    • 可能简单方便而效率极差

  • 有些算法必须能够高效访问数据结构的任何元素，如折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class P, class X>
P binsearch(P start, P beyond, X x) {
    P low = start, high = beyond;
    while (low != high) {
        P mid = low + (high - low) / 2;
        if (x == *mid)
            return mid;
        if (x < *mid)
            high = mid;
        else
            low = mid + 1;
    }
    return beyond;
}

  • 关键是能够快速计算指向某个序列中间元素的指针

  • 随机访问迭代器增加了操作：+, -, +=, -=和[]

是否用继承关联

  • 前向迭代器能作为输入迭代器或者输出迭代器工作
  • 双向迭代器能像前向迭代器、输入迭代器和输出迭代器一样工作

  • 随机访问迭代器可以像任何其他的迭代器一样工作

  • 但是迭代器不属于继承这种关联类型的范畴

    • 一系列类型应该满足或者不应该满足的需求的集合

  • 继承增加了更多地需求

    • 一个特殊的基类
    • 迭代器必须是类而不是內建类型(不能把指针当作迭代器使用了)

  • 概念继承(conceptual inheritance): 构建C++库的概念框架的一部分

性能

  • 效率是使用C++的原因之一
  • STL赋予迭代器 强的性能要求: 特定类型的迭代器要支持的每种操作都要快(分摊执行时间必须是O(1))

Summary

泛型算法: 对于所操作数的数据结构的细节信息只加入最低限度的了解

  • 将用来访问数据结构的类型分类

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