【C++】【自用】STL的六大组件：迭代器

1. 什么是迭代器

行为像指针一样的类型，用户不用关注容器底层细节，而可以轻松访问容器。底层可能是指针，也可能是被类封装的指针。每种容器都有自己专属的迭代器。

2. 迭代器的价值

迭代器是 算法 和 容器之间的桥梁

如果没有迭代器：

访问需要暴露容器底层结构及实现细节，容器的封装性就别谈了
使用者门槛较高，比如要访问 map，需要掌握二叉树的遍历
1
2

所以我们可以说，迭代器：

• 封装隐藏了底层实现细节。
• 提供统一的方式去访问容器，极大降低了使用成本。

3. 什么是迭代器失效

• 迭代器指向的空间野指针
• 迭代器指向的位置已经不是原来的位置，意义发生变化

失效举例：

vector 
	insert 扩容，会导致野指针
	insert 不扩容，但是挪动数据，指向位置已经不是原来的位置
  	erase 数据以后，挪动数据，指向位置已经不是原来的位置
list
	erase 数据以后，节点删除，导致野指针
map/set/unordered_xxx
	erase 数据以后，节点删除，导致野指针
1
2
3
4
5
6
7
8

4. 反向迭代器的原理

• 适配器
• 即，一个容器的反向迭代器使用这个容器自己的正向迭代器封装出来的

5. 迭代器分类

• 单向：支持 ++
  forward_list、unordered_xxx

• 双向：支持 ++/--
  map/set、list

• 随机：支持 ++/--、+/ -、[]…
  string、vector、deque

某些算法对传入容器的迭代器有要求，从命名上就能看出：

sort 支持随机

reverse 支持双向、随机

find 支持单项、双向、随机