对于一个编程语言来说,定制各种需要的数据结构是一项重要的能力,如果定制的手段非常精简,将会获得极大的开发效率提升,而构建的手段针对当前计算机底层很贴合,则可以有机会获得非常高的性能。
对于定制数据结构来说,最基础的一项操作就是,遍历所有内容,因为有了遍历,基本上就有了“读”的功能。
大家都知道,不同的数据结构无论是外在形态还是内部结构都相差甚远,有什么办法能提供一个统一的接口对内部所有数据进行便利呢?这就是所谓“迭代器”。
以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
呜呜 阅读(664)
评论(2) 编辑 收藏 引用