迭代器简介
迭代器（Iterator）是一种抽象设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器。迭代器的功能：访问容器对象的元素
STL中迭代器的一个重要作用就是作为容器与STL算法的连接，容器提供迭代器的接口，同一套算法代码可以用在不同的容器中。所有标准库容器都可以使用迭代器，部分支持使用下标运算符。（String对象不属于容器）
迭代器是指针的泛化，提供一种行为类似指针的类对非数组数据结构进行遍历，这允许程序员以相同的方式处理不同的数据结构（容器）
迭代器的类别
首先介绍五种迭代器类别：
| 迭代器类型 | 迭代器说明 |
|---|---|
输入迭代器input iterator |
从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列 |
输出迭代器output iterator |
向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，统一输出迭代器不能两次遍历一个序列 |
正向迭代器forward iterator |
组合输入迭代器和输出迭代器的功能，并保留在容器中的位置 |
双向迭代器bidirectional iterator |
组合正向迭代器和逆向迭代器的功能，支持多遍算法 |
随机访问迭代器random-access iterator |
组合双向迭代器的功能与直接访问容器中任何元素的功能，即可向前向后跳过任意个元素 |
它们的基础关系如下图所示：
迭代器的操作
每种迭代器均可进行包括表中前一种迭代器可进行的操作。（见参考资料[3]）
所有迭代器：
| 迭代器操作 | 说明 |
|---|---|
| p++ | 后置自增迭代器 |
| ++p | 前置自增迭代器 |
输入迭代器：
| 迭代器操作 | 说明 |
|---|---|
| *p | 复引用迭代器，作为右值 |
| p=p1 | 将一个迭代器赋给另一个迭代器 |
| p==p1 | 比较迭代器的相等性 |
| p!=p1 | 比较迭代器的不等性 |
输出迭代器：
| 迭代器操作 | 说明 |
|---|---|
| *p | 复引用迭代器，作为左值 |
| p=p1 | 将一个迭代器赋给另一个迭代器 |
正向迭代器：
| 迭代器操作 | 说明 |
|---|---|
| 提供输入输出迭代器的所有功能 |
双向迭代器：
| 迭代器操作 | 说明 |
|---|---|
| –p | 前置自减迭代器 |
| p– | 后置自减迭代器 |
随机迭代器：
| 迭代器操作 | 说明 |
|---|---|
| p+=i | 将迭代器递增i位 |
| p-=i | 将迭代器递减i位 |
| p+i | 在p位加i位后的迭代器 |
| p-i | 在p位减i位后的迭代器 |
| p[i] | 返回p位元素偏离i位的元素引用 |
| p<p1 | 如果迭代器p的位置在p1前，返回true，否则返回false |
| p<=p1 | p的位置在p1的前面或同一位置时返回true，否则返回false |
| p>p1 | 如果迭代器p的位置在p1后，返回true，否则返回false |
| p>=p1 | p的位置在p1的后面或同一位置时返回true，否则返回false |
容器支持的迭代器
只有顺序容器和关联容器支持迭代器遍历，容器适配器不支持：
| 容器 | 支持的迭代器类别 | 说明 |
|---|---|---|
| vector | 随机访问 | 一种随机访问的数组类型，提供了对数组元素进行快速随机访问以及在序列尾部进行快速的插入和删除操作的功能。可以再需要的时候修改其自身的大小 |
| deque | 随机访问 | 一种随机访问的数组类型，提供了序列两端快速进行插入和删除操作的功能。可以再需要的时候修改其自身的大小 |
| list | 双向 | 一种不支持随机访问的数组类型，插入和删除所花费的时间是固定的，与位置无关。 |
| set | 双向 | 一种随机存取的容器，其关键字和数据元素是同一个值。所有元素都必须具有惟一值。 |
| multiset | 双向 | 一种随机存取的容器，其关键字和数据元素是同一个值。可以包含重复的元素。 |
| map | 双向 | 一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个特定的关键字只能与一个元素关联。 |
| multimap | 双向 | 一种包含成对数值的容器，一个值是实际数据值，另一个是用来寻找数据的关键字。一个关键字可以与多个数据元素关联。 |
| stack | 不支持 | 适配器容器类型，用vector，deque或list对象创建了一个先进后出容器 |
| queue | 不支持 | 适配器容器类型，用deque或list对象创建了一个先进先出容器 |
| priority_queue | 不支持 | 适配器容器类型，用vector或deque对象创建了一个排序队列 |
迭代器的基本使用
迭代器的类型
一般来说不需要知道迭代器的准确类型，标准库使用iterator来表示迭代器的类型（对象是常量只能用const前缀的，变量则都行）
迭代器按照定义方式分成以下四种：
- 正向迭代器，定义方法如下：
容器类名::iterator 迭代器名;
- 常量正向迭代器，定义方法如下：
容器类名::const_iterator 迭代器名;
- 反向迭代器，定义方法如下：
容器类名::reverse_iterator 迭代器名;
- 常量反向迭代器，定义方法如下：
容器类名::const_reverse_iterator 迭代器名;
begin和end方法
容器和string对象都有定义迭代器类型，同时拥有返回迭代器的成员函数。如：容器有成员函数begin和end：
- begin成员函数复制返回指向第一个元素的迭代器
- end成员函数返回指向容器尾元素的下一个位置的迭代器
对于常量对象，begin和end返回的是const_iterator，非常量返回iterator
为便于专门得到const_iterator类型，C++11提供了两个新函数：cbegin和cend
简单使用示例
正向反向遍历vector容器：
int main()
{
std::vector<int> scores = { 1,2,3,4,5,6,7,8,9,10};
// 正向遍历vector容器
for (auto i = scores.begin(); i < scores.end(); i++)
{
std::cout << *i << " ";
}
std::cout << std::endl;
// 1 2 3 4 5 6 7 8 9 10
// 反向遍历vector容器
for (auto i = scores.rbegin(); i < scores.rend(); i++)
{
std::cout << *i << " ";
}
std::cout << std::endl;
// 10 9 8 7 6 5 4 3 2 1
auto a = scores.begin();
auto b = scores.rend();
if (a == b.base()) { // base方法用于将reverse_iterator转换成iterator
std::cout << "begin == rend" << std::endl;
}
else {
std::cout << "begin != rend" << std::endl;
}
return 0;
}
迭代器的辅助函数
STL有操作迭代器的三个函数模板：(均来自<algorithm>库)
advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。
使用案例
本段内容来自参考资料[5]
std::replace函数：
template <class _FwdIt, class _Ty>
_CONSTEXPR20 void replace(const _FwdIt _First, const _FwdIt _Last, const _Ty& _Oldval, const _Ty& _Newval) {
// replace each matching _Oldval with _Newval
_Adl_verify_range(_First, _Last);
auto _UFirst = _Get_unwrapped(_First);
const auto _ULast = _Get_unwrapped(_Last);
for (; _UFirst != _ULast; ++_UFirst) {
if (*_UFirst == _Oldval) {
*_UFirst = _Newval;
}
}
}
这段是我从VS2022里复制出来的，模板参数里两个类模板，看名字不难猜到前者这个_FwdIt指的是ForwardIterator前向迭代器，replace函数的功能遍历迭代器区间将旧值替换成新值
std::merge函数：
代码我直接从参考资料那里复制吧，VS里提取出来的看着没这个清晰
// merge，将两个有序序列进行合并，返回结果序列最后一个元素的下一个位置
// 版本1，operator<
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2) { // 输入的两组迭代器区间不相同
if (*first1 < *first2) { // 如果1的值小
*result = *first1; // 就保存到输出序列中的第一个
++first1; // 迭代器1往后挪
}
else {
*result = *first2;
++first2;
}
++result;
}
// 将两个序列中剩余的元素拷贝到result中
return copy(first1, last1, copy(first2, last2, result));
}
5个参数，两对迭代器区间加一个输出迭代器参数，功能是把两个序列进行升序合并，可见对迭代器的操作就像用指针一样
std::reverse函数：
一样，从参考资料那里copy了：
// reverse，将序列反转
// 不同迭代器类型会影响性能，双向迭代器或者随机访问迭代器
// 因此需要设计两层函数，通过tag来区分不同的迭代器类型
// 底层函数，双向迭代器的版本，只能使用自增和自减
template <class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) {
--last;
while (first != last) {
swap(*first, *last);
if (++first == last)
return;
--last;
}
}
// 底层函数，随机访问迭代器的版本
template <class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {
// 修正last
--last;
// 随机访问迭代器的好处就是可以直接比较大小
while (first < last) {
swap(*first, *last);
++first;
--last;
}
}
// reverse对外接口
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
// 萃取出迭代器的类型
typedef typename iterator_traits<BidirectionalIterator>::iterator_category iterator_category;
// 根据参数类型的不同调用不同版本的函数
__reverse(first, last, iterator_category());
}
迭代器的实现
本段内容来自参考资料[5]
迭代器的实现
迭代器内部通过定义一个tag结构体来设定它的迭代器类别，同时在内部实现该迭代器支持的操作，在使用的时候通过iterator_traits萃取出迭代器内部定义的tag，来区分不同迭代器，调用不同迭代器版本的底层函数（就像上面的reverse函数）
五种迭代器对应的tag：
// 五种迭代器类别对应的tag
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{};// 随机访问迭代器，支持指针的所有运算操作
按照STL架构，迭代器需要提供五种类型用于traits萃取
// 具体的某个迭代器实现
// 任何迭代器都应该提供五种类型，以利于traits萃取，否则便是自别于整个STL架构，可能无法与其他STL组件顺利搭配
// 所以STL提供了一个iterators class，如果每个新设计的迭代器都继承自它，则可保证符合STL所需之规范
// 因为主要是为了实现萃取五种类型的功能，所以迭代器中只有这几种类型的信息
// Category被定义为迭代器类型，实参应该为上面五个tag的其中一个
template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
traits萃取迭代器中的类型信息：
// traits相当于萃取机，通过traits可以获得迭代器中的五种类型
// 一般类型的traits，获取迭代器中的类型信息
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category; // 普通类型的迭代器类型，类型值为五个迭代器tag结构体类型的其中一个
typedef typename Iterator::value_type value_type; // 普通类型的类型
typedef typename Iterator::difference_type difference_type; // 普通类型的迭代器中的指针差值类型
typedef typename Iterator::pointer pointer; // 普通类型的迭代器中的指针类型
typedef typename Iterator::reference reference; // 普通类型的迭代器中的引用类型
};
特化traits：
// 针对原生指针类型设计的traits偏特例化版本（特殊化）
// 原生指针也算是迭代器的一种
// 通过将模板参数设定为T*来进行模板参数特例化
// 表明只有模板参数为原生指针类型时，才会使用这个模板类
// 相当于将模板参数定为原生指针类型，所以五种类型不需根据迭代器中的信息就可以提前知道
// 也就是当T为原生指针类型时的五种类型
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category; // 原生指针应该是支持随机访问的，所以tag是随机访问的tag
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
list迭代器
下面是一个list迭代器，是一个双向迭代器，内部重载双向迭代器支持的运算符
template <class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*> iterator; // 迭代器类型
typedef __list_iterator<T, Ref, Ptr> self; //
typedef bidirectional_iterator_tag iterator_category; // 迭代器的类型为双向迭代器。tag用于在调用一些底层函数时识别这个迭代器的类型
typedef T value_type; // 元素的类型
typedef Ptr pointer; // 元素的指针类型
typedef Ref reference; // 元素的引用类型
typedef __list_node<T>* link_type; // 指向节点的指针类型
typedef size_t size_type; // 元素数目的类型
typedef ptrdiff_t difference_type; // 迭代器差值的类型
link_type node; // 迭代器内部的指向节点的指针
// 构造函数
__list_iterator() = default;
__list_iterator(link_type x) : node(x) {}
__list_iterator(const iterator& x) : node(x.node) {}
// 接着重载运算符
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
// 解引用，取数据值
reference operator*() const { return node->data; }
// 成员存取运算子的标准做法
pointer operator->() const { return &(operator*()); }
// 最后是自增自减
// 前缀自增
// 返回的是当前对象(*this)，所以可以返回引用
self& operator++() {
// node指向下一个节点
node = (link_type)(node->next);
return *this;
}
// 后缀自增
// 返回的是临时对象，所以不能返回引用
self operator++(int) {
self tmp = *this;
// this->node = (link_type)(node->next);
++*this;
return tmp;
}
// 前缀自减
self& operator--() {
node = (link_type)(node->prev);
return *this;
}
// 后缀自减
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
};