C++ 迭代器，了解一下？

@[捂脸熊](http://img.uoj.ac/utility/bear-facepalm.jpg)那我~~咬着~~要这迭代器有何用？

别急别急，迭代器还是有几个定义好的分类的，标准库内的迭代器何时会非法化也有严格限制。

在说这个之前，先提一嘴迭代器的一个辅助类型```std::iterator_traits```，其一般化定义是长这个样子滴：
```cpp
template< class Iterator >
struct iterator_traits {
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
};

什么？你问我这五个鬼东西干啥用的？~~把他们翻译成中文就好了~~ ←真的如此，STL的命名还是挺清楚的哇

其中标准库自带了五个用于```iterator_category```的空类型，分别对应下方的前五种迭代器：
```cpp
struct output_iterator_tag { };
struct input_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 { };

返回的还是这个迭代器本身，所以不要做出```a = *it```这种操作，~~伦家明明是输出迭代器不要把窝搞成输入嘛~~~

实际上这个不是输出迭代器标准定义，但是STL中输出迭代器的实例就是这样的

仅资瓷单趟算法

啥是单趟算法？只需要遍历这个序列一次的算法，不需要把当前位置迭代器记存一个副本，等以后再使用。

因为该序列上同一时间可能只有一个位置的迭代器是合法的

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)输出迭代器这个名字看起来就是用于输出内容的，STL有两个小玩意叫做```std::ostream_iterator```和```std::ostreambuf_iterator```，把输出流包装了一下
```cpp
// 构造一个输出T类型的输出迭代器
// 第一个参数为绑定到的流
// 第二个参数为每次输出后输出的字符串，可省
std::ostream_iterator<T> it(std::cout, " ");
T t;
it = t; //这些都等同于 std::cout << t << " "
*it = t;
it++ = t;
++it = t;
*it++ = t;

// 跟上面那个一样，不过变成输出字符类型，也没有第二个参数了
std::ostreambuf_iterator<char> it(std::cout);

it = 'A'; // 等同于 std::cout << 'A'
*it = 'A';
...

可以读取啦，但是不一定可以写入，因为返回的引用可能是```const```的（下面的输入流迭代器就如此）

为什么是“可转换为```value_type```的引用”呢？

~[](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)```std::vector<bool>```为了节约空间，每一个 0101 位占一个bit而非一个byte，但是没有办法返回一个bit的对象，只能返回一个包装好的代理类辣，所以```std::vector<bool>::iterator::reference```是代理类的引用而非位引用或```bool&

~~C++真是一门难学的语言~~![](https://i.loli.net/2018/08/11/5b6eca17075cd.jpg)

可比较相等和不等

```operator*```返回当前元素

可使用```operator->```访问成员

仅资瓷单趟算法

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)把输出迭代器的栗子的输出改成输入就好了

emmmmm...等等，那EOF咋判断？![思考熊](http://img.uoj.ac/utility/bear-thinking.gif)

默认构造的输入流迭代器就代表EOF，判一下相等/不等就好了
```cpp
std::vector<int> v;
std::istream_iterator<int> i1(std::cin), i2;
while(i1 != i2) v.push_back(*i1++);

![](https://i.loli.net/2018/08/12/5b6fc6e27d42a.jpg)那这个输入/输出迭代器比直接用```std::cin/cout```还麻烦啊！！！有啥用啊！！！

别急着骂我，主要是配合各种STL函数食用的

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)众所周知，```std::vector```有这样一个构造函数，接收一对迭代器，将 ```[begin,end)``` 范围内元素拷贝入容器（```std::vector<>::assign()```也是）

所以上面的代码可以改写成这样
```cpp
std::vector<int> v(std::istream_iterator<int>(std::cin), std::istream_iterator<int>());

提供多趟保证

可以放心地把迭代器存起来辣

不会因为解引用并赋值导致迭代器非法化

自增```it```的副本不改变解引用```it```得到的值

保证若```ita == itb```则

- 要么二者都不可解引用，要么指向同一对象
- ```++ita == ++itb

## 双向迭代器
```cpp
typedef bidirectional_iterator_tag iterator_category;

## 随机访问迭代器
```cpp
typedef random_access_iterator_tag iterator_category;

指向数组元素的指针会用吧？一样的

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)```std::vector, std::array, std::deque, std::string```的```iterator```、指向数组元素的指针

## 相接迭代器

是迭代器

其所指向的逻辑相邻元素也在内存中物理上相邻

任意合法的```*(a + n)```等价于```*(std::addressof(*a) + n)

因为```operator&```是可以重载的...它可以返回任何奇怪的东西

所以C++11引入了```std::addressof```函数，专门用于返回一个对象的地址，其实现用了一些小trick，C++11及之后所有的标准库实现取地址用的都是这个函数而不是```operator&

![](https://i.loli.net/2018/08/12/5b6fd12ac0062.jpg)

~~C++真是一门难学的语言~~![](https://i.loli.net/2018/08/11/5b6eca17075cd.jpg)

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)```std::vector, std::array, std::basic_string_view```的```iterator```、指向数组元素的指针

## 可变迭代器

是输入迭代器

是输出迭代器

也就是可以读也可以写的

![](https://i.loli.net/2018/08/11/5b6ecf17aea62.jpg)所有STL容器的```iterator```（```const_iterator```除外）、指针（常量指针除外）

## 类型总结

![](https://i.loli.net/2018/08/11/5b6edd403bc5f.png)

来源cppreference

## 相对用的比较多的迭代器适配器

```std::reverse_iterator

```std::move_iterator