Xeonacid
2018-08-11 17:32:56
由于作者是个C++鶸，如果本文有任何错误，烦请不吝指出。（有的地方已知描述是不完整的，但是与指针行为一致，或鉴于多数看这篇文章的都是算法竞赛选手，抑或考虑实际，刻意忽略掉辣）
迭代器(Iterator)：一种“能够迭代某序列内所有元素”的对象
指针都知道吧？不知道的先出门左转了解一下
迭代器：指针的抽象，指针是迭代器的子集
#include <iterator>所有迭代器都能做的操作：
int main(){
/*
* suppose:
* T t;
* container<T> v1{t}, v2;
* container<T>::iterator
* container<T>::begin()
* container<T>::end()
* have been defined here
*/
container<T>::iterator ita = v1.begin(), itb = v2.begin();
*ita;
using std::swap;
swap(ita, itb);
++ita;
}emmmm...这些跟指针没什么差别对吧。
真的没差别吗？
其实是有的...
指针不可能随便解引用或者交换一下，甚至你什么都没做，就非法化了对吧。但是就“迭代器”本身，不加任何限制的情况下，其只是一个可以做上述操作的类而已啦，随时有可能被非法化。
*it返回什么是未指定的，返回void也合fa♂ 三去法，意味着在这里你可能什么也做不了2333333
那我咬着要这迭代器有何用？
别急别急，迭代器还是有几个定义好的分类的，标准库内的迭代器何时会非法化也有严格限制。
在说这个之前，先提一嘴迭代器的一个辅助类型std::iterator_traits，其一般化定义是长这个样子滴：
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;
};很简单对吧，直接从迭代器类型本身拿来了这几个成员，标准库提供了对于指针的特化，毕竟指针没有这些成员。
只有使std::iterator_traits<T>合法且含有上述五个成员，且能执行前面列出的那些迭代器操作的T类型才满足迭代器概念。
什么？你问我这五个鬼东西干啥用的？把他们翻译成中文就好了 ←真的如此，STL的命名还是挺清楚的哇
其中标准库自带了五个用于iterator_category的空类型，分别对应下方的前五种迭代器：
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 { };迭代器分类的依据是其可以进行的操作
由上至下越来越像指针，越来越正常
typedef output_iterator_tag iterator_category;operator*解引用（空操作）返回的还是这个迭代器本身，所以不要做出a = *it这种操作，伦家明明是输出迭代器不要把窝搞成输入嘛~
实际上这个不是输出迭代器标准定义，但是STL中输出迭代器的实例就是这样的
啥是单趟算法？只需要遍历这个序列一次的算法，不需要把当前位置迭代器记存一个副本，等以后再使用。
因为该序列上同一时间可能只有一个位置的迭代器是合法的
输出迭代器这个名字看起来就是用于输出内容的，STL有两个小玩意叫做std::ostream_iterator和std::ostreambuf_iterator，把输出流包装了一下
// 构造一个输出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';
...STL还有几个用于插入序列的迭代器适配器，以及配套的为了方便的函数模板
std::deque<int> q;
std::back_insert_iterator< std::deque<int> > it1(q);
// 等同于 auto it1 = std::back_inserter(q);
it1 = 1; // 等同于 q.push_back(1)
*it1 = 1;
...
std::front_insert_iterator< std::deque<int> > it2(q);
// 等同于 auto it2 = std::front_inserter(q);
it2 = 1; // 等同于 q.push_front(1)
*it2 = 1;
...
std::insert_iterator< std::deque<int> > it3(q, q.begin());
// 等同于 auto it3 = std::inserter(q);
it3 = 1; // 等同于 q.insert(q.begin(), 1)
*it3 = 1;
...
这玩意从名字看上去就与上面那个有许多相似之处，实际上也是
typedef input_iterator_tag iterator_category;实际上输入迭代器标准定义不可默认构造，向前迭代器才可以，但是STL中输入迭代器的实例都是可以的
operator*返回reference，为可转换为value_type的引用可以读取啦，但是不一定可以写入，因为返回的引用可能是const的（下面的输入流迭代器就如此）
为什么是“可转换为value_type的引用”呢？
std::vector<bool>为了节约空间，每一个std::vector<bool>::iterator::reference是代理类的引用而非位引用或bool&
PS:std::vector<bool>不是容器，不满足容器的要求，下文提到std::vector时均不包含std::vector<bool>
C++真是一门难学的语言
operator*返回当前元素operator->访问成员把输出迭代器的栗子的输出改成输入就好了
emmmmm...等等，那EOF咋判断？
默认构造的输入流迭代器就代表EOF，判一下相等/不等就好了
std::vector<int> v;
std::istream_iterator<int> i1(std::cin), i2;
while(i1 != i2) v.push_back(*i1++);同一个位置的元素可以读多次，不过不能倒回来读
std::istream_iterator<int> i1(std::cin);
int a = *i1, b = *i1, c = *++i1, d = *i1++; // 前提未EOF
std::istreambuf_iterator同理，只不过读入的变成了字符
那这个输入/输出迭代器比直接用std::cin/cout还麻烦啊！！！有啥用啊！！！
别急着骂我，主要是配合各种STL函数食用的
众所周知，std::vector有这样一个构造函数，接收一对迭代器，将std::vector<>::assign()也是）
所以上面的代码可以改写成这样
std::vector<int> v{std::istream_iterator<int>(std::cin), std::istream_iterator<int>()};一行结束，简单多了对吧。输出的也同理
别问我这个在算法竞赛中的应用是什么，我知道你们都不会在比赛中用流式输入输出的，但是这些都是C++这门语言的重要组成部分，毕竟C++不是只用来算法竞赛的对吧
终于到比较正常的用的比较多的了
typedef forward_iterator_tag iterator_category;reference为引用可以放心地把迭代器存起来辣
不会因为解引用并赋值导致迭代器非法化
自增it的副本不改变解引用it得到的值
保证若ita == itb则
++ita == ++itb可以看成不可自减和随机访问的指针
std::forward_list和无序关联容器（哈希容器）的iterator
typedef bidirectional_iterator_tag iterator_category;行为与自增都类似
可以看成不可随机访问的指针
std::list和有序关联容器的iterator
typedef random_access_iterator_tag iterator_category;operator[]指向数组元素的指针会用吧？一样的
std::vector, std::array, std::deque, std::string的iterator、指向数组元素的指针
任意合法的*(a + n)等价于*(std::addressof(*a) + n)
顺便提一句，为什么是std::addressof(*a)而不是&(*a)呢
因为operator&是可以重载的...它可以返回任何奇怪的东西
所以C++11引入了std::addressof函数，专门用于返回一个对象的地址，其实现用了一些小trick，C++11及之后所有的标准库实现取地址用的都是这个函数而不是operator&
那么问题来了，如何在C++11之前将一个重载了operator&的类放入标准库容器呢？
C++真是一门难学的语言
std::vector, std::array, std::basic_string_view的iterator、指向数组元素的指针
也就是可以读也可以写的
所有STL容器的iterator（const_iterator除外）、指针（常量指针除外）
来源cppreference
std::reverse_iterator反向迭代器，原迭代器+变-、-变+，提供原迭代器提供的所有功能
STL容器的rbegin(), rend()返回的就是这个
std::move_iterator原迭代器需至少为输入迭代器，其reference为右值引用
关于std::move和右值引用...那应该是另一篇文章的内容了
See https://zh.cppreference.com/w/cpp/container#.E8.BF.AD.E4.BB.A3.E5.99.A8.E9.9D.9E.E6.B3.95.E5.8C.96
适配器均取决于其底层容器
（溜了溜了）
emmmm...还是说几个常见的吧
所有只读操作无
std::vector扩大重分配、std::deque插入+扩大重分配+非首尾擦除：全部
std::vector插入/擦除（无重分配）：插入位置及其后
std::deque首尾擦除（无重分配）：首尾
链表+有序关联容器：插入无，擦除仅被擦除元素
（毕竟它们是节点形式出现的）
哈希容器：
插入导致重哈希：全部
插入未导致重哈希：无
擦除：仅被擦除元素
在不需要返回值的情况下尽可能使用前置递增/递减，而非后置
后置比前置慢
这个对于内置类型是假的，开不开优化都一样
但是对于非内置类型就不一定了
像迭代器这种实现相对比较简单的类（绝大部分容器的迭代器底层都只是一个或几个指针），开了优化可能会被优化成一样
但是如果是复杂一点的就不一定了2333333
小建议：（求不喜勿喷）干脆全改成前置好了，反正不会慢对吧，要不然写的时候还要想一下是不是内置类型，也挺麻烦的
使用std::array而非原生数组
窝个人觉得，OOP的封装性的优势在这体现地淋漓尽致，不用管底层怎么搞的，用就好辣
其成员函数什么的都是STL的命名格式，会用一个STL容器就会用其他的_(:з」∠)_
一维数组还好办，二维及以上的话指针、sizeof什么的比封装好的麻烦多了（表喷窝TAT，再熟练也改变不了它麻烦的事实呀）
常数这个无需担心，std::array只是把原生数组封装了一下，效率没有任何差别，成员函数都是内联的
然鹅...这个东西是C++11才有的，C++98的话也可以自己封装一下嘛，几分钟就写完了（逃）
ISO/IEC 14882:2017 Programming languages -- C++:952-986.
cppreference.com.
（德）约祖蒂斯（Josuttis,N.M.）著；侯捷译.C++标准库：第2版[M].北京：电子工业出版社，2015.6：433-474.