对于一个编程语言来说，定制各种需要的数据结构是一项重要的能力，如果定制的手段非常精简，将会获得极大的开发效率提升，而构建的手段针对当前计算机底层很贴合，则可以有机会获得非常高的性能。
对于定制数据结构来说，最基础的一项操作就是，遍历所有内容，因为有了遍历，基本上就有了“读”的功能。
大家都知道，不同的数据结构无论是外在形态还是内部结构都相差甚远，有什么办法能提供一个统一的接口对内部所有数据进行便利呢？这就是所谓“迭代器”。
以C++为例，遍历一个vector：
#include <iostream>
#include <vector>
int main(int argc, char *argv[])
{
std::vector<int> a = {1, 2, 3};
for (std::vector<int>::iterator iter = a.begin(); iter != a.end(); ++iter)
{
std::cout << *iter << std::endl;
}
return 0;
}
我们可以看到，它定义了一个新类型，叫std::vector<int>::iterator，这么个类型就是迭代器类型。从直觉上看他就是给访问数据提供个类似指针的接口而已，实际上这个迭代器变量还有另一个重要功能，就是“保存状态”，有了这个状态，才能知道下一次迭代能得到什么结果。
后来C++11标准出来后在语法方面进行了加强，淡化了保存状态这么个过程，写出的代码显得更加简洁：
#include <iostream>
#include <vector>
int main(int argc, char *argv[])
{
std::vector<int> a = {1, 2, 3};
for (auto iter : a)
{
std::cout << iter << std::endl;
}
return 0;
}
当然底层该有的操作是不会少的。
有了“保存状态”这个概念，实现编程语言的时候，就可以快速排除掉一些不靠谱的方案。
比如，不要迭代器而把状态保存在数据结构内部行不行？当然不行，考虑以下代码：
#include <iostream>
#include <vector>
int main(int argc, char *argv[])
{
std::vector<int> a = {1, 2, 3};
for (std::vector<int>::iterator iter = a.begin(); iter != a.end(); ++iter)
{
std::cout << *iter << ": ";
for (std::vector<int>::iterator iter2 = a.begin(); iter2 != a.end(); ++iter2)
{
std::cout << *iter2 << " ";
}
std::cout << std::endl;
}
return 0;
}
我们就知道，访问状态有时候是需要保存多份的，而对于引用类型的对象来说，状态要想在内部保存多份会更加复杂，还不如用显式的状态保存。
直接修改数据结构内部呢？比如用类似car和cdr循环赋值的方式进行遍历。这一样行不通，如果复制保存的引用类型真实数据，则代价太大，看不出引用类型的好处，而直接修改则会破坏数据本身，而数据可能之后还要使用。
以下Python作为例子如何创建一个可迭代的，Range对象：
class Range:
def __init__(self, low, high):
self.cur = low
self.high = high
def __iter__(self):
return self
def next(self):
if self.cur >= self.high:
raise StopIteration
else:
v = self.cur
self.cur += 1
return v
for item in Range(1, 3):
print item
创建对象的时候，执行了初始化方法和__iter__方法，在迭代的过程中则执行了和next方法，并且以StopIteration异常作为迭代结束的标志。
posted on 2014-10-11 17:10
呜呜 阅读(675)
评论(2) 编辑 收藏 引用