模板(三)：迭代器

发表于

迭代器

  • 已经定义Array<T>, Pointer<T>和Ptr_to_const<T>使得能部分确保安全性，避免使用指针

  • 进一步取代指针，需实现加法、减法和关系运算符

1
2
3
4
5
6
7
void f() {
    int a[10];
    int* pa = a;
    int* end = pa + 10;
    while (pa != end)
        *pa++ = 0;
}
  • 基类及派生类都要定义这些操作
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
template <class T> class Pointer: public Ptr_to_const<T> {
public:
    Pointer& operator++() {
        ++sub;
        return *this;
    }
    Pointer& operator--() {
        --sub;
        return *this;
    }
    Pointer& operator++(int) {
        Pointer ret = *this;
        ++sub;
        return ret;
    }
    Pointer& operator--(int) {
        Pointer ret = *this;
        --sub;
        return ret;
    }
    Pointer& operator+=(int n) {
        sub += n;
        return *this;
    }
    Pointer& operator-=(int n) {
        sub -= n;
        return *this;
    }
    // ...
};
template <class T> Pointer<T> operator+(const Pointer<T>& p, int n) {
    Pointer<T> ret = p;
    return ret += n;
}
template <class T> Pointer<T> operator+(int n, const Pointer<T>& p) {
    Pointer<T> ret = p;
    return ret += n;
}
// subtration is similar
  • 两个指针当且仅当指向同一个Array的同一个元素(或都不指向任何Array)时才相等
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
int operator==(const Ptr_to_const<T>& op1, cosnt Ptr_to_const<T>& op2) {
    if (op1.ap != op2.ap)
        return 0;
    return (op1.sub == op2.sub);
}
template <class T>
int operator<(const Ptr_to_const<T>& op1, const Ptr_to_const<T>& op2) {
    if (op1.ap != op2.ap)
        throw "< on different Arrays";
    return op1.sub < op2.sub;
}
  • 迭代器能在不暴露容器内部结构的情况下访问容器的元素

删除元素

当元素不存在时的处理方法

  • 禁止从容器中删除单个元素(可以删除整个容器)

  • 在每个容器对象中保存一个有效迭代器的列表，删除一个元素则正好删除刚好指向这个
    被删除元素的迭代器

  • 对容器中每个元素采用引用计数，删除任何一个元素都必须等到最后一个指向该元素的
    引用都不存在

  • 让迭代器指向容器中元素与元素之间的位置上(难以实现；影响先有代码)

删除容器

容器本身已不存在，还有活动的迭代器的解决方法

  • 删除操作延后到最后一个迭代器失效

  • 采用处理删除单个元素的思想

  • 用户确保一旦容器删除就不再使用迭代器

  • 只要有活动迭代器存在就禁止删除容器本身

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