ACM/ICPC竞赛

第05篇 ACM/ICPC竞赛之STL--iterator简介

iterator(迭代器)是用于访问容器中元素的指示器，从这个意义上说，iterator(迭代器)相当于数据结构中所说的“遍历指针”，也可以把iterator(迭代器)看作是一种泛化的指针。

STL中关于iterator(迭代器)的实现是相当复杂的，这里我们暂时不去详细讨论关于iterator(迭代器)的实现和使用，而只对iterator(迭代器)做一点简单的介绍。

简单地说，STL中有以下几类iterator(迭代器)：

输入iterator(迭代器)，在容器的连续区间内向前移动，可以读取容器内任意值；
输出iterator(迭代器)，把值写进它所指向的容器中；
前向iterator(迭代器)，读取队列中的值，并可以向前移动到下一位置(++p,p++)；
双向iterator(迭代器)，读取队列中的值，并可以向前向后遍历容器；
随机访问iterator(迭代器), 可以直接以下标方式对容器进行访问，vector的iterator(迭代器)就是这种iterator(迭代器)；
流iterator(迭代器)，可以直接输出、输入流中的值；
每种STL容器都有自己的iterator(迭代器)子类，下面先来看一段简单的示例代码：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     vector<int> s;
 9     for (int i=0; i<10; i++) s.push_back(i);
10     for (vector<int>::iterator it=s.begin(); it!=s.end(); it++) 
11         cout << *it << " ";
12     cout << endl;
13     return 0;
14 }

vector的begin()和end()方法都会返回一个vector::iterator对象，分别指向vector的首元素位置和尾元素的下一个位置（我们可以称之为结束标志位置）。

对一个iterator(迭代器)对象的使用与一个指针变量的使用极为相似，或者可以这样说，指针就是一个非常标准的iterator(迭代器)。

再来看一段稍微特别一点的代码：

 1 #include <iostream>
 2 #include <vector>
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     vector<int> s;
 9     s.push_back(1);
10     s.push_back(2);
11     s.push_back(3);
12     copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
13     cout <<endl;
14     return 0;
15 }

这段代码中的copy就是STL中定义的一个模板函数，copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));的意思是将由s.begin()至s.end()(不含s.end())所指定的序列复制到标准输出流cout中，用" "作为每个元素的间隔。也就是说，这句话的作用其实就是将表中的所有内容依次输出。

iterator(迭代器)是STL容器和算法之间的“胶合剂”，几乎所有的STL算法都是通过容器的iterator(迭代器)来访问容器内容的。只有通过有效地运用iterator(迭代器)，才能够有效地运用STL强大的算法功能。

未完待续、。，