目录
- 迭代器的使用
- 迭代器的种类
- 迭代器的失效
- 迭代器的实现
1.迭代器的使用
为了提高C++编程的效率，STL中提供了许多容器，包括vector、list、map、set等。有些容器例如vector可以通过脚标索引的方式访问容器里面的数据，但是大部分的容器不能使用这种方式，例如list、map、set。STL中每种容器在实现的时候设计了一个内嵌的iterator类，不同的容器有自己专属的迭代器，使用迭代器来访问容器中的数据。除此之外，通过迭代器，可以将容器和通用算法结合在一起，只要给予算法不同的迭代器，就可以对不同容器执行相同的操作，例如find查找函数。迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构，所有迭代的使用和指针的使用非常相似。通过begin，end函数获取容器的头部和尾部迭代器，end 迭代器不包含在容器之内，当begin和end返回的迭代器相同时表示容器为空。
template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value)
{
while (first != last && *frist != value)
++first;
return first;
}
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main(int argc, const char *argv[])
{
int arr[5] = { 1, 2, 3, 4, 5};
vector<int> iVec(arr, arr + 5);//定义容器vector
list<int> iList(arr, arr + 5);//定义容器list
//在容器iVec的头部和尾部之间寻找整形数3
vector<int>::iterator iter1 = find(iVec.begin(), iVec.end(), 3);
if (iter1 == iVec.end())
cout<<"3 not found"<<endl;
else
cout<<"3 found"<<endl;
//在容器iList的头部和尾部之间寻找整形数4
list<int>::iterator iter2 = find(iList.begin(), iList.end(), 4);
if (iter2 == iList.end())
cout<<"4 not found"<<endl;
else
cout<<"4 found"<<endl;
return 0;
}
2.迭代器的种类
根据迭代器所支持的操作，可以把迭代器分为5类。
1) 输入迭代器：是只读迭代器，在每个被遍历的位置上只能读取一次。例如上面find函数参数就是输入迭代器。
2) 输出迭代器：是只写迭代器，在每个被遍历的位置上只能被写一次。
3) 前向迭代器：兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。但它不支持operator--，所以只能向前移动。
4) 双向迭代器：很像前向迭代器，只是它向后移动和向前移动同样容易。
5) 随机访问迭代器：有双向迭代器的所有功能。而且，它还提供了“迭代器算术”，即在一步内可以向前或向后跳跃任意位置， 包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。
STL每种容器类型都定义了 const_iterator，只能读取容器的值，不能修改所指向容器范围内元素的值。vector、string、Deque随机存取迭代器；List、Set、map、mutiset、multimap双向迭代器。
3.迭代器失效
容器的插入insert和erase操作可能导致迭代器失效，对于erase操作不要使用操作之前的迭代器，因为erase的那个迭代器一定失效了，正确的做法是返回删除操作时候的那个迭代器。
#include <vector>
using namespace std;
int main(int argc, const char *argv[]) {
int arr[5] = { 1, 2, 3, 4, 5 };
vector<int> iVec(arr, arr + 5); //定义容器vector
//迭代器失效
// for (vector<int>::iterator it = iVec.begin(); it != iVec.end();) {
// iVec.erase(it);
// }
//返回erase操作之后的迭代器
for (vector<int>::iterator it = iVec.begin();it != iVec.end();) {
it = iVec.erase(it);
}
return 0;
}
4.迭代器的实现
STL中每个容器都有自己的迭代器，各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念，下面在单链表类中内嵌入一个iterator的类来实现单链表的迭代
#include <iostream>
template<typename T>
struct ListNode {
T value;
ListNode* next;
ListNode() {
next = 0;
}
ListNode(T val, ListNode *p = nullptr) :
value(val), next(p) {
}
};
template<typename T>
class List {
private:
ListNode<T> *m_pHead;
ListNode<T> *m_pTail;
int m_nSize;
public:
List() {
m_pHead = nullptr;
m_pTail = nullptr;
m_nSize = 0;
}
//从链表尾部插入元素
void push_back(T value) {
if (m_pHead == nullptr) {
m_pHead = new ListNode<T>(value);
m_pTail = m_pHead;
} else {
m_pTail->next = new ListNode<T>(value);
m_pTail = m_pTail->next;
}
}
//打印链表元素
void print(std::ostream &os = std::cout) const {
for (ListNode<T> *ptr = m_pHead; ptr != m_pTail->next ; ptr = ptr->next)
std::cout << ptr->value << " ";
os << std::endl;
}
//内置迭代器
class iterator {
private:
ListNode<T> *m_ptr;
public:
iterator(ListNode<T>* p = nullptr) :
m_ptr(p) {
}
T operator*() const {
return m_ptr->value;
}
ListNode<T>* operator->() const {
return m_ptr;
}
iterator& operator++() {
m_ptr = m_ptr->next;
return *this;
}
iterator operator++(int) {
ListNode<T>* tmp = m_ptr;
m_ptr = m_ptr->next;
return iterator(tmp);
}
bool operator==(const iterator &arg) const {
return arg.m_ptr == this->m_ptr;
}
bool operator!=(const iterator &arg) const {
return arg.m_ptr != this->m_ptr;
}
};
//返回链表头部指针
iterator begin() const {
return iterator(m_pHead);
}
//返回链表尾部指针
iterator end() const {
return iterator(m_pTail->next);
}
//其它成员函数
};
int main() {
List<int> l;
l.push_back(1);
l.push_back(2);
l.print();
for (List<int>::iterator it = l.begin(); it != l.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
在《C++ primer》（第五版）中的9.3.6中是这样总结的：
向容器中添加元素和从容器中删除元素的操作可能会使指向容器的元素指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再代表任何元素。使用失效的指针、引用或迭代器是一种严重的程序错误，很可能引起与使用未初始化指针一样的问题 。
在向容器添加元素后：
如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效（至于原因跟deque的申请内存有关，它的内存是拼接的）。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
对于list和forward_list指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。
当我们从一个容器中删除元素后：
指向被删除元素的迭代器、指针和引用会失效，这样该不会令人惊讶。毕竟，这些元素都已经被销毁了。当我们删除一个元素后：
对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
对于deque，如果在首尾之外的任何位置删删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器 也会失效，但其他迭代器、引用或指针不受影响；如果删删除首元素，这些也不会受影响。
对于vector和 string，指向被删除元素之前元素的迭代器、引用和指针仍有效。
由于向迭代器添加元素和从 迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变迭代器的操作之后都正确的重新定位迭代器。这个建议对vector、string和deque尤为重要。
补充：deque迭代器失效问题
deque由一段一段的定量连续空间构成，采用一个表（map）来记录每个连续空间的首址，map是一小块连续的空间，目的是便于迭代器的寻址（map+1即可跳转到下一个连续空间的首址）。map中的每一个元素（node）都是指针，指向另一端（较大的）连续线性空间，称为缓冲区，缓冲区才是deque的储存空间主体。具体机制如下所示：
其中，对迭代器it的解引用得到的是cur位置处对应的元素。
deque要求map中前后各预留一个node节点，以便扩充时可用。
下面讨论插入删除操作，deque中的迭代器、引用失效问题。
查看deque源码可知，在push_front/push_back中，由于要满足以上预留一个节点的要求，若当前map所管理的节点个数不足以扩充时，map需要重分配。如下图所示：
当前deque中含有23个元素，此时push_back（23），会导致node节点不足，于是引起map的重分配。
原来的迭代器的node指向的map节点被释放，也就无法找到对应的元素，故原迭代器失效。而由于这个过程中内存并未发生改变，故其他元素的引用、指针仍然有效。push_front同理。
pop_front，pop_back只是简单的析构元素，必要时（第一个缓冲区、最后一个缓冲区只有一个元素）释放该缓冲区、调整start、finish迭代器的状态，所以指向其他元素的迭代器、引用均有效。
除了头尾两端，在任何地方插入和删除元素都将导致内存重新分配，导致指向deque元素的任何pointer、iterator、reference失效。
总结如下：
插入操作：
1、在队前或队后插入元素时（push_back(),push_front()）,由于可能缓冲区的空间不够，需要增加map中控器，而中控器的个数也不够，所以新开辟更大的空间来容纳中控器，所以可能会使迭代器失效；但指针、引用仍有效，因为缓冲区已有的元素没有重新分配内存。
2、在队列其他位置插入元素时，由于会造成缓冲区的一些元素的移动（源码中执行copy()来移动数据），所以肯定会造成迭代器的失效；并且指针、引用都会失效。
删除操作：
1、删除队头或队尾的元素时，由于只是对当前的元素进行操作，所以其他元素的迭代器不会受到影响，所以一定不会失效，而且指针和引用也都不会失效；
2、删除其他位置的元素时，也会造成元素的移动，所以其他元素的迭代器、指针和引用都会失效。