【C++ STL迭代器】iterator

• 背景
  • 我们知道，尽管不同容器的内部结构各异，但它们本质上都是用来存储大量数据的，换句话说，都是一串能存储多个数据的存储单元。因此，诸如数据的排序、查找、求和等需要对数据进行遍历的操作方法应该是类似的。
  • 既然类似，完全可以利用泛型技术，将它们设计成适用所有容器的通用算法，从而将容器和算法分离开。但实现此目的需要有一个类似中介的装置，它除了要具有对容器进行遍历读写数据的能力之外，还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据。
  • 这是泛型思维发展的必然结果，于是迭代器就产生了。简单来讲，迭代器和 C++ 的指针非常类似，它 可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

【 1. 迭代器的属性 】

• 常用的迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器 5 种。
• 输入迭代器和输出迭代器
  比较特殊，它们不是把数组或容器当做操作对象，而是 把输入流/输出流作为操作对象。
• 前向迭代器（forward iterator）
  假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较 。此外，两个正向迭代器可以互相赋值。
• 双向迭代器（bidirectional iterator）
  双向迭代器 具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则 还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。
• 随机访问迭代器（random access iterator）
  随机访问迭代器 具有双向迭代器的全部功能 。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
  • p+=i：使得 p 往后移动 i 个元素。
  • p-=i：使得 p 往前移动 i 个元素。
  • p+i：返回 p 后面第 i 个元素的迭代器。
  • p-i：返回 p 前面第 i 个元素的迭代器。
  • p[i]：返回 p 后面第 i 个元素的引用。
  • 此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。

【 2. 不同容器支持的迭代器 】

• STL 标准库为每一种标准容器定义了一种迭代器类型，这意味着，不同容器对应的迭代器不同，其功能强弱也有所不同（容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法）。不同容器对应的迭代器类型如下所示：

容器适配器 stack 和 queue 没有迭代器，它们包含有一些成员函数，可以用来对元素进行访问。

【 3. 迭代器的定义方式 】

• 尽管不同容器对应着不同类别的迭代器，但这些迭代器有着较为统一的定义方式：

• 定义以上几种迭代器后，就可以读取它指向的元素： *迭代器名 就表示迭代器指向的元素。
• 常量迭代器和非常量迭代器的区别：
  通过非常量迭代器还能修改其指向的元素。
• 反向迭代器和正向迭代器的区别：
  • 对 正向迭代器进行 ++操作 时，迭代器会 指向容器中的后一个元素；
  • 对 反向迭代器进行 ++操作 时，迭代器会 指向容器中的前一个元素。
• 注意，以上 4 种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上 4 种方式，比如 array、deque、vector；而有些容器只支持其中部分的定义方式，例如 forward_list 容器只支持定义正向迭代器，不支持定义反向迭代器。

【 4. 实例 】

4.1 定义方式：正向迭代器和反向迭代器

• 以 vector容器 为例，实现正向迭代器和反向迭代器这两种定义方式。

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    vector <int> vec = {1, 2,3, 4 ,5};
    //正向迭代器
    vector <int>::iterator t1;
    for (t1 = vec.begin(); t1 != vec.end(); ++t1)
        cout << *t1 << " ";
    cout << endl;
    
    //反向迭代器
    vector <int>::reverse_iterator  t2;
    t2 = vec.rbegin();
    for (; t2 != vec.rend(); ++t2)
        cout << *t2 << " ";

    return 0;
}

4.2 迭代器属性：前向迭代、双向迭代、随机迭代

• 以 vector 容器为例，vector容器属于随机访问迭代器，也支持前向迭代和双向迭代。表现前向迭代、双向迭代、随机访问迭代三种属性。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector <int> vec = { 1,2,3,4,5 };
    vector <int>::iterator t;//正向迭代器的定义方式

    //前向迭代，前向迭代器可以实现p++
    for (t = vec.begin(); t != vec.end(); ++t)
        cout << *t << " ";
    cout << endl;
    
    //双向迭代，双向迭代器可以实现p--
    t = vec.end()-1;
    for (int j = 0; j < vec.size(); ++j)
    {
        cout << *t << " ";
        if (t !=vec.begin())  t--;
    }
    cout << endl;

    //随机迭代，随机迭代器可以实现p+i
    t = vec.begin();
    t = t+2;
    cout << *t << " ";

    return 0;
}

4.2 迭代器的遍历方法

• 以 vector 容器为例，按照正向迭代器的定义方式，下面的程序中，每个循环演示了一种做法。

//遍历 vector 容器。
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v{ 1,2,3,4,5,6,7,8,9,10 }; //v被初始化成有10个元素
    vector<int>::iterator i;//创建一个正向迭代器
        
    cout << endl << "第 1 种遍历方法：" << endl;
    for (i = v.begin(); i != v.end(); ++i)//用 != 比较两个迭代器
        cout << *i << " ";

    cout << endl << "第 2 种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";

    cout << endl << "第 3 种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) 
    {
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}

4.3 auto关键字 自动指定迭代器定义类型

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector <int> vec = { 1, 2,3, 4 ,5 };

    auto t = vec.begin();
    for (; t != vec.end(); ++t)
        cout << *t << " ";

    return 0;
}