一、迭代器有什么用？
我们知道，STL标准库一共有六大部件：分配器、容器、迭代器、算法、仿函数、适配器。其中，迭代器就是用来“联结”算法、仿函数与容器的纽带。
除此之外，在设计模式中有一种模式叫迭代器模式，简单来说就是提供一种方法，在不需要暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素，这种设计思维在STL中得到了广泛的应用，是STL的关键所在，通过迭代器，容器和算法可以有机的粘合在一起，只要对算法给予不同的迭代器，就可以对不同容器进行相同的操作。（参考：https://blog.csdn.net/shudou/article/details/11099931）
比如下面这个find函数，展示了容器、算法和迭代器如何合作：
template<typename InputIterator, typename T> InputIterator find(InputIterator first, InputIterator last, const T &value) { while (first != last && *frist != value) ++first; return first; }
上述的find函数，只需要传递容器的迭代器，就可以实现对不同的容器实现相同的算法，这其实是一种泛型编程的思想。
二、不同容器的迭代器实现
vector
我们来看看在vector中对于iterator的实现：
template<typename T,class Alloc = alloc > class vector { public: typedef T value_type; typedef value_type* iterator; ······ };
在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针。
List
下面是某位博主自己实现的一个简单List 迭代器，供大家学习使用：
#ifndef CPP_PRIMER_MY_LIST_H #define CPP_PRIMER_MY_LIST_H #include <iostream> template<typename T> class node { public: T value; node *next; node() : next(nullptr) {} node(T val, node *p = nullptr) : value(val), next(p) {} }; template<typename T> class my_list { private: node<T> *head; node<T> *tail; int size; private: class list_iterator { private: node<T> *ptr; //指向list容器中的某个元素的指针 public: list_iterator(node<T> *p = nullptr) : ptr(p) {} //重载++、--、*、->等基本操作 //返回引用，方便通过*it来修改对象 T &operator*() const { return ptr->value; } node<T> *operator->() const { return ptr; } list_iterator &operator++() { ptr = ptr->next; return *this; } list_iterator operator++(int) { node<T> *tmp = ptr; // this 是指向list_iterator的常量指针，因此*this就是list_iterator对象，前置++已经被重载过 ++(*this); return list_iterator(tmp); } bool operator==(const list_iterator &t) const { return t.ptr == this->ptr; } bool operator!=(const list_iterator &t) const { return t.ptr != this->ptr; } }; public: typedef list_iterator iterator; //类型别名 my_list() { head = nullptr; tail = nullptr; size = 0; } //从链表尾部插入元素 void push_back(const T &value) { if (head == nullptr) { head = new node<T>(value); tail = head; } else { tail->next = new node<T>(value); tail = tail->next; } size++; } //打印链表元素 void print(std::ostream &os = std::cout) const { for (node<T> *ptr = head; ptr != tail->next; ptr = ptr->next) os << ptr->value << std::endl; } public: //操作迭代器的方法 //返回链表头部指针 iterator begin() const { return list_iterator(head); } //返回链表尾部指针 iterator end() const { return list_iterator(tail->next); } //其它成员函数 insert/erase/emplace }; #endif //CPP_PRIMER_MY_LIST_H
对于其他的容器迭代器分析，暂略。
三、迭代器分类
在STL中，除了原生指针以外，迭代器被分为五类：
Input Iterator
顾名思义，input——此迭代器不允许修改所指的对象，即是只读的。支持==、!=、++、*、->等操作。
Output Iterator
允许算法在这种迭代器所形成的区间上进行只写操作。支持++、*等操作。
Forward Iterator
允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持Input Iterator和Output Iterator的所有操作。
Bidirectional Iterator
允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持Forward Iterator的所有操作，并另外支持–操作。
Random Access Iterator
包含指针的所有操作，可进行随机访问（vector容器支持），随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。
上述五种迭代器的分类和联系可参考下图：
了解了迭代器的类型，我们就能解释vector的迭代器和list迭代器的区别了。显然vector的迭代器具有所有指针算术运算能力，而list由于是双向链表，因此只有双向读写但不能随机访问元素。**故vector的迭代器种类为Random Access Iterator,list 的迭代器种类为Bidirectional Iterator。**我们只需要根据不同的迭代器种类，利用traits编程技巧萃取出迭代器种类，然后由C++的重载机制就能够对不同型别的迭代器采用不同的处理流程了。为此，对于每个迭代器都必须定义型别iterator_category,也就是源码中的typedef std::forward_iterator_tag iterator_category; 实际中可以直接继承STL中定义的iterator模板,模板后三个参数都有默认值，因此继承时只需要指定前两个模板参数即可。如下所示，STL定义了五个空类型作为迭代器的标签：
template<class Category,class T,class Distance = ptrdiff_t,class Pointer=T*,class Reference=T&> class iterator{ typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; }; struct input_iterator_tag{}; struct output_iterator_tag{}; struct forward_iterator_tag:public input_iterator_tag{}; struct bidirectional_iterator_tag:public forward_iterator_tag{}; struct random_access_iterator_tag:public bidirectional_iterator_tag{};
四、迭代器失效？
当使用一个容器的insert或者erase函数通过迭代器插入、删除或者修改元素（如map、set，因为其底层是红黑树）"可能"会导致迭代器失效，因此为了避免危险，应该重新获取的新的有效的迭代器进行正确的操作。plus
vector
1、当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。
2、当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。
3、当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。
list
1、插入操作（insert）和接合操作（splice）不会造成原有的list迭代器失效，这在vector中是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致所有的迭代器全部失效。
2、list的删除操作（erase）也只有指向被删除元素的那个迭代器失效，其他迭代器不受影响。（list目前只发现这一种失效的情况）
关联容器
对于关联容器(如map, set,multimap,multiset)，删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响（虽然删除了一个元素，整棵树也会调整，以符合红黑树或者二叉树的规范，但是单个节点在内存中的地址没有变化，变化的是各节点之间的指向关系）。erase迭代器只是被删元素的迭代器失效，但是返回值为void，所以要采用**erase(iter++)（分三步走，先把iter传值到erase里面，然后iter自增，然后执行erase,所以iter在失效前已经自增了）**的方式删除迭代器。
