tags:
- CppSTL Iterator - A Generic Pointer Wrapper (Part I)
在 cppreference 对迭代器的介绍中讲到：迭代器是一系列泛化的指针，和指针不同的是，迭代器是一个类对象。迭代器通过抽象化指针的基本操作来为不同数据结构提供统一的遍历和访问接口。通过这层封装，可以让函数模板和算法配合标准迭代器使用，实现更广泛的适用性。
我们用一个例子来看看迭代器的强大之处。假设我们定义了一个 std::vector<int>：
#include <vector>
#include <iostream>
int main(){
std::vector<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
return 0;
}
我们先来看看不使用迭代器的遍历会是如何的。最常见的 raw loop，和迭代器没有任何相关性：
for(size_t i = 0; i < vec.size(); ++i){
std::cout << vec[i] << std::endl;
std::cout << &vec[i] << std::endl;
}
在使用 raw loop 的方式中，你需要知道容器对象的大小信息。可喜的是 STL 容器中含有获取对象大小信息的成员函数。
在 C++03 后，你可以用迭代器遍历整个容器对象，这样做的好处是：你不需要知道容器有多大。而且使用迭代器还能很好的满足对一些非线性的数据结构的遍历。如 std::map （底层实现为红黑树）等，你不用担心其底层如何实现也能遍历。
for(std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it){
std::cout << *it << std::endl;
// std::cout << it << std::endl;
std::cout << &*it << std::endl; // The address of element that iterator points
std::cout << &it << std::endl; // The address of iterator object
}
在使用迭代器的循环中，我们定义并初始化了一个 std::vector<int>::iterator ，让我们定义的迭代器 it 指向 std::vector 的首元素。在指向容器尾后位置之前，迭代器不停地迭代。尾后迭代器(past-the-end iterator) 指向容器最后一个元素的下一个位置。不可以解引用。
迭代器是一个类类型，它的核心设计目标之一就是模拟指针的行为。由于其这种特性，迭代器必须重载 operator* 。如此，你可以直接通过 *it 来访问元素值，和指针变量一样。
相比 Raw loop，使用迭代器方式循环的逻辑并没有改变。只不过我们开始操作的是一个迭代器（模拟指针）对象了，因此，在我们想要查看元素内容时，我们需要对其解引用。然而，迭代器并不等同与指针，它是一个类对象，你不能通过 std::cout << it << std::endl 打印迭代器指向元素的地址（因为迭代器类没有重载 operator<<）。
你可以使用 &*it 来获取迭代器指向元素的地址。如果你对迭代器对象取地址，你得到的只是迭代器的地址（栈上）。
auto在 C++11 引入 auto 关键字之后，一切来得更加方便丝滑。
for(auto it = vec.begin(); it != vec.end(), ++it){ // Same... }
同 auto ，C++11 还引入了范围for循环。这是一个语法糖，是对循环的进一步封装，从而暴露给用户的接口变得更简洁了。一般，我们会这样使用范围for循环：
for(auto elem : vec){
std::cout << elem << std::endl;
}
for(const auto& elem : vec){ // Avoid copying
std::cout << elem << std::endl;
}
我们去掉一层封装，看看没有类型推断的话是什么样子：
for(int elem : vec){
std::cout << elem << std::endl;
}
在褪去一层封装，看看其丑陋的面貌（GCC）：
#include <vector>
#include <iostream>
int main()
{
std::vector<int, std::allocator<int> > vec = std::vector<int, std::allocator<int> >{std::initializer_list<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, std::allocator<int>()};
{
std::vector<int, std::allocator<int> > & __range1 = vec;
for(__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > __begin1 = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >(__range1.begin()), __end1 = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >(__range1.end());
__gnu_cxx::operator!=(__begin1, __end1);
__begin1.operator++()) {
int elem = __begin1.operator*();
std::cout.operator<<(elem).operator<<(std::endl);
}
}
return 0;
}
好乱，但实际上很简单。我们来看看范围for的实质上是什么。for循环的第一个 statement 定义了一个指向 begin 的迭代器；第二个 statement 是一个判断，这里判断迭代器是否指向 end；第三个 statement 当然是迭代器++操作。
在 C++ 中，我们有6种不同的迭代器，分别是：LegacyOutputIterator、LegacyInputIterator、LegacyForwardIterator、LegacyBidirectionalIterator、LegacyRandomAccessIterator 和 LegacyContiguousIterator。C++ 将这些 C++17 的标准库迭代器称为 LegacyIterator。
这些不同类型的迭代器有着不同的功能。比如说 LegacyInputIterator 具有只读属性，而且单次遍历、单向移动。而继承 LegacyInputIterator 的 LegacyForwardIterator 有读写访问权限、而且支持多次遍历，std::forward_list 采用的就是 LegacyForwardIterator 的迭代器。
之后，我们还有支持双向移动的 LegacyBidirectionalIterator 迭代器，继承自 LegacyForwardIterator。 std::list 的迭代器就被归为 LegacyBidirectionalIterator。
继承自 LegacyBidirectionalIterator 的是 LegacyRandomAccessIterator 。提供随机访问属性，一般数组结构的数据结构往往都具备这种特性。std::array、std::vector 采用的就是这类迭代器。
C++ Iterator hierarchy 如下：
我们举个例子简单地说明一下迭代器的不同操作：
#include <list> // linked-list
#include <vector> // array
std::list<int> lst{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::list<int>::iterator lst_it = lst.begin();
lst_it++; // Increment (forward)
lst_it--; // Decrement
// int i = list_it[5]; // Random Access, not allowed in list
std::vector<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto vec_it = vec.begin();
vec_it++;
vec_it--;
auto i = vec_it[5]; // okay
在上面，我们介绍了几种不同的迭代器类型，还简单地说明了迭代器的不同操作。但是这些操作没有经过封装，不会进行边界检查，如果迭代器月结，行为就会是未定义的。为了更加安全地使用迭代器。这里我们介绍对迭代器的四个操作方法：advance, distance, next, prev。
std::advancestd::advance 的作用是将迭代器对象向前或向后移动 n 个位置，直接修改迭代器对象本身。其原型如下（Since C++17)：
template< class InputIt, class Distance >
constexpr void advance( InputIt& it, Distance n ); // No return value.
Distance 的正数表示向前移动，负数表示向后移动。标准容器库有许多不同的容器，有的容器只能向前移动，而有的容器可以双向移动。迭代器的类型不同，std::advance 的行为也随之改变。如：
#include <list>
#include <vector>
#include <iostream>
std::list<int> lst{1, 2, 3, 4, 5};
std::vector<int> vec{1, 2, 3, 4, 5};
auto lst_it = lst.begin();
auto vec_it = vec.begin();
std::advance(lst_it, 3);
std::cout << *lst_it << std::endl;
// std::advance(lst_it, -3); Not allowed, forward_list cannot move backwards
std::advance(vec_it, 3);
std::cout << *vec_it << std::endl;
std::advance(vec_it, -3);
std::cout << *vec_it << std::endl;
std::advance 的时间复杂度是 std::array 这类支持随机存取的数据结构，它的时间复杂度就是
std::distance这个函数的作用就是接收两个迭代器，然后返回这两个迭代器之间元素的个数。它的原型如下：
template< class InputIt >
constexpr
typename std::iterator_traits<InputIt>::difference_type
distance( InputIt first, InputIt last );
时间复杂度同上。
std::next接收当前的迭代器和一个整型数，返回从当前迭代器向前（forward）移动 n 步后的新迭代器（默认为 1 步）。这个操作不会修改当前迭代器。它的原型如下：
template< class InputIt >
constexpr
InputIt next( InputIt it, typename std::iterator_traits<InputIt>::difference_type n = 1 );
时间复杂度同上上。
std::prev接收当前的迭代器和一个整型数，返回从当前迭代器向后（backward）移动 n 步后的新迭代器（默认为 1 步）。这个操作不会修改当前迭代器。这个操作仅支持双向迭代器及以上类型。它的原型如下：
template< class BidirIt >
constexpr
BidirIt prev( BidirIt it, typename std::iterator_traits<BidirIt>::difference_type n = 1 );
时间复杂度同上上上。