迭代器分类
C++ STL 中根据移动能力将迭代器分成了 5 类：
-
Input Iterator 输入迭代器，只支持 operator++ 操作。
-
Output Iterator 输出迭代器，只支持 operator++ 操作。
-
Forward Iterator 前向迭代器，只支持 operator++ 操作。
-
Bidirectional Iterator 双向迭代器，支持 operator-- 和 operator++ 操作。
-
Random Access Iterator 随机访问迭代器，不仅支持 operator-- 和 operator++ 操作，还可以与整数进行算术运算。
int main()
{
// 1.输入迭代器, 只能读缓冲区
// 这样会直接进入读取状态一直读取int, 直到状态出错或遇到EOF
// 比如输入了非数字, ctrl + d等等
istream_iterator<int> initer(cin);
int x = *initer; // 从缓冲区读取第一个数到变量中
// 2.输出迭代器, 只能写到某个地方
ostream_iterator<int> oiter(cout, " "); // 绑定到标准输出, 分隔符为空格字符串
vector<int> v{1, 2, 3, 4};
copy(v.begin(), v.end(), oiter); // 输出1 2 3 4
cout << endl;
// 3.前向迭代器, unordered_xxx系列的关联式容器的迭代器就是这个类型的
// 大部分能读能写, set 系列由于键值合一, 不能够写
// map 中 key 不可更改, value 可以
unordered_map<int, char> m{{1, 'a'}, {2, 'b'}};
unordered_map<int, char>::iterator mit = m.begin();
while (mit != m.end()) {
mit->second = 'c'; // 可以修改 value
++mit; // 不支持 operator--
}
// 4.双向迭代器, list 的迭代器就是该类型的
list<int> l{1, 2, 3};
list<int>::iterator lit = l.begin(); // 指向 1
++lit; // 指向 2
--lit; // 回到 1
*lit = 666; // 更改
// 5.随机访问迭代器, vector 和 deque 的迭代器就是该类型的
// 例如输出 vecor 的最后一个元素
vector<int>::iterator vit = v.begin();
cout << *(vit + v.size() - 1) << endl; // 支持与整数运算
return 0;
}
忽略了头文件，自行添加。
编译器多态
C++ STL 中很多算法会根据迭代器参数的类型来选择最优的实现方法，以 advance 为例，它的作用是将给定的迭代器移动指定步数，实现如下：
template<typename InputIterator, typename Distance>
void advance(InputIterator& it, Distance n)
{
// concept requirements -- taken care of in __advance
typename iterator_traits<InputIterator>::difference_type d = n;
std::__advance(i, d, std::__iterator_category(it));
}
可以看到它内部转调了 std::__advance，注意到它的第三个参数 std::__iterator_category(it)。
该方法根据传入的迭代器返回一个迭代器类型对象，一共 5 种，迭代器类型命名类似于 xxx_iterator_tag。
然后std::__advance共有如下版本：
针对输入迭代器的：
template<typename InputIterator, typename Distance>
void __advance(InputIterator& it, Distance n, input_iterator_tag)
{
while (n--) ++it;
}
针对前向迭代器的：
template<typename InputIterator, typename Distance>
void __advance(InputIterator& it, Distance n, forward_iterator_tag)
{
__advance(it, n, input_iterator_tag()); // 直接转调
}
针对双向迭代器的：
template<typename InputIterator, typename Distance>
void __advance(InputIterator& it, Distance n, bidirectional_iterator_tag)
{
// 可以双向移动
if (n >= 0)
while (n--) ++it;
else
while (n++) --it;
}
针对随机访问迭代器的：
template<typename InputIterator, typename Distance>
void __advance(InputIterator& it, Distance n, random_access_iterator_tag)
{
it += n; // 直接加, 跳着走, 爽得一批
}
当我们调用 advance 时，编译器根据第三个参数（迭代器类型）选择最优模板。