【C++】泛型算法（二）泛型指针Iterator（迭代器）

迭代器iterator定义

• 迭代器是一种检查容器内元素并遍历元素的数据类型；
• 迭代器提供一个对容器对象或者string对象的访问方法，并定义了容器范围；
• 迭代器的使用可以提高编程的效率。

其定义应该提供：

1. 迭代对象（某个容器）的类型，用来决定如何访问下一个元素；

2. iterator所指的元素类型，决定iterator提领操作的返回值；

区别迭代器iterator和指针pointer

1. 指针可以用来遍历存储空间连续的数据结构，但对于存储空间非连续的，就需要寻找一个行为类似指针的类，来对非数组的数据结构进行遍历；
2. 迭代器是指针的泛化，它允许程序员用相同的方式处理不同的数据结构（容器）。

//每种容器类型都定义了自己的迭代器类型，用于访问容器内的元素
//定义方法：容器类名::iterator 迭代器名

vector<string>::iterator iter = svec.begin();

//iter被定义为一个iterator，指向一个vector
//元素类型是string，初值指向svec的第一个元素。 
1
2
3
4
5
6
7

常用迭代器类型

• 如上图所示，迭代器类型主要支持两类，随机访问和双向访问：
  其中vector和deque支持随机访问，list,set,map等支持双向访问。

1. 随机访问：提供了对数组元素进行快速随机访问以及在序列尾部进行快速插入和删除操作。
2. 双向访问：插入和删除所花费的时间是固定的，与位置无关。

参考：C++迭代器（Iterator）详解

使用示例

vector

#include 
#include 
 
using namespace std;
 
int main(int argc, char* argv[])
{
	vector<int> vecTemp;
	for (int i = 0; i<6; i++)
	{
		vecTemp.push_back(i);
	}
	cout <<"Original deque: ";    
	vector<int>::iterator it;
	for (it = vecTemp.begin(); it!=vecTemp.end(); it++)
	{
		cout <<*it <<" ";
	}
 
	return 0;
}
 

/*
输出结果：
Original deque: 0 1 2 3 4 5
*/
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

deque

#include 
#include 
 
using namespace std;
 
int main(int argc, char* argv[])
{
	deque<int> dequeTemp;
	for (int i = 0; i<6; i++)
	{
		dequeTemp.push_back(i);
	}
	cout <<"Original deque: ";
	deque<int>::iterator it;
	for (it = dequeTemp.begin(); it != dequeTemp.end(); it++)
	{
		cout <<*it <<" ";
	}
	cout <<endl;
 
	return 0;
}
 
/*
输出结果：
Original deque: 0 1 2 3 4 5
*/
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

list

#include 
#include 
 
using namespace std;
 
int main(int argc, char* argv[])
{
	list<int> listTemp;
	for (int i = 0; i<6; i++)
	{
		listTemp.push_back(i);
	}
	cout << "Original list: ";
	list<int>::iterator it;
	for (it = listTemp.begin(); it != listTemp.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
 
	list<int>::iterator itStart = listTemp.begin();
	listTemp.insert(itStart,5,9);
 
	cout << "Result of list: ";
	for (it = listTemp.begin(); it != listTemp.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
 
	return 0;
}
 
/*
输出结果：
Original list: 0 1 2 3 4 5
Result of list: 9 9 9 9 9 0 1 2 3 4 5
*/
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

set

#include 
#include 
 
using namespace std;
 
int main(int argc, char* argv[])
{
	set<char> setTemp;
	for (int i = 0; i<6; i++)
	{
		setTemp.insert('F'-i);
	}
	cout <<"Original set: ";
	set<char>::iterator it;
	for (it = setTemp.begin(); it != setTemp.end(); it++)
	{
		cout <<*it <<" ";
	}
	cout <<endl;
 
	return 0;
}

/*
输出结果：
Original set: A B C D E F
*/
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

map

#include 
#include 
 
using namespace std;
 
typedef map<int, char> MyMap;
 
int main(int argc, char* argv[])
{
	MyMap mapTemp;
	for (int i = 0; i<6; i++)
	{
		mapTemp[i] = ('F'-i);
	}
	cout <<"Original map: " <<endl;
	MyMap::iterator it;
	for (it = mapTemp.begin(); it != mapTemp.end(); it++)
	{
		cout << (*it).first << " --> ";
		cout << (*it).second << std::endl;
	}
	cout <<endl;
 
	return 0;
}

/*
输出结果：
Original map:
0 --> F
1 --> E
2 --> D
3 --> C
4 --> B
5 --> A
*/
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

参考：C++ STL 迭代器（iterator）详解