c++11——范围 for 的那些事

众所周知在 c++11 中支持了同 python3 一样的范围 for 语句。即 for (int x : vector)。

该语法结合 c++11 中方便的 auto 不定类型名使用体验极佳。

但是这样仅适用于系统提供的容器，包括但不限于 STL、数组等。如：

vector <int> v;
for (auto x : v) { /* do something */ }
set <int> s;
for (auto x : s) { /* do something */ }
int a[1005];
for (auto x : a) { /* do something */ }

在一些时候如果我们想要如此方便的遍历自己的结构体就不适用了。

这里给出一种可以实现这个效果的方法。

首先我们要知道 for (:) 在程序内部到底是怎么实现的。抛开数组不谈，对于一些可遍历的 STL，我们自己在遍历的时候是用迭代器从 begin() 到 end() 遍历。其实在程序内部，这种范围 for 有一种实现也是这样，即 for (auto x = v.begin(); x != v.end(); ++x)。当然具体如何实现不管，我们只需要知道，对于我们自己定义的结构体，如果能自定义一个迭代器，且该结构体有 begin()、end() 函数供迭代器遍历，那么就可以实现这个过程。

实际上迭代器用指针模拟就可以了。但是因为指针的 ++ 和 * 已经被定义，不适合当做这里的迭代器。但是我们可以用一个结构体来存储指针并模拟。即

template <typename T> struct Iterator {
  T *iter;
  Iterator (T *p) { iter = p; }
  T& operator *() { return *iter; }
  bool operator != (const Iterator& that) { return this->iter != that.iter; }
  Iterator& operator++() { iter = iter->next; return *this; }
};

为了能够适用更多情况，这里的模拟迭代器适用 template 模板。在其中定义了一个指针来储存数据，重载的取值的 *，自加 ++ 和不等于，即与上文暴力实现的需求相对应。这里有两个注意项，++ 的函数中的语句 iter = iter->next，这需要适用这个迭代器的结构体有 next 指针；* 的返回值必须为传引用，不然的话就不能通过这个来修改了。

考虑怎么使用它。下面给出一个边表的实现：

struct Edges {
  int to; Edges *next;
  Edges () { to = 0, next = nullptr; }
  Iterator<Edges> begin() { return Iterator<Edges>(this); };
  Iterator<Edges> end() { return Iterator<Edges>(nullptr); }
} e[];

其中 to 是边表要存的信息，这里不管。next 是连接下一个元素的指针，这里和迭代器中的 next 相对应。在该结构体中我们还需要定义两个函数 begin() 和 end()，这样才能遍历这个结构体。

不难发现最后 Edges 会连出一个链表。用范围 for 遍历的时候，我们传入的是开始遍历的位置。具体的，即 for (auto x : e[k])，这意味着它会从 e[k] 开始遍历，到链尾才会结束。

至此我们就可以实现用范围 for 遍历自定义的结构体了。

❀ ~撒花~ ❀

但事实上在算法竞赛中它的用途极少，因为似乎除了边表就没有什么东西需要遍历一个结构体了。但是或许可以写一些算法竞赛之外的东西，~~用来装 X~~。