参考C++ STL迭代器原理和实现
迭代器STL（Standard Template Library）中提供了许多容器，包括vector、list、map、set等，少部分容器（vector）可以通过下标来访问其中的元素，而大部分的容器都不可以这么做，为了能够以一种统一的方式来访问STL的所有容器，STL提供了迭代器访问的方式，它的实现方式是在每个容器类中内嵌了一个专属的iterator类，在iterator类中实现了对该容器的元素的遍历和访问。
通过在所有容器类中实现iterator，就可以很方便地实现一些通用算法，比如find查找函数，前两个参数填起始和结束位置的迭代器，第三个参数填需要查找的值，就可以适用于各种容器（因为迭代器提供了统一的访问方式）。
在每个容器类中实现迭代器时，需要对一些基本操作如*、->、++、==、!=、=等进行重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的容器，所有迭代器的使用和指针的使用非常相似（迭代器很好地诠释了接口与实现分离的意义）。通过begin，end函数获取容器的头部和尾部迭代器，end迭代器不包含在容器之内，当begin和end返回的迭代器相同时表示容器为空。
实现迭代器这里以List为例子，展示了如何在容器中内嵌和实现list_iterator类。
my_list.h#ifndef CPP_PRIMER_MY_LIST_H #define CPP_PRIMER_MY_LIST_H #includetemplate class node { public: T value; node *next; node() : next(nullptr) {} node(T val, node *p = nullptr) : value(val), next(p) {} }; template class my_list { private: node *head; node *tail; int size; private: class list_iterator { private: node *ptr; //指向list容器中的某个元素的指针 public: list_iterator(node *p = nullptr) : ptr(p) {} //重载++、--、*、->等基本操作 //返回引用，方便通过*it来修改对象 T &operator*() const { return ptr->value; } node *operator->() const { return ptr; } list_iterator &operator++() { ptr = ptr->next; return *this; } list_iterator operator++(int) { node *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 (value); tail = head; } else { tail->next = new node (value); tail = tail->next; } size++; } //打印链表元素 void print(std::ostream &os = std::cout) const { for (node *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
上面主要包含三个部分：node结点定义、my_list类和list_iterator类，前两个都非常简单易懂，下面直接分析list_iterator相关的实现内容。
1、首先是指针ptr，iterator就是通过这个指针来遍历容器的。
2、重载操作符：
- *：通过*iter可以访问对应的元素
- ->：当迭代器指向的是一个对象时，可以通过iter->a这样的方式来访问这个对象里的a变量。
- ++：重载前置++，返回的是++后的迭代器
- ++(int)：重载后置++，返回的是++前的迭代器
- ==：判断两个迭代器所持有的指针是否指向容器的同一个元素
- !=：判断两个迭代器所持有的指针是否指向容器的不同元素
3、begin函数中构造一个指针指向第一个元素的迭代器并且返回，end函数中构造一个指针指向最后一个元素的迭代器并且返回。
test.cpp#include#include "my_list.h" struct student { std::string name; int age; student(std::string n, int a) : name(n), age(a) {} //重载输出操作符 friend std::ostream &operator<<(std::ostream &os, const student &stu) { os << stu.name << " " << stu.age; return os; } }; int main() { my_list l; l.push_back(student("bob", 1)); //临时量作为实参传递给push_back方法 l.push_back(student("allen", 2)); l.push_back(student("anna", 3)); l.print(); for (my_list ::iterator it = l.begin(); it != l.end(); it++) { std::cout << *it << std::endl; *it = student("wengle", 18); } return 0; }
主要看iterator的用法，可见声明iter时，用的是命名空间my_list
使用迭代器时遇到的一个最常见的问题就是迭代器失效，两种经典的情况：
- 往vector中插入了大量的元素导致vector扩容（在别的地方新建一块两倍的内存，并且释放原本的内存），然后还操作此前的旧的迭代器，导致crash。
- 在for循环中erase了当前迭代器指向的元素，随后iter++时，由于要执行ptr->next操作需要访问该元素节点，而该元素已经被释放了，导致crash。
上面的情况中，无一例外都是因为迭代器中的指针ptr已经变成野指针，迭代器失效，但是仍然对迭代器进行操作而导致的错误。
