STL学习总结之<迭代器>

1 迭代器

迭代器是一种“能够遍历某个序列内的所有元素”的对象。它可以透过与一般指针一致的接口来完成自己的工作。迭代器是一种抽象的概念：任何东西，只要行为类似迭代器，就是一种迭代器。迭代器中“能力”是一个很重要的概念，据此可将迭代器划分成不同的类型。

2 迭代器的类型

迭代器类型	能力	供应者
Input(输入)迭代器	向前读取(read)	istream
Output(输出)迭代器	向前写入(write)	ostream,inserter
Forward迭代器	向前读取和写入
Bidirectional(双向)迭代器	向前和向后读取和写入	list,set,multiset,map,multimap
Random access(随机)迭代器	随机存取，可读取也可写入	vector,deque,string,array

3 Input迭代器

Input迭代器只能一次一个向前读取元素，按此顺序一个个传回元素值。Input的操作行为如下：

表达式	效果
*iter	读取实际元素
iter->member	读取实际元素的成员(如果有的话)
++iter	向前步进(传回新位置)
iter++	向前步进(传回旧位置)
iter1 == iter2	判断两个迭代器是否相等
iter1 != iter2	判断两个迭代器是否不相等
TYPE(iter)	复制迭代器(copy)构造函数

注：

(1) Input迭代器只能读取元素一次，如果复制Input迭代器，并使原Input迭代器和新产生的副本都向前读取，可能会遍历到不同的值(eg3)。几乎所有的迭代器都具备Input迭代器的能力，而且通常更强，纯粹的Input迭代器的一个典型例子是“从标准输入装置读取数据”的迭代器。同一个值不会被读取两次，一旦从输入流读入一个字后(离开input缓冲区)，下次读取时就会传回另一个字。

eg1:

View Code

 1 eg1:
 2 #include<iostream>
 3 #include<iterator>
 4 using namespace std;
 5 int main()
 6 {
 7     istream_iterator<int> test(cin);
 8     istream_iterator<int> test2(test);
 9     cout<<*test<<" "<<*test2<<endl;
10     return 0;
11 }
12 输入：2
13 输出：2  2；

eg2:

View Code

 1 eg2:
 2 #include<iostream>
 3 #include<iterator>
 4 using namespace std;
 5 int main()
 6 {
 7     istream_iterator<int> test(cin);
 8     istream_iterator<int> test2(test);
 9     ++test;
10     cout<<*test<<" "<<*test2<<endl;
11     return 0;
12 }
13 输入： 2  3  4  5
14 输出： 3  2
15 -------------------------------------------------------------------------

eg3:

View Code

 1 eg3:
 2 #include<iostream>
 3 #include<iterator>
 4 using namespace std;
 5 int main()
 6 {
 7     istream_iterator<int> test(cin);
 8     istream_iterator<int> test2(test);
 9     ++test;
10     ++test2;
11     cout<<*test<<" "<<*test2<<endl;
12     return 0;
13 }
14 输入： 2  3  4  5
15 输出： 3  4

(2) 应该尽可能优先选用前置式递增运算操作符(++iter)而不是后置式(iter++)因为前者有更好的性能。

(3) Input迭代器不支持递减操作符。

4 Output迭代器

Output迭代器与Input迭代器相反，其作用是将元素值一个个写入，只能一个一个地赋新值。Output迭代器的操作如下：

表达式	效果
*iter = value	将数值写到迭代器所指位置
++iter	向前步进（传回新位置）
iter++	向前步进（传回旧位置）
TYPE(iter)	复制迭代器(copy构造函数)

注：Output迭代器无需比较操作，无法鉴定Output迭代器是否有效，可做的就是写入、写入再写入。

几乎所有的迭代器都有Output迭代器的功能。纯粹的Output迭代器的一个典型例子就是“将元素写到标准输出装置”的迭代器。如果采用两个Output迭代器写至屏幕，第二个将跟在第一个后面，而不是覆盖第一个字(eg1)。Output的另一个典型的例子是inserters。inserters是将元素插入容器的一种迭代器，如果向它赋予一个新值就是将它安插到容器内。如果写入第二个值，并不会覆盖第一个值，而是将改值安插进去(eg2)。

eg1:

View Code

 1 #include<iostream>
 2 
 3 #include<iterator>
 4 
 5 using namespace std;
 6 
 7  
 8 
 9 int main()
10 
11 {
12 
13          ostream_iterator<int>test1(cout);
14 
15          ostream_iterator<int>test2(test1);
16 
17          cout<<"test1 and test2"<<endl;
18 
19          *test1 = 1;
20 
21          *test2 = 2;
22 
23          cout<<endl;
24 
25          return 0;
26 
27 }
28 
29 输出：
30 
31 test1 and test2
32 
33 12
34 
35 -----------------------------------------------------------------------------

eg2:

View Code

 1 eg2:
 2 
 3 #include<iostream>
 4 
 5 #include<vector>
 6 
 7 #include<iterator>
 8 
 9  
10 
11 using namespace std;
12 
13  
14 
15 void print(vector<int>& ivec)
16 
17 {
18 
19          vector<int>::iterator ibegin=ivec.begin();      
20 
21          for(; ibegin!=ivec.end(); ++ibegin)
22 
23          {
24 
25                    cout<<*ibegin<<" ";
26 
27          }
28 
29          cout<<endl;
30 
31 }
32 
33  
34 
35 int main()
36 
37 {
38 
39          vector<int> ivec;
40 
41          back_insert_iterator<vector<int> > iter(ivec);
42 
43          *iter = 1;
44 
45          print(ivec);
46 
47          *iter = 2;
48 
49          print(ivec);
50 
51          return 0;
52 
53 }
54 
55 输出：
56 
57 1
58 
59 1  2

5 Forward(前向)迭代器

Forward迭代器是Input迭代器和Output迭代器的结合，具有Input迭代器的全部功能和Output迭代器的大部分功能。Forward迭代器的所有操作如下：

表达式	效果
*iter	存取实际元素
iter->member	存取实际元素成员
++iter	向前步进
iter++	向前步进
iter1 == iter2	判断两迭代器是否相等
iter1 != iter2	判断两个迭代器是否不等
TYPE()	产生迭代器(default构造函数)
TYPE(iter)	复制迭代器(copy构造函数)
iter1 = iter2	赋值

和Input迭代器及Output迭代器不同，Forward迭代器能多次指向同一个群集中的同一元素，并能多次处理同一元素。

Output迭代器在写入元素时不用有末端检查，Forward迭代器在存取元素时必须要有末端检查，防止未定义行为的发生。

6 Bidirectional(双向)迭代器

Bidirectional迭代器在Forward迭代器的基础上增加了回头遍历的能力，它支持递减运算操作符，用以一步一步的后退操作。Bidirectional迭代器新增的操作如下：

算式	效果
--iter	步退(传回新位置)
iter--	步退(传回旧位置)

7 Random Access(随机存取)迭代器

Random Access迭代器在Bidirectional迭代器的基础之上再增加随机存取能力。因此它必须提供“迭代器算术运算”。它能加减某个偏移量、能处理距离问题，并运用关系运算符进行比较。Random Access迭代器的新增操作。

算式	效果
iter[n]	存取索引位置为n的元素
iter+=n	向前跳n个元素(如果n是负数,则向后跳)
iter-n	向后跳n个元素(如果n是负数，则向前跳)
iter+n/n+iter	传回iter之后的第n个元素
iter-n	传回iter之前的第n个元素
iter1-iter2	传回iter1和iter2之间的距离
iter1 < iter2	判断iter1是否在iter2之前
iter1 > iter2	判断iter1是否在iter2之后
iter1<= iter2	判断iter1是否不在iter2之后
iter1 >= iter2	判断iter1是否不在iter2之前

8关于Vector、strings迭代器的递增和递减问题

为了保证可移植性，最好不要递增或递减暂时性迭代器，如：sort(++coll.begin(),coll.end());因为，如果迭代器被实作为一般指针则编译会失败，C++不允许修改任何基本型别(包括指针)的暂时值(eg1)。

eg1:

View Code

 1 eg1:
 2 
 3 #include<iostream>
 4 
 5 using namespace std;
 6 
 7 class Test
 8 
 9 {
10 
11 private:
12 
13          int num;
14 
15 public:
16 
17          Test():num(0){}
18 
19          Test& operator ++()
20 
21          {
22 
23                    ++num;
24 
25                    return *this;
26 
27          }
28 
29          friend ostream& operator <<(ostream& out, const Test& test);
30 
31 };
32 
33 int func1()
34 
35 {
36 
37          int a = 5;
38 
39          return a;
40 
41 }
42 
43 int* func2()
44 
45 {
46 
47          int a = 5;
48 
49          return &a;  //E(返回局部变量的地址)
50 
51 }
52 
53  
54 
55 Test func3()
56 
57 {
58 
59          Test test;
60 
61          return test;
62 
63 }
64 
65 ostream& operator <<(ostream& out, const Test& test)
66 
67 {
68 
69          out << test.num;
70 
71 }
72 
73 int main()
74 
75 {
76 
77          cout<<++func1()<<endl;  //A(修改基本型别的临时变量的值)
78 
79          cout<<++func2()<<endl;  //B(修改指针类型的临时变量的值)
80 
81          cout<<++func3()<<endl;  //C(修改自定义型别的临时变量的值)
82 
83          cout<<++(*func2())<<endl;  //D(对临时变量解引用并改变其值)
84 
85  
86 
87          return 0;
88 
89 }

编译结果：

A和B处会报告错误：“++”需要左值。C处不会报错。D处不会报错，因为解引用和下标操作符都会返回左值。E处会有警告：返回局部变量或临时变量地址。

9 迭代器辅助函数

9.1 advance()
advance()可将迭代器的位置增加，增加的幅度由参数决定，也就是使迭代器一次前进(或后退)多个元素。

#include <iterator>

void advance(InputIterator& pos, Dist n)

使名为pos的Input迭代器步进(或步退)n个元素。对Bidirectional迭代器和RandomAccess迭代器而言，n可为负值，表示向后退，对于输入迭代器和输出迭代器n为负数时无操作或行为未定义(eg1)。注：advance()并不检查迭代器是否超过end().

eg1:

View Code

 1 eg1:
 2 
 3 #include<iostream>
 4 
 5 #include<iterator>
 6 
 7 using namespace std;
 8 
 9  
10 
11 int main()
12 
13 {
14 
15          istream_iterator<int>test(cin);
16 
17          cout<<"please input at least 3 nums"<<endl;
18 
19          cout<<"first: "<<*test<<endl;
20 
21          advance(test,2);
22 
23          cout<<"third: "<<*test<<endl;
24 
25          advance(test,-1);
26 
27          cout<<"second: "<<*test<<endl;
28 
29          return 0;
30 
31 }
32 
33 在VS2010下输出:
34 
35 please input at least 3 nums
36 
37 first: 1
38 
39 third: 3
40 
41 second: 3
42 
43 ------------------------------------------------------------------------

9.2 distance()

函数distance()可以用来处理两个迭代器之间的距离:

#include<iterator>

Dist distance(InputIterator pos1, InputIterator pos2)

注：

(1)传回两个Input迭代器pos1和pos2之间的距离。

(2)两个迭代器都必须指向同一个容器

(3)如果不是RandomAccess迭代器，则从pos1开始往前走必须能够到达pos2，也就是说pos2的位置必须与pos1相同或在其后。

(4)返回值Dist的型别由迭代器决定:

iterator_traits<InputIterator>::difference_type

对于non_RandomAccess迭代器而言distance()的性能并不好，应尽力避免，如果想在程序中轻松更换容器型别和迭代器型别，应该用distance();

9.3 iter_swap()

iter_swap()用来交换两个迭代器所指的元素值。

#include<algorithm>

void iter_swap(ForwardIterator1 pos1, ForwardIterator2 pos2)

注：

(1)交换迭代器pos1和pos2所指的值。

(2)迭代器的型别不必相同，但其所指的两个值必须可以相互赋值。

10 迭代器配接器

10.1 Reverse(逆向)迭代器

Reverse迭代器是一种配接器，重新定义递增运算和递减运算，使其行为正好倒置。如果使用这种迭代器，算法将以逆向次序来处理元素。所有标准容器都允许用Reverse迭代器来遍历元素。如：

vector<int> coll;

for_each(coll.begin(),coll.end(),print);//正向

for_each(coll.rbegin(),coll.rend(),print);//逆向

10.2迭代器和Reverse迭代器

可以将一般迭代器转化成一个Reverse迭代器，只要原来的迭代器具有双向移动能力。注意，转换后迭代器的逻辑位置发生了变化(Reverse迭代器的所指实际位置与逻辑位置不同，逻辑位置是实际所指位置的下一个位置)，而迭代器实际所指的位置并没有变化(eg1)。

eg1:

View Code

 1 eg1:
 2 
 3 #include<iostream>
 4 
 5 #include<vector>
 6 
 7 #include<algorithm>
 8 
 9 using namespace std;
10 
11 int main()
12 
13 {
14 
15          vector<int> coll;
16 
17          for(int i=1; i<=9; ++i)
18 
19          {
20 
21                    coll.push_back(i);
22 
23          }
24 
25          vector<int>::iterator pos;
26 
27          pos = find(coll.begin(),coll.end(),5);
28 
29          cout<<"pos: "<<*pos<<endl;
30 
31          vector<int>::reverse_iterator rpos(pos);
32 
33          cout<<"rpos: "<<*rpos<<endl;
34 
35          return 0;
36 
37 }
38 
39 输出：
40 
41 pos: 5
42 
43 rpos: 4

注：pos与rpos所指位置相同，但rpos的逻辑值，即实际要输出的值是4。因为rpos逻辑要输出的值就是4。因为pos离begin()的距离是4，则rpos离rend()的距离也应该是4，而rend()实际所指位置为begin()位置，所以rend()的逻辑位置为begin()的前一个位置，故Reverse迭代器的逻辑位置位于实际位置的前一个位置。(详见《C++标准程序库》中文版P267)

base()函数

base()函数可以将逆向迭代器转换成正常迭代器。像转换为逆向迭代器一样，实际位置维持不动，变化的是逻辑位置。

10.2 Insert(安插型)迭代器

Insert迭代器用来将“赋值新值”操作转换为“安插新值”操作。通过这种迭代器，算法可以执行安插操作，所有的Insert迭代器都隶属于Output迭代器类型。

注：

(1)operator *被实作为一个无实际动作的动作，只是简单地传回*this，所以对于Insert迭代器来说，*pos与pos等价。

(2)赋值操作转化安插操作(eg1)。

(3)递增运算也被实作为一个no-op，也是简单地传回一个*this(eg1)。

eg1:

vector<int> coll;

back_insert_iterator<vector<int> >iter(coll);

*iter = 1;//A

++iter;//可有可无

iter = 2;//B与A等价

---------------------------------------------

Insert迭代器的操作

算式	效果
*iter	无实际操作
iter=value	安插value
++iter	无实际操作(传回iter)
iter++	无实际操作(传回iter)

Insert迭代器的种类

C++标准程序库提供三种Insert迭代器:back inserts, front inserts, general inserts.它们之间的区别在于插入位置，不同的迭代器适用的容器类型存在一些差异，在Insert迭代器初始化时一定要清楚自己所属的容器是哪一种，是否支持对应操作。每一种Insert迭代器都可以由一个对应的便捷函数加以生成和初始化。Insert迭代器的种类如下：

名称	Class	其所调用的函数	便捷生成函数
Back inserter	back_insert_iterator	push_back(value)	back_inserter(cont)
Front inserter	front_insert_iterator	push_front(value)	front_inserter(cont)
General inserter	insert_iterator	insert(pos,value)	inserter(cont)

10.2.1 BackInserters

Back inserters透过成员函数push_back()将一个元素追加到容器尾部。支持的容器有：vector，deque,list,string.

使用方法：

(1) 根据所属容器初始化使用

vector<int> coll;

back_insert_iterator<vector<int> > iter(coll);

*iter=1;//插入元素。

copy(coll.begin(),coll.end(),iter);

(2)利用back_inserter

vector<int>coll;

back_inserter(coll)=3;

copy(coll.begin(),coll.end(),back_inserter(coll));

10.2.2 Front Inserters

Front inserters透过成员函数push_front将一个元素值加在容器头部。支持的容器有：deque和list。

使用方法：

(1)根据所属容器初始化使用

list<int> coll;

front_insert_iterator<list<int> > iter(coll);

*iter=1;

copy(coll.begin(),coll.end(),iter);

(2)利用front_inserter

list<int>coll;

front_inserter(coll)=3;

copy(coll.begin(),coll.end(),front_inserter(coll));

10.2.3 General Inserters

General Inserter根据两个参数而初始化：容器和待安插位置。迭代器内部以待安插位置为参数，调用成员函数insert().General Inserter对所有标准容器都适用，因为所有容器都有insert()成员函数，对于关联式容器，安插位置只是个提示，因为在这两个容器中元素的真正位置视其键值而定。安插完毕后general inserter获得刚刚被安插的那个元素的位置。

使用方法：

(1) 根据使用容器初始化和位置

set<int> coll;

insert_iterator<set<int> >iter(coll,coll.begin());

*iter=1;

copy(coll.begin(),coll.end(),iter);

(2)利用inserter

set<int>coll;

set<int>coll2;

inserter(coll,coll.end())=3;

copy(coll.begin(),coll.end(),inserter(coll2,++coll2.begin());

10.2.4 Stream(流)迭代器

stream迭代器是一种迭代器配接器，通过它可以把stream当成算法的原点和终点，一个istream迭代器可用来从input stream中读取元素，而一个ostream迭代器可以用来对output stream写入元素。

Ostream迭代器

ostream迭代器可以将赋予的值写入output stream中，ostream迭代器将赋值操作转化为operator <<。ostream迭代器的各项操作如下：

算式	效果
ostream_iterator<T>(ostream)	为ostream产生一个ostream迭代器
ostream_iterator<T>(ostream,delim)	为ostream产生一个ostream迭代器，各个元素间以delim为分隔符(delim的类型为const char*)
*iter	无实际操作，传回iter
iter=value	将value写到 ostream(ostream<<value<<delim)
++iter	无实际操作，传回iter
iter++	无实际操作，传回iter

注：产生ostream迭代器时，必须提供一个output stream作为参数，迭代器将会把元素值写到该output stream身上，另一个参数可有可无，是个字符串，被用来作为每一个元素值之间的分隔符。

使用方法：

ostream_iterator<int> intWriter(cout,"\n");

*intWriter = 42;//输出42和换行

intWriter++;//无实际操作。

vector<int>coll;

copy(coll.begin(),coll.end(),ostream_iterator<int>(cout," "));

Istream

istream迭代器用来从input stream读取元素，透过istream迭代器，算法可以从stream中直接读取数据。产生istream迭代器时必须提供一个input stream作为参数，迭代器将从其中读取数据。为例确定读取是否已经到了总点，可以使用一个end-of-stream迭代器，只要有任何一次失败，所有istream迭代器都会变成end-of-stream迭代器，所以每进行一次读取都要和end-of-stream进行一次读取，看看当前迭代器是否仍然合法。istream迭代器的各项操作如下：

算式	效果
istream_iterator<T>()	产生一个end-of-stream迭代器
istream_iterator<T>(istream)	为istream产生一个迭代器
*iter	传回先前读取的值或执行读取任务
iter->member	传回先前读取元素的成员
++iter	读取下一个元素，并传回其位置
iter++	读取下一个元素，并传回迭代器指向前一个元素
iter1==iter2	检查iter1和iter2是否相等
iter1！=iter2	检查iter1和iter2是否不相等

使用方法：

eg1:

istream_iterator<int> intReader(cin);

istream_iterator<int> intReaderEOF;

while(intReader != intReadEOF)

{

cout<<"once: "<<*intReader<<endl;

cout<<"again: "<<*intReader<<endl;

++intReader;

}

输入：

1 2 3 f 4

输出：

once: 1

again: 1

once: 2

again: 2

once: 3

again: 3

---------------------------------------------------------------

eg2:

istream_iterator<string>cinPos(cin);

ostream_iterator<string>coutPos(cout);

while(cinPos != istream_iterator<string>())

{ *coutPos++ = *cinPos++; }

cout<<endl;

----------------------------------------------------------------