0x00 前言

文章中的文字可能存在语法错误以及标点错误，请谅解；

如果在文章中发现代码错误或其它问题请告知，感谢！

本文档为个人边学习边记录的C++笔记，非教程，笔记中会存在引用他人文章内容的部分，被引用的原文不会被特殊标记出来，但会在参考文档中给出原文链接

0x01 迭代器

迭代器是泛化的指针，STL算法利用迭代器对存储在容器中的元素序列进行遍历，迭代器提供了访问容器中每个元素的方法。虽然指针也是一种迭代器，但是迭代器却不仅仅是指针。指针可以指向内存中的一个地址，通过这个地址就可以访问相应的内存单元；而迭代器更为抽象，它可以指向容器中的一个位置，我们不必关心这个位置对应的真正物理地址，只需要通过迭代器访问这个位置的元素。

在STL中，容器是封装起来的类模板，其内部结构无从知晓，而只能通过容器接口来使用容器。

算法是要适用多种容器，而每一种容器中存放的元素又可以是任何类型，如何用普通指针来充当中介呢？这时候就必须使用更为抽象的“指针”，这就是迭代器。

使用迭代器，算法函数可以访问容器中指定位置的元素，而无须关系元素的具体类型。

1. 输入流迭代器和输出流迭代器

1）输入流迭代器

输入流迭代器用来从一个输入流中连续的输入某种类型的数据，它是一个类模板。例如：

template<class T>istream_iterator<T>;

其中T是使用该迭代器从输入流中输入数据的类型。类型T要满足两个条件：有默认构造函数；对该类型的数据可以使用“>>”从输入流输入。一个输入流迭代器的实例需要由下面的构造函数来构造：

istream_iterator(istream& in);

istream_iterator类模板有一个默认构造函数，用该函数构造出的迭代器指向的就是输入流的结束位置，将一个输入流与这个迭代器进行比较就可以判断输入流是否结束。

2）输入流迭代器

输出流迭代器用来向一个输出流中连续输出某种类型的数据，它也是一个类模板。例如：

temp;ate<class T>ostream_iterator<T>

其中T表示向输出流中输出数据的类型，类型T需要一个功能：对该类型的数据可以使用"<<"向输出流输出。一个输出流迭代器可以用下面两个构造函数来构造：

ostream_iterator(ostream& out);
ostream_iterator(ostream& out, const char *delimiter);

构造函数的参数out表示将数据输出到输出流。参数delimiter是可选的，表示两个输出数据之间的分隔符。

例：从标准输入读入几个实数，分别将它们的平方输出：

#include<iterator>
#include <iostream>
#include<algorithm>

using namespace std;

double square(double x){
	return x * x;
}
int main() {
	transform(istream_iterator<double>(cin), istream_iterator<double>(),
				ostream_iterator<double>(cout, "\t"), square);
	cout << endl;
	return 0;
}

运行结果：
输入：

0.5 1.1 0 -3 0.1

输出：

0.25	1.21	0	9	0.01

由于该程序会从标准输入流中读取数据直到输入流结束，运行该程序时，输入完数据后，在windows下需要Ctrl+Z和回车键，在Linux下需要按Ctrl+D键，表示标准输入结束。

2. 迭代器分类

STL根据迭代器的功能，将它们分为5类，这五类对应于5个概念，这5个概念之间关系图如下所示：
在这里插入图片描述

1）输入迭代器

输入迭代器可以用来从序列中读取数据，但是不一定能够向其中写入数据。

输入迭代器支持对序列进行不可重复的单向遍历。

输入迭代器只使用于作为那些只需要遍历序列一次的算法的输入。

2）输出迭代器

输出迭代器允许向序列中写入数据，但是并不保证可以从其中读取数据。

输出迭代器也支持对序列进行单向遍历。

3）前向迭代器

前向迭代器这一概念是输入迭代器和输出迭代器这两个概念的子概念，它既支持数据读取，也支持数据写入。

前向迭代器支持对序列进行可重复的单向遍历。

4）双向迭代器

双向迭代器这一概念是单向迭代器的子概念。在单向迭代器所支持的功能基础上，它又支持迭代器向反向移动。

5）随机访问迭代器

随机访问迭代器这一概念是双向迭代器的子概念。在双向迭代器的基础上，它又支持直接将迭代器向前或向后移动n个元素，因此随机访问迭代器的功能几乎和指针一样。

通过向量容器vector的begin和end函数得到的迭代器就是随机访问迭代器，指针也是随机访问迭代器。

3. 迭代器的区间

STL算法的形参中常常包括一对输入迭代器，用它们所构成的区间来表示输入数据的序列。

例：综合运用几种迭代器的示例

#include<algorithm>
#include <iterator>
#include<vector>
#include<iostream>
using namespace std;

template<class T, class InputIterator, class OutputIterator>
void mySort(InputIterator first, InputIterator last, OutputIterator result){
	vector<T>s;
	for(;first!=last;++first)
		s.push_back(*first);
	sort(s.begin(), s.end());
	copy(s.begin(), s.end(), result);
}
int main() {
	double a[5] = {1.2, 2.4, 0.8, 3.3, 3.2};
	mySort<double>(a, a+5, ostream_iterator<double>(cout, " "));
	cout << endl;
	mySort<int>(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, ""));
	cout << endl;
	return 0;
}