为了提高C++编程的效率，STL（Standard Template Library）中提供了许多容器，包括vector、list、map、set等。然而有些容器（vector）可以通过下标索引的方式访问容器里面的数据，但是大部分的容器（list、map、set）不能使用这种方式访问容器中的元素。为了统一访问不同容器时的访问方式，STL为每种容器在实现的时候设计了一个内嵌的iterator类，不同的容器有自己专属的迭代器（专属迭代器负责实现对应容器访问元素的具体细节），使用迭代器来访问容器中的数据。除此之外，通过迭代器可以将容器和通用算法结合在一起，只要给予算法不同的迭代器，就可以对不同容器执行相同的操作，例如find查找函数（因为迭代器提供了统一的访问方式，这是使用迭代器带来的好处）。迭代器对一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的容器，所有迭代器的使用和指针的使用非常相似。通过begin，end函数获取容器的头部和尾部迭代器，end迭代器不包含在容器之内，当begin和end返回的迭代器相同时表示容器为空。
STL主要由 容器、迭代器、算法、函数对象、和内存分配器 五大部分构成。
首先，看看STL中迭代器的实现思路：
从上图中可以看出，STL通过类型别名的方式实现了对外统一；在不同的容器中类型别名的真实迭代器类型是不一样的，而且真实迭代器类型对于++、--、*、->等基本操作的实现方式也是不同的。（PS：迭代器很好地诠释了接口与实现分离的意义）
既然我们已经知道了迭代器的实现思路，现在如果让我们自己设计一个list容器的简单迭代器，应该如何实现呢？
- list类需要有操作迭代器的方法
- begin/end
- insert/erase/emplace
- list类有一个内部类list_iterator
- 有一个成员变量ptr指向list容器中的某个元素
- iterator负责重载++、--、*、->等基本操作
- list类定义内部类list_iterator的类型别名
以上就是实现一个list容器的简单迭代器需要考虑的具体细节。
my_list.h（重要部分有注释说明）
test.cpp
上面的代码很好地展示了什么是迭代器失效？迭代器失效会导致什么样的问题？
当执行完这条语句后，实际上myvector已经申请了一块新的内存空间来存放之前已保存的数据和本次要插入的数据，由于迭代器内部的指针还是指向旧内存空间的元素，一旦旧内存空间被释放，当执行时就会crash（PS：因为你通过iterator的指针正在操作一块已经被释放的内存，大多数情况下都会crash)。迭代器失效就是指：迭代器内部的指针没有及时更新，依然指向旧内存空间的元素。
上图展示了STL源码中vector容器方法的实现方式。当插入的元素个数超过当前容器的剩余容量时，就会导致迭代器失效。这也是测试代码中插入200个元素的原因，为了模拟超过当前容器剩余容量的场景，如果你的测试环境没有crash，可以将插入元素设置的更多一些。
- Iterator invalidation rules
- 迭代器失效问题？
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6672.html