模板(八)：泛型迭代器的使用

发表于
  • 一个小程序，使用不同类型迭代器做不同的事
1
2
3
4
5
6
7
// 复制顺序的数据结构
template <class In, class Out>
Out copy(In start, In end, Out dest) {
    while (start != end)
        *dest++ = *start++;
    return dest;
}
  • 调用例子
1
2
3
4
5
6
7
8
9
10
11
12
int main() {
    char* hello = "Hello ";
    char* world = "world";
    char message[15];
    char* p = message;
    p = copy(hello, hello + 6, p);
    p = copy(world, world + 5, p);
    *p = '\0';
    cout << message << endl;
}

迭代器类型

  • 模板参数类型In和Out分别作为输入迭代器和输出迭代器
  • 支持相等(==/!=)比较和++自增操作符(前置/后置)

  • 作为函数的参数被传递、返回、保存在数据结构中等

  • 区别在于各自如何访问迭代器所代表的数据

    • 通过一元操作符*支持间接引用
    • 输入迭代器只需要能读取一个值
    • 输出迭代器只需要能够赋值
    • *out = *in必须按照预想工作，*in = *out则不必

  • 输出迭代器表示定位时都必须给迭代器赋一个值，且只能赋一次

  • 输入迭代器增加到超过某个特定的输入值，那么这个值将再也不能被访问

虚拟序列

  • 创建一个用来读取相同常量值序列的输入迭代器

  • 设置数组的元素为某个特定值(把x的元素都设成0):

1
2
3
4
int x[100];
Constant_iterator c(0);
copy(c, c + 100, x);
  • c的行为类似指向一个无界“数组”的“指针”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Constant_iterator {
public:
    Constant_iterator(int k=0);
    int operator*() const;
    Constant_iterator& operator++();
    Constant_iterator operator++(int);
private:
    int n;
    int count;
    friend int operator==(const Constant_iterator&, const Constant_iterator&);
    friend int operator!=(const Constant_iterator&, const Constant_iterator&);
    friend Constant_iterator operator+(const Constant_iterator&, int);
    friend Constant_iterator operator+(int, const Constant_iterator&);
};

  • 缺省拷贝构造函数和赋值操作符

  • 成员count跟踪产生的值的数量，比较操作符可以判断何时到达“序列”尾部

1
2
3
4
5
Constant_iterator::Constant_iterator(int k=0): n(k) { }
int Constant_iterator::operator*() const {
    return n;
}

  • 构造函数记住迭代器生成的值，解引用(dereference)操作符返回这个值

  • 自增操作符递增遍历过的值的数目的计数

1
2
3
4
5
6
7
8
9
10
Constant_iterator& Constant_iterator::operator++() {
    ++count;
    return *this;
}
Constant_iterator Constant_iterator::operator++(int) {
    Constant_iterator r = *this;
    ++count;
    return r;
}
  • +操作会把int对象增加增加到计数中，类似“哨岗”
1
2
3
4
5
6
7
8
9
Constant_iterator operator+(const Constant_iterator& p, int n) {
    Constant_iterator r = p;
    r.count += n;
    return r;
}
Constant_iterator operator+(int n, const Constant_iterator& p) {
    return p + n;
}
  • 当且仅当两个迭代器生成相同数量的值并且这些值都相等时这两个迭代器才相等
1
2
3
4
5
6
7
int operator==(const Constant_iterator& p, const Constant_iterator& q) {
    return p.count == q.count && p.n == q.n;
}
int operator!=(const Constant_iterator& p, const Constant_iterator& q) {
    return !(p == q);
}

  • 创建了一个迭代器，表示包含相等值的“虚拟数组”(实际上并不存在)

  • 可以创建类似的起点和步长固定的迭代器

输出流迭代器

  • 定义一个可以把值打印出来的输出迭代器(类ostream_iterator的一个对象)

  • ostream_iterator<int> out(cout)

    • *out++ = x; 打印x到cout上

  • ostream_iterator类设计构造函数设计为接受两个参数: ostream对象和const char*对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T>
class ostream_iterator {
public:
    ostream_iterator(ostream& os, const char* s): strm(&os), str(s) { }
    ostream_iterator& operator++() {
        return *this;
    }
    ostream_iterator& operator++(int) {
        return *this;
    }
    ostream_iterator& operator*() {
        return *this;
    }
    ostream_iterator& operator=(const T& t) {
        *strm << t << str;
        return *this;
    }
private:
    ostream* strm;
    const char* str;
};
  • 用例: 将42重复10次打印到标准输出上
1
2
3
4
5
6
int main() {
    ostream_iterator<int> oi(cout, " \n");
    Constant_iterator c(42);
    copy(c, c + 10, oi);
}

输入流迭代器

  • 创建一个从某个istream中取值的输入迭代器

    • 输入迭代器必须实现比较操作以判断是否到达文件尾部
    • 进行尝试性地读取才能判断是否已经到达文件尾部，而读取值很耗费系统资源

  • “惰性读取”策略

    • 每个istream_iterator对象有一个只能容纳一个元素的缓冲区和一个表明缓冲区是否已满的标志
    • 另一个标志说明是否到达文件尾部
1
2
3
4
5
6
7
8
9
template <class T>
class istream_iterator {
private:
    T buffer;
    istream* strm;
    int full;
    int eof;
    // ...
};
  • 当且仅当buffer内有一个有用值时full为true
1
2
3
4
5
6
7
template <class T>
class istream_iterator {
public:
    istream_iterator(istream& is): strm(&is), full(0), eof(0) { }
    istream_iterator(): strm(0), full(0), eof(1) { }
    // ...
};
  • 可以使用缺省的复制操作
  • 自增操作符: 确保一旦迭代器遍历过一个值之后不会再读取这个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T>
class istream_iterator {
public:
    istream_iterator& operator++() {
        full = 0;
        return *this;
    }
    istream_iterator operator++(int) {
        istream_iterator r = *this;
        full = 0;
        return r;
    }
    // ...
};

  • 必须预读以便判断是否到达文件尾部

  • 惰性计算策略，首先检查是否需要输入，若需要则读取数据并适当地设置状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
class istream_iterator {
private:
    void fill() {
        if (!full && !eof) {
            if (*strm >> buffer)
                full = 1;
            else 
                eof = 1;
        }
    }
public:
    T operator*() {
        fill();
        assert(full);
        return buffer;
    }
    // ...
};
  • 只有当两个istream_iterator是同一个对象或者两者都处于文件尾部时才相等
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
int operator==(istream_iterator<T>& p, istream_iterator<T>& q) {
    if (p.eof && q.eof) return 1;
    if (!p.eof && !q.eof) return &p == &q;
    p.fill();
    q.fill();
    return p.eof == q.eof;
}
template <class T>
int operator!=(istream_iterator<T>& p, istream_iterator<T>& q) {
    return !(p == q);
}
  • 将一个输入文件复制值到一个输出文件中去
1
2
3
4
5
6
7
int main() {
    ostream_iterator<int> output(cout, " \n");
    istream_iterator<int> input(cin);
    istream_iterator<int> eof;
    copy(input, eof, output);
}

Summary

  • 看上去像指针的结构，容易被设想成仅仅是一个指针

  • 深入研究某个算法使用到的指针操作会发现可以针对其他的数据结构模拟指针

  • istream_iterator和ostream_iterator类标准模板库的组成部分

    • 而Constan_iterator不是(首字母大写)

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