STL 迭代器

在 STL 中，迭代器（Iterator）用来访问和检查 STL 容器中元素的对象，它的行为模式和指针类似，但是它封装了一些有效性检查，并且提供了统一的访问格式。
迭代器的设计思维是STL的关键所在，STL的中心思想在于将容器(container)和算法(algorithms)分开，彼此独立设计，最后再一贴胶着剂将他们撮合在一起。

迭代器(iterator)是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。 在<>一书中提供了23种设计模式的完整描述， 其中iterator模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

从技术角度来看，容器和算法的泛型化并不困难，c++的class template和function template可分别达到目标，如果设计出两这个之间的良好的胶着剂，才是大难题。

1. 基本使用

概念虽然晦涩难懂，但是在使用时可以当作指针，大部分迭代器都支持这两个运算符：自增 运算符（ ++ ）和解引用运算符（* ），其中自增用来移动迭代器，解引用可以获取或修改它指向的元素。

2. 迭代器分类

迭代器总共又五种，分别是：输入迭代器，输出迭代器，正向迭代器，双向迭代器和随机访问迭代器。具体区别见下表：

2.1. 输入迭代器（input iterator）

可以读取序列中的元素。一个输入迭代器必须支持：

• 用于比较两个迭代器的相等和不相等运算符（==、!=）
• 用于推进迭代器的前置和后置递增运算（++）
• 用于读取元素的解引用运算符（*）；解引用只会出现在赋值运算符的右侧
• 箭头运算符（->），等价于 (*it).member ，即，解引用迭代器，并提取对象的成员

输入迭代器只用于顺序访问。对于一个输入迭代器，*it++保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。因此，输入迭代器只能用于单遍扫描算法。算法find和accumulate要求输入迭代器；而istream_iterator是一种输入迭代器。

2.2.输出迭代器（output iterator）

可以看作输入迭代器功能上的补集——只写而不读元素。输出迭代器必须支持:

• 用于推进迭代器的前置和后置递增运算（++）
• 解引用运算符（*），只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

我们只能向一个输出迭代器赋值一次。类似输入迭代器，输出迭代器只能用于单遍扫面算法。用作目的位置的迭代器通常都是输出迭代器。例如，copy函数的第三个参数就是输出迭代器。ostream_iterator类型也是输出迭代器。

2.3. 前向迭代器（forward iterator）

可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。算法replace要求前向迭代器，forward_list上的迭代器是前向迭代器。

演示：支持通过 ++ 自增（前移），通过 * 访问或赋值。

#include <iostream>
#include <forward_list>
using namespace std;
int main() {
    // forward_list 是 STL 中的单向链表，可以获得前向迭代器
    forward_list<int> l{1, 2, 3};
    forward_list<int>::iterator iter = l.begin();
    for (; iter != l.end(); ++iter) {
        cout << *iter << ' ';  // 输出: 1 2 3
    }
    return 0;
}

2.4. 双向迭代器（bidirectional iterator）

可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（--）。算法reverse要求双向迭代器，除了forward_list之外，其他标准库都提供符合双向迭代器要求的迭代器。
演示：在前向迭代器的基础上，增加了自减（--）的支持。

#include <iostream>
#include <list>
using namespace std;
int main() {
    // list 是 STL 中的双向链表，可以获得双向迭代器
    list<int> l{1, 2, 3};
    list<int>::iterator iter = l.begin();
    for (; iter != l.end(); ++iter) {
        cout << *iter << ' ';  // 输出: 1 2 3
    }
    cout << endl;
    while (iter != l.begin()) {
        --iter;
        cout << *iter << ' ';  // 输出: 3 2 1
    }
    return 0;
}

2.5. 随机访问迭代器（random-access iterator）

提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能，此外还支持如下操作：

• 用于比较两个迭代器相对位置的关系运算符（<,<=,>和>=）
• 迭代器和一个整数值的加减运算（+,+=,-,-=）,计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
• 用于两个迭代器上的减法运算符(-)，得到两个迭代器的距离
• 下标运算符（iter[n]）,与 *(iter[n]) 等价

演示：在双向迭代器的基础上，增加了加减运算和比较运算的支持。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    // vector 是 STL 对数组的封装
    vector<int> v{1, 2, 3, 4, 5};
    for (vector<int>::iterator iter = v.begin(); iter < v.end(); iter += 2) {
        cout << *iter << ' ';  // 输出: 1 3 5
    }
    return 0;
}

引用自【C/C++】STL详解——迭代器应用演示，作者：沉晓

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//STL 中的容器 算法 迭代器
void test01(){
    vector<int> v; //STL 中的标准容器之一 ：动态数组
    v.push_back(1); //vector 容器提供的插入数据的方法
    v.push_back(5);
    v.push_back(3);
    v.push_back(7);
    //迭代器
    vector<int>::iterator pStart = v.begin(); //vector 容器提供了 begin()方法 返回指向第一个元素的迭代器
    vector<int>::iterator pEnd = v.end(); //vector 容器提供了 end()方法 返回指向最后一个元素下一个位置的迭代器
    //通过迭代器遍历
    while (pStart != pEnd){
        cout << *pStart << " ";
        pStart++;
    }
    cout << endl;
    //算法 count 算法 用于统计元素的个数
    int n = count(pStart, pEnd, 5);
    cout << "n:" << n << endl;
}
//STL 容器不单单可以存储基础数据类型，也可以存储类对象
class Teacher
{
public:
    Teacher(int age) :age(age){};
    ~Teacher(){};
public:
    int age;
};
void test02(){
    vector<Teacher> v; //存储 Teacher 类型数据的容器
    Teacher t1(10), t2(20), t3(30);
    v.push_back(t1);
    v.push_back(t2);
    v.push_back(t3);
    vector<Teacher>::iterator pStart = v.begin();
    vector<Teacher>::iterator pEnd = v.end();
    //通过迭代器遍历
    while (pStart != pEnd){
        cout << pStart->age << " ";
        pStart++;
    }
    cout << endl;
}
//存储 Teacher 类型指针
void test03(){
    vector<Teacher*> v; //存储 Teacher 类型指针
    Teacher* t1 = new Teacher(10);
    Teacher* t2 = new Teacher(20);
    Teacher* t3 = new Teacher(30);
    v.push_back(t1);
    v.push_back(t2);
    v.push_back(t3);
    //拿到容器迭代器
    vector<Teacher*>::iterator pStart = v.begin();
    vector<Teacher*>::iterator pEnd = v.end();
    //通过迭代器遍历
    while (pStart != pEnd){
        cout << (*pStart)->age << " ";
        pStart++;
    }
    cout << endl;
}
//容器嵌套容器 难点
void test04()
{
    vector< vector<int> > v;
    vector<int>v1;
    vector<int>v2;
    vector<int>v3;
    for (int i = 0; i < 5;i++)
    {
        v1.push_back(i);
        v2.push_back(i * 10);
        v3.push_back(i * 100);
    }
    v.push_back(v1);
    v.push_back(v2);
    v.push_back(v3);
    for (vector< vector<int> >::iterator it = v.begin(); it != v.end();it++)
    {
        for (vector<int>::iterator subIt = (*it).begin(); subIt != (*it).end(); subIt ++)
        {
            cout << *subIt << " ";
        }
        cout << endl;
    }
} 
int main(){
    //test01();
    //test02();
    //test03();
    test04();
    system("pause");
    return EXIT_SUCCESS;
}