——迭代器


1) 迭代器（Iterator）的介绍：
背景：指针可以用来遍历存储空间连续的数据结构，但是对于存储空间费连续的，就需要寻找一个行为类似指针的类，来对非数组的数据结构进行遍历。
定义：迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。
迭代器（Iterator）是指针（pointer）的泛化，它允许程序员用相同的方式处理不同的数据结构（容器）。
（1）迭代器类似于C语言里面的指针类型，它提供了对对象的间接访问。
（2）指针是C语言中的知识点，迭代器是C++中的知识点。指针较灵活，迭代器功能较丰富。
（3）迭代器提供一个对容器对象或者string对象的访问方法，并定义了容器范围。

2) 迭代器和指针的区别：
容器和string有迭代器类型同时拥有返回迭代器的成员。如：容器有成员begin和end,其中begin成员复制返回指向第一个元素的迭代器，
而end成员返回指向容器尾元素的下一个位置的迭代器，也就是说end指示的是一个不存在的元素，所以end返回的是尾后迭代器。

3) 容器迭代器的使用:
每种容器类型都定义了自己的迭代器类型，如vector：vector< int>:: iterator iter;//定义一个名为iter的变量，数据类型是由vector< int>定义的iterator 类型。
简单说就是容器类定义了自己的iterator类型，用于访问容器内的元素。每个容器定义了一种名为iterator的类型，这种类型支持迭代器的各种行为。

各容器支持的迭代器的类别如下：(只有顺序容器和关联容器支持迭代器遍历)

容器

支持的迭代器类别

说明

vector

随机访问

一种随机访问的数组类型，提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小

deque

随机访问

一种随机访问的数组类型，提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小

list

双向

一种不支持随机访问的数组类型，插入和删除所花费的时间是固定的，与位置无关。

set

双向

一种随机存取的容器，其关键字和数据元素是同一个值。所有元素都必须具有惟一值。

multiset

双向

一种随机存取的容器，其关键字和数据元素是同一个值。可以包含重复的元素。

map

双向

一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。

multimap

双向

一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。

stack

不支持

适配器容器类型，用vector，deque或list对象创建了一个先进后出容器

queue

不支持

适配器容器类型，用deque或list对象创建了一个先进先出容器

priority_queue

不支持

适配器容器类型，用vector或deque对象创建了一个排序队列

如上表所示，迭代器类型主要支持两类，随机访问和双向访问。其中vector和deque支持随机访问，list,set,map等支持双向访问。
1）随机访问：提供了对数组元素进行快速随机访问以及在序列尾部进行快速插入和删除操作。
2）双向访问：插入和删除所花费的时间是固定的，与位置无关。
各个迭代器的功能如下：

迭代器类别

说明

输入

从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列

输出

向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，统一输出迭代器不能两次遍历一个序列

正向

组合输入迭代器和输出迭代器的功能，并保留在容器中的位置

双向

组合正向迭代器和逆向迭代器的功能，支持多遍算法

随机访问

组合双向迭代器的功能与直接访问容器中任何元素的功能，即可向前向后跳过任意个元素


迭代器的操作：(每种迭代器均可进行包括表中前一种迭代器可进行的操作。)

迭代器操作

说明

所有迭代器

p++

后置自增迭代器

++p

前置自增迭代器

输入迭代器

*p

复引用迭代器，作为右值

p=p1

将一个迭代器赋给另一个迭代器

p==p1

比较迭代器的相等性

p!=p1

比较迭代器的不等性

输出迭代器

*p

复引用迭代器，作为左值

p=p1

将一个迭代器赋给另一个迭代器

正向迭代器

提供输入输出迭代器的所有功能

双向迭代器

--p

前置自减迭代器

p--

后置自减迭代器

随机迭代器

p+=i

将迭代器递增i位

p-=i

将迭代器递减i位

p+i

在p位加i位后的迭代器

p-i

在p位减i位后的迭代器

p[i]

返回p位元素偏离i位的元素引用

p<p1

如果迭代器p的位置在p1前，返回true，否则返回false

p<=p1

p的位置在p1的前面或同一位置时返回true，否则返回false

p>p1

如果迭代器p的位置在p1后，返回true，否则返回false

p>=p1

p的位置在p1的后面或同一位置时返回true，否则返回false