模板(九)：迭代器配接器

发表于

迭代器配接器(iterator adaptor): 把迭代器作为参数并转换为其他迭代器的模板

例子

  • 一个泛型函数: 找出第一次出现某个值的位置
1
2
3
4
5
6
template <class T, class X>
T find(T start, T beyond, const X& x) {
    while (start != beyond && *start != x)
        ++*start;
    return start;
}

  • 普通指针可以充当输入迭代器

  • 找出最后一个与某个特定值相等的实例

1
2
3
4
5
6
7
8
9
10
template <class T, class X>
T find(T start, T beyond, const X& x) {
    T result = beyond;
    while (start != beyond) {
        if (*start == x) 
            result = start;
        ++start;
    }
    return result;
}
  • T是输入迭代器，只能这样实现

  • 缺陷: 总是需要查找数据结构中的所有元素，即使要查找的值就在尾部

  • 采用双向迭代器: 可以使用--操作符

1
2
3
4
5
6
7
8
9
10
template <class T, class X>
T rfind(T start, T beyond, const X& x) {
    if (start != beyond) {
        T p = beyond;
        do {
            if (*--p == x) return p;
        } while (p != start)
    }
    return beyond;
}

方向不对称性

  • 反转某个算法的方向时并不能总是精确地保持原有的对称性

    • Cplusplus语言定义的迭代器的特性: 通常迭代器确保逾尾值有效但对超出头部的值没有相应的保障
1
2
for (int* p = a; p < a + 10; ++p)
    *p = 0;
  • 循环结束时p等于a+10
    • C/Cpp语言保证(且只保证)能够定位任何超出数组尾部之后的那一个元素的地址
    • a+10是合法的，a+11是非法的，a-1是非法的
1
2
3
4
5
6
7
8
// 无效的代码
for (int* p = a+9; p >= a; p--)
    *p = 0;
// 有效的代码
int* p = a + 10;
while (p > a)
    *--p = 0;

一致性和不对称性

  • 后向查找不到时返回超出头部的指针

  • 每个迭代器指向数据结构中正要查找的元素的后面的位置

  • rnfind(reverse neighbor find): 

1
2
3
4
5
6
template <class T, class X>
T rnfind(T start, T beyond, const X& x) {
    while (beyond != start && beyond[-1] != x)
        --beyond;
    return beyond;
}
  • beyond[-1] : *(beyond-1)
    • T必须是一个随机存取迭代器而不仅仅是双向迭代器

自动反向

  • 新类型TR(T reverse): 将T转换为TR，指向T所指向的元素的前一个元素
  • 迭代器适配器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class It, class T>
class Rev {
    friend bool operator==(const Rev<It, T>, const Rev<It, T>);
    friend bool operator!=(const Rev<It, T>, const Rev<It, T>);
public:
    Rev();
    Rev(It i);
    operator It();
    Rev<It, T>& operator++();
    Rev<It, T>& operator--();
    Rev<It, T>& operator++(int);
    Rev<It, T>& operator--(int);
    T& operator*();
};
  • 解引用操作实际发生在私有数据成员所指向元素的前一个元素
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
template <class It, class T>
class Rev {
    friend bool operator==(const Rev<It, T>, const Rev<It, T>);
    friend bool operator!=(const Rev<It, T>, const Rev<It, T>);
public:
    Rev() { }
    Rev(It i): it(i) { }
    operator It() {
        return it;
    }
    Rev<It, T>& operator++() {
        --it;
        return *this;
    }
    Rev<It, T>& operator--() {
        ++it;
        return *this;
    }
    Rev<It, T>& operator++(int) {
        Rev<It, T> r = *this;
        --it;
        return r;
    }
    Rev<It, T>& operator--(int) {
        Rev<It, T> r = *this;
        ++it;
        return r;
    }
    T& operator*() {
        It i = it;
        --i;
        return *i;
    }
private:
    It it;
};
template <class It, class T>
bool operator==(const Rev<It, T>& x, const Rev<It, T>& y) {
    return x.it == y.it;
}
template <class It, class T>
bool operator!=(const Rev<It, T>& x, const Rev<It, T>& y) {
    return x.it != y.it;
}
  • 可以通过与迭代器相关联的容器，将一个双向迭代器由前向遍历迭代器转变为后向遍历迭代器
1
2
3
4
typedef Rev<int*, int> R
int* p = find(x, x+100, 42);
R r = find(R(x+100), R(x), 42);

Summary

  • 取决于描述数据结构的双向迭代器的可用性

  • 编写进行接口适配的模板

  • STL的更通用的模板: reverse_bidirectional_iterator

  • 随机存取迭代器: 可以使用reverse_iterator

  • 迭代器配接器的其他应用

    • 边界检查配接器
    • 被生成的迭代器类型可以将源迭代器的值限定在由创建该类型的对象时确定的一对边界中

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