容器额外的迭代器

一、什么是迭代器?

迭代器设计思维是STL的关键所在。迭代器（iterators）是一种抽象的设计概念，现实程序语言中没有直接对应这个概念的实物，在《Design Patterns》对迭代器的定义如下：提供一种方法，使之能够依序巡防某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表达形式。STL的中心思想在于，将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以贴胶着剂将他们撮合起来[1]。本文讨论的重点不在于迭代器的实现，而在于如何使用，如何利用迭代器加速、巧妙的完成项目设计任务。

迭代器的编程假定：左闭合。假定begin和end构成一个合法的迭代器范围，有，

• 空范围。begin=end；
• 至少一个。begin!=end；
• 可递增。若干次begin递增可以到达end；

空迭代器begin和end都指向尾后迭代器（One pass the last element），位于该位置的迭代器可以指定位置，但是不能使用其内容。

二、迭代器种类及使用

迭代器是为了灵活操纵容器的，除了每个类自己的begin和end成员，标准库在iterator还定义了一些额外的迭代器帮助我们完成指定任务。

• 插入迭代器（insert iterator），向指定容器插入元素；
• 流迭代器（stream iterator），遍历相关的IO流；
• 反向迭代器（reverse iterator），与普通迭代器前进方向相反（除了forward_list，其他容器都有反向迭代器）；
• 移动迭代器（move iterator），专门用来移动其中的元素的。

2.1 插入迭代器

普通迭代器重点在于如何访问、取值，而插入迭代器通常在泛型算法作为输出迭代器。这个对一个指向某内容的插入迭代器使用*符号后赋值，等价于往这个位置插入一个新的元素，此外运算符++ --的结果仍然是同一个迭代器，这样的好处在于我们无需处理迭代器就可以实现往同一位置插入元素。至于是指向元素前插值还是元素后插值，取决于具体的插入迭代器种类：

• back_inserter 使用push_back将元素追加到迭代器所指位置之后；
• front_inserter 使用push_front将元素追加到迭代器所致位置之前；
• inserter 使用insert将元素插入到指定迭代器之前。

front_inserter、back_inserter正如其名字一样，分别是往指向元素之前和之后插入元素；inserter和我们常用的容器insert方法一样，是往指向前插入元素的。

我们可以通过关键字std::back_inserter、std::front_inserter 和std::inserter ，来获得一个序列的指定位置的插入迭代器。

std::inserter(vec,position_iter); //指向vec的position_iter的前插器
std::back_inserter(vec);		  //指向vec的end的后插器	
std::front_inserter(vec);		  //指向vec的begin的前插器

front_inserter是inserter的特例，当inserter的位置选择是begin时，两者等效，即：

std::inserter(vec,vec.begin());
std::front_inserter(vec);//等价表达

值得注意的是不是所有的容器都支持所有的插入迭代器，

• 支持push_backback_inserter；
• 支持push_frontfront_inserter；
• 支持insertinserter；

容器种类push_frontpush_backinsertvectorNYYstringNYYlistYYYforward_listYNNdequeYYYarrayNNN

可见，array不支持任何插入迭代器；deque、list支持全部插入迭代器；vector、string支持inserter和back_inserter；forward_list只支持front_inserter。

下面是关于插入迭代器的例子：

list ilst{ 1,2,3 };
back_inserter(ilst)=4;//1 2 3 4
front_inserter(ilst) = 0;//0 1 2 3 4
vector dvec{2,3,4};
back_inserter(dvec)=5;//2 3 4 5
front_inserter(dvec)=1;//error,vector不支持push_front
inserter(dvec,dvec.begin())=1;//1 2 3 4 5
inserter(dvec,dvec.end())=6;//1 2 3 4 5 6

插入迭代器+STL算法可以完成很多有意思的事情，std::copy第三个参数要求是输入迭代器（只写不读 单遍扫描 只能递增）

std::list lst{1,2,3,4,6};
std::list lst3(lst.size());//需要提前开辟空间
std::copy(lst.cbegin(), lst.cend(), lst3.begin());

对于一个普通迭代器，默认从所指位置开始写元素，对于一个空容器的begin()其至等于尾后迭代器，显然写入尾后迭代器不是一个好主意。可以刚学的back_inserter，和普通迭代器不同的地方在于，往这个迭代器写元素等于往其后写入一个数值，编译器将会帮你分配空间。

std::list lst{1,2,3,4,6};
std::list lst3;// (lst.size());
std::copy(lst.cbegin(), lst.cend(), std::back_inserter(lst3));

再看一个例子：

std::vector lst{1,2,3,4,6};
std::vector lst3{22,33,44,55,66};// (lst.size());
std::copy(lst.cbegin(), lst.cend(), std::inserter(lst3,lst3.begin()));

结果是：1 2 3 4 6 22 33 44 55 66，为啥?因为插入位置永远是更新后序列的第一个，这种方式实现了类似append_front的功能。如果lst3是空，那么就等价于std::back_inserter的结果。如果插入位置是最后一个，那么等价于append_back一个序列。如果在中间，那么则是append_middle！下次你要用insert一个序列，不妨试试插入迭代器。

最后一个例子：

std::list lst{1,2,3,4,6};
std::list lst3{22,33,44,55,66};
std::copy(lst.cbegin(), lst.cend(), std::front_inserter(lst3));

这个例子实现了倒序插入，相当于实现了reserse_append_front！特别的，若lst3是一个空序列，则lst3结果将是lst的倒序，相当于实现了lst的reserve！

std::list lst{1,2,3,4,6};
std::list lst3;
std::copy(lst.cbegin(), lst.cend(), std::front_inserter(lst3));//lst3结果与lst.reverse()结果一样

list本身就有实现reverse这个迭代器可能没有这么吸引人，但是如果你需要对vector进行一个reverse就相当好用了。

2.2 流迭代器

虽然流不是一个容器，为了支持泛型算法，标准库支持两种流对象的读写，分别是：

• 输入流迭代器 （istream_iterator）
• 输出流迭代器（ostream_iterator）

2.2.1 输入流迭代器

和插入迭代器不同，插入迭代器直接调用函数获取迭代器，而不需要给定类型，流迭代器的定义是一个类模板，需要指定迭代器类型，如istream_iterator内容为int的输入流迭代器，构造函数是IO流对象。除了上述不同外，流迭代器支持的操作更为丰富：

构造函数或操作含义istream_iterator in(is)is流构造流迭代器istream_iterator end尾后流迭代器in1==in2 in1!=in2读取类型相同，如果都是尾后迭代器或相同输入流则相等；反之不等*in返回流当前所指元素值in->*(in).mem++in in++读取元素的类型定义的>>运算符从输入流读取下一个值

看看实际的例子：

std::vector vec;
istream_iterator int_iter(cin);
istream_iterator eof;//空容器，指向的就是尾后迭代器
while (int_iter != eof)
{
	vec.push_back(*int_iter++);
}
	
for (auto e : vec) std::cout