本文将深入介绍标准库中迭代器相关内容，迭代器是算法和容器之间的中介，它提供了一个标准接口来依次遍历容器中的元素，这样任何算法都可以在任何容器上工作，只要容器提供了算法所需的迭代器类别。

迭代器

标准库通过迭代器模式提供了访问容器元素使用的通用抽象。迭代器实际上是增强版的指针，这种指针知道如何遍历特定容器的元素，并且它还遵循C++标准中定义的特定接口，因此即使容器提供不同的功能，访问容器元素的代码也可以使用迭代器的统一接口。

C++标准定义了六大类迭代器：

获取迭代器

标准库中每个支持迭代器的容器类都为其迭代器类型提供了公共类型别名：iterator和const_iterator。允许反向迭代元素的容器还提供了名为reverse_iterator和const_reverse_iterator的公共类型别名，这样我们使用容器迭代器时就不需要关系它的实际类型了。

可以通过容器的成员方法来获得相应迭代器：

也能通过<iterator>提供的全局非成员函数来查找容器中的特定迭代器，函数名和上边的成员方法相同。建议使用非成员函数而不是成员方法，因为这会启用参数相关查找(ADL)：

// 以begin()为例
using std::begin;
auto iter = begin(...);

假设我们在自定义类的名称空间中为其特化这些非成员函数，那么ADL将会被启用，这样我们调用begin()的时候就会先在该名称空间中查找begin()的重载，如果找不到才会由于using std::begin去std里找。

PS: 还能用std::distance()计算容器的两个迭代器间距离。

迭代器萃取

一些算法实现可能需要关于迭代器的详细信息，这可以通过C++提供的iterator_traits类模板实现，它被定义在<iterator>中，提供如下类型别名：

• value_type：引用的元素类型
• difference_type：一种能够表示距离的类型，例如表示两个迭代器间元素的数量
• iterator_category：迭代器的类型（如input_iterator_tag等），这是C++20的内容
• pointer：指向元素的指针类型
• reference：元素引用的类型

例如，如下函数模板传入一个迭代器，它会尝试获取该迭代器的类型，并声明一个同类型的变量，值为迭代器所指向的元素：

template <typename IteratorType>
void test(IteratorType it)
{
    // 每当访问基于一个或多个模板类型参数的类型时，必须加上typename
	typename iterator_traits<IteratorType>::value_type temp;
	temp = *it;
	cout << temp << "\n";
}

示例

接下来可以利用上边学到的知识来自己实现一个find()函数：

template <typename Iter>
auto myFind(Iter begin, Iter end, 
			const typename iterator_traits<Iter>::value_type& value)
{
	for (auto iter{ begin }; iter != end; ++iter)
	{
		if (*iter == value)
		{
			return iter;
		}
	}
	return end;
}

它在给定范围内查找给定值，找不到就返回end迭代器。

流迭代器

标准库还提供了4个流迭代器，它们允许将输入和输出流视为输入和输出迭代器。以下是常见的流迭代器：

• ostream_iterator：输出流迭代器
• istream_iterator：输入流迭代器

还有两个不常用的：ostreambuf_iterator, istreambuf_iterator。

输出流迭代器

ostream_iterator可以接受一个元素类型参数，它的构造函数接收一个输出流和一个分隔符字符串，并用<<把每个元素写入流中。

例如有以下myCopy()函数模板，它将begin~end内的元素复制到target迭代器范围中：

template <typename InputIter, typename OutputIter>
void myCopy(InputIter begin, InputIter end, OutputIter target)
{
	for (auto iter {begin}; iter != end; ++iter, ++target)
	{
		*target = *iter;
	}
}

可以这样使用它，我们将一个vector里的元素复制到输出流中，并将其输出：

vector<int> i_vector{ 5, 6, 7 };
myCopy(cbegin(i_vector), cend(i_vector), ostream_iterator<int>{cout, " "});

可见仅需一行代码就能打印容器中的元素。

输入流迭代器

istream_iterator同理，不过它的构造函数只需接受一个输入流，并用>>把每个元素写入流中。

例如有以下sum()模板，它计算给定范围内所有元素的和：

template <typename InputIter>
auto sum(InputIter begin, InputIter end)
{
	auto sum{ *begin };
	for (auto iter {++begin}; iter != end; ++iter)
	{
		sum += *iter;
	}
	return sum;
}

可以这样使用它：

istream_iterator<int> numbersIter{ cin };
istream_iterator<int> endIter;
cout << "Sum:" << sum(numbersIter, endIter) << endl;

在Windows上，结束输入是Ctrl+Z；在linux上，结束输入是Ctrl+D。有了输入流迭代器的帮助，仅需一行就能读取任意数量的整数，并将其相加。

迭代器的适配器

标准库还提供了3类特殊的迭代器，被称为迭代器的适配器，都在<iterator>中定义：

1. 插入迭代器：
   • back_insert_iterator：使用push_back()将元素插入容器中。
   • front_insert_iterator：使用push_front()将元素插入容器中。
   • insert_iterator：使用insert()将元素插入容器中。
2. 逆向迭代器reverse_iterator：反转另一个迭代器的迭代顺序。
3. 移动迭代器move_iterator：它的解引用运算符自动将左值转换为右值引用，因此可以将其移动到新目标。

插入迭代器

前面实现的myCopy()不将元素插入到容器中，它只是用新元素替代范围内的旧元素。但如果将这些插入迭代器用作myCopy()等算法的目标迭代器，就会调用它们从而插入新元素。

下例在myCopy()中使用back_insert_iterator，将vectorOne的内容插入到vectorTwo中：

vector<int> vectorOne{ 1, 2, 3, 4 ,5 };
vector<int> vectorTwo;

// 使用std::back_inserter()构建back_insert_iterator
myCopy(cbegin(vectorOne), cend(vectorOne), back_inserter(vectorTwo));
// 也能用类模板参数推断(CTAD)
myCopy(cbegin(vectorOne), cend(vectorOne), back_insert_iterator{ vectorTwo });

同时也发现，当使用插入迭代器时，不需要提前调整目标容器的大小。

也能使用更细致的insert_iterator，它的构造函数有两个参数：要插入的容器和要插入的位置。使用它的一个好处是 允许使用关联容器(set/map)作为修改算法的目标。下例将vectorOne中的内容插入到setOne中：

vector<int> vectorOne{ 1, 1, 3, 4 ,5, 5 ,5 };
set<int> setOne;
myCopy(cbegin(vectorOne), cend(vectorOne), inserter(setOne, begin(setOne)));

逆向迭代器

reverse_iterator可以用相反的方向来遍历双向/随机访问迭代器。下例将此迭代器应用在myFind()中，以实现找到序列中最后一个元素位置：

vector<int> ivec{ 11, 22, 33, 22, 11 };

auto it1{ myFind(begin(ivec), end(ivec), 22) };
auto it2{ myFind(rbegin(ivec), rend(ivec), 22) };

if (it1 != end(ivec) && it2 != rend(ivec))
{
    cout << format("Found at pos {} going forward", distance(begin(ivec), it1)) << endl;
    cout << format("Found at pos {} going backward", distance(begin(ivec), --it2.base())) << endl;
}

由于it2的返回类型是reverse_iterator，可以调用it2.base()来获取其底层迭代器。但由于逆向迭代器的实现方式，返回的迭代器总是指向目标元素的前一个，因此要进行–。

移动迭代器

在源对象将在赋值操作或拷贝构造后被销毁的情况下，或者在使用std::move()时，可以用移动语义防止不必要的复制。move_iterator的解引用运算符自动将左值转换为右值引用，这意味着可以将左值移动到新的目标，而不必复制开销。

首先写一个支持移动语义的类，为了演示用，只让构造函数和运算符输出日志：

class Moveable
{
public:
	Moveable()
	{
		cout << "默认构造函数" << endl;
	}
	Moveable(const Moveable& src)
	{
		cout << "复制构造函数" << endl;
	}
	Moveable(Moveable&& src) noexcept
	{
		cout << "移动构造函数" << endl;
	}
	Moveable& operator= (const Moveable& rhs)
	{
		cout << "复制赋值运算符" << endl;
		return *this;
	}
	Moveable& operator= (Moveable&& rhs) noexcept
	{
		cout << "移动赋值运算符" << endl;
		return *this;
	}

};

然后写程序测试一下：

cout << "创建vecSource:" << endl;
vector<Moveable> vecSource;
cout << "创建Moveable对象:" << endl;
Moveable mv;
cout << "给vecSource中添加mv:" << endl;
vecSource.push_back(mv);
vecSource.push_back(mv);

在VS2022中的输出结果为：

第一个.push_back()的调用触发复制构造函数，将mv复制到vector中。第二个.push_back()的调用触发vector的扩容机制，它会触发移动构造函数将第一个mv从旧的内存空间移动到新的内存空间中，并进行第二个mv的复制操作。

接下来创建vector的副本：

cout << "创建vecSource的副本:" << endl;
vector<Moveable> vecTmp{ cbegin(vecSource), cend(vecSource) };

它会调用两次复制构造函数，将vecSource中的两个mv各复制一次。

如果通过使用std::make_move_iterator()构造的move_iterator去创建副本，就会调用两次移动构造函数：

cout << "创建vecSource的副本:" << endl;
vector<Moveable> vecTmp{ make_move_iterator(begin(vecSource)), make_move_iterator(end(vecSource)) };

这样做可以减小开销，但需要注意的是，一旦一个对象被移动到另一个对象，就不应该再使用源对象了。

【TODO】在C++20中引入了范围库，它是迭代器之上的抽象层，消除了不匹配的迭代器错误，待学习……

参考资料

• 飘零的落花 - 现代C++详解
• C++20高级编程