迭代器
作者：biggates
原文发表于： http://2ndvisual.com/2ndvisual/Xhtml/pro/ruby/6433.html 及
http://www.zaoxue.com/Article/readcourse/bianchengwendang/youxikaifa/ProgramminginLuafanyi--7.IteratorsandtheGenericfor.shtml
前言
迭代器是方法、get访问器或者运算符。它是用来干什么的呢？它的主要作用是使类或者结构，包括我们自己定义的数据集等中能够支持foreach遍历。只要我们在程序中提供一个迭代器，就可以遍历类中的数据结构。
正文
- 迭代器并不是Ruby发明的.它广泛地运用于各种面向对象语言.在Lisp中也有,只是不这么叫罢了.尽管如此,迭代器的概念并不为许多人熟悉,因此我们将在此做较为详细的介绍. 你知道,动词 iterate 的意思是做同一件事许多遍,因此,iterator就是用来将同一件事做许多次的东西. 当我们写代码时,我们需要各种环境下的循环.在C里,我们用for或者while.比如,
1 char *str;
2 for (str = "abcdefg"; *str != '\0'; str++)
3 {
4 /* process a character here */
5 }
- C的for(;;)语法提供了一种写循环的抽象方法,但测试 *str 是否为空(null)字符需要程序员了解字符串内部结构的细节.这让C看起来像低级(low-level)语言.更高级的语言是通过它们更具弹性的迭代器支持来实现的. 在一种语言能够很好的给内建的数据类型的提供迭代器的同时,我们却仍需要回去用低级别的循环语言来实现对自己定义的数据类型的迭代,这真是让人失望.在面对对象编程时,用户经常一个接一个地定义数据类型,因此这是一个很严重的问题. 因此,所有的OOP语言都包含了一定的迭代器机制.某些语言为此提供一种特殊的类。 采用迭代器,这将很轻松的取代C的大多数编程效果(找换行符,生成子串等等) 搞懂什么是迭代器了吗?有一些限制,但你可以写自己的迭代器;实际上,当你定义一个新的数据类型时,为它定义一个合适的迭代器经常也很方便.这样看来,上面的例子并不是很好用.在我们理解了类以后,我们可以讨论讨论更具实际意义的迭代器.
Programming in Lua 的第七章
迭代器与闭包
- 迭代器是一种支持指针类型的结构,它可以使遍历集合的每一个元素.在Lua中我们常常使用函数来描述迭代器,每次调用该函数就返回集合的下一个元素. 迭代器需要保留上一次成功调用的状态和下一次成功调用的状态,也就是他知道来自于哪里和将要前往哪里.闭包提供的机制可以很容易实现这个任务.记住:闭包是一个内部函数,它可以访问一个或者多个外部函数的外部局部变量.每次闭包的成功调用后这些外部局部变量都保存他们的值(状态).当然如果要创建一个闭包必须要创建其外部局部变量.所以一个典型的闭包的结构包含两个函数:一个是闭包自己;另一个是工厂(创建闭包的函数). 举一个简单的例子,我们为一个list写一个简单的迭代器,与ipairs()不同的是我们实现的这个迭代器返回元素的值而不是索引下标:
1 function list_iter (t)
2 local i = 0
3 local n = table.getn(t)
4 return function ()
5 i = i + 1
6 if i <= n then return t[i] end
7 end
8 end
- 这个例子中list_iter 是一个工厂,每次调用他都会创建一个新的闭包(迭代器本身).闭包包村内部局部变量(t,i,n),因此每次调用他返回list中的下一个元素值,当list中没有值时,返回nil.我们可以在while语句中使用这个迭代器:
1 t = {10, 20, 30}
2 iter = list_iter(t) -- creates the iterator
3 while true do
4 local element = iter() -- calls the iterator
5 if element == nil then break end
6 print(element)
7 end
- 我们设计的这个迭代器也很容易用于范性for语句
1 t = {10, 20, 30}
2 for element in list_iter(t) do
3 print(element)
4 end
- 范性for为迭代循环处理所有的薄记(bookkeeping):首先调用迭代工厂;内部保留迭代函数,因此我们不需要iter变量;然后在每一个新的迭代处调用迭代器函数;当迭代器返回nil时循环结束(后面我们将看到范性for能胜任更多的任务). 下面看一个稍微高级一点的例子:我们写一个迭代器遍历一个文件内的所有匹配的单词.为了实现目的,我们需要保留两个值:当前行和在当前行的偏移量,我们使用两个外部局部变量line,pos保存这两个值.
1 function allwords ()
2 local line = io.read() -- current line
3 local pos = 1 -- current position in the line
4 return function () -- iterator function
5 while line do -- repeat while there are lines
6 local s, e = string.find(line, "%w+", pos)
7 if s then -- found a word?
8 pos = e + 1 -- next position is after this word
9 return string.sub(line, s, e) -- return the word
10 else
11 line = io.read() -- word not found; try next line
12 pos = 1 -- restart from first position
13 end
14 end
15 return nil -- no more lines: end of traversal
16 end
17 end
- 迭代函数的主体部分调用了string.find函数,string.find在当前行从当前位置开始查找匹配的单词,例子中匹配的单词使用模式'%w+'描述的;如果查找到一个单词,迭代函数更新当前位置pos为单词后的第一个位置,并且返回这个单词(string.sub函数从line中提取两个位置参数之间的子串).否则迭代函数读取新的一行并重新搜索.如果没有line可读返回nil结束. 尽管迭代函数有些复杂,但使用起来是很直观的:
1 for word in allwords() do
2 print(word)
3 end
- 通常情况下,迭代函数都难写易用.这不是一个大问题:一般Lua编程不需要自己定义迭代函数,而是使用语言提供的,除非确实需要自己定义.
范性for的语义
- 前面我们看到的迭代器有一个缺点:每次调用都需要创建一个闭包,大多数情况下这种做法都没什么问题,例如在allwords迭代器中创建一个闭包的代价比起读整个文件来说微不足道,然后在有些情况下创建闭包的代价是不能忍受的.在这些情况下我们可以使用范性for本身来保存迭代的状态. 前面我们看到在循环过程中范性for在自己内部保存迭代函数,实际上它保存三个值:迭代函数,状态常量和控制变量.下面详细说明. 范性for的文法如下:
1 for <var-list> in <exp-list> do
2 <body>
3 end
<var-list>是一个或多个以逗号分割变量名的列表,<exp-list>是一个或多个以逗号分割的表达式列表,通常情况下exp-list只有一个值:迭代工厂的调用.
1 for k, v in pairs(t) do
2 print(k, v)
3 end
- 变量列表k,v;表达式列表pair(t),在很多情况下变量列表也只有一个变量,比如:
1 for line in io.lines() do
2 io.write(line, '\n')
3 end
- 我们称变量列表中第一个变量为控制变量,其值为nil时循环结束. 下面我们看看范性for的执行过程: 首先,初始化,计算in后面表达式的值,表达式应该返回范性for需要的三个值:迭代函数,状态常量和控制变量;与多值赋值一样,如果表达式返回的结果个数不足三个会自动用nil补足，多出部分会被忽略. 第二,将状态常量和控制变量作为参数调用迭代函数(注意:对于for结构来说,状态常量没有用处,仅仅在初始化时获取他的值并传递给迭代函数). 第三,将迭代函数返回的值赋给变量列表. 第四,如果返回的第一个值为nil循环结束,否则执行循环体. 第五,回到第二步再次调用迭代函数. 更精确的来说:
1 for var_1, ..., var_n in explist do block end
- 等价于
1 do
2 local _f, _s, _var = explist
3 while true do
4 local var_1, ... , var_n = _f(_s, _var)
5 _var = var_1
6 if _var == nil then break end
7 block
8 end
9 end
- 如果我们的迭代函数是f，状态常量是s,控制变量的初始值是a0,那么控制变量将循环:a1=f(s,a0);a2=f(s,a1);...直到ai=nil
无状态的迭代器
- 无状态的迭代器是指不保留任何状态的迭代器,因此在循环中我们可以利用无状态迭代器避免创建闭包花费额外的代价. 每一次迭代,迭代函数都是用两个变量(状态常量和控制变量)的值作为参数被调用,一个无状态的迭代器只利用这两个值可以获取下一个元素.这种无状态迭代器的典型的简单的例子是ipairs,他遍历数组的每一个元素.
1 a = {"one", "two", "three"}
2 for i, v in ipairs(a) do
3 print(i, v)
4 end
- 迭代的状态包括被遍历的表(循环过程中不会改变的状态常量)和当前的索引下标(控制变量),ipairs和迭代函数都很简单,我们在Lua中可以这样实现:
1 function iter (a, i)
2 i = i + 1
3 local v = a[i]
4 if v then
5 return i, v
6 end
7 end
8
9 function ipairs (a)
10 return iter, a, 0
11 end
- 当Lua调用ipairs(a)开始循环时,他获取三个值:迭代函数iter,状态常量a和控制变量初始值0;然后Lua调用iter(a,0)返回1,a[1](除非a[1]=nil);第二次迭代调用iter(a,1)返回2,a[2]...直到第一个非nil元素. Lua库中实现的pairs是一个用next实现的原始方法:
1 function pairs (t)
2 return next, t, nil
3 end
- 还可以不使用ipairs直接使用next
1 for k, v in next, t do
2 ...
3 end
- 记住:exp-list返回结果会被调整为三个,所以Lua获取next,t,nil;确切地说当他调用pairs时获取.
多状态的迭代器
- 很多情况下,迭代器需要保存多个状态信息而不是简单的状态常量和控制变量,最简单的方法是使用闭包,还有一种方法就是将所有的状态信息封装到table内,将table作为迭代器的状态常量,因为这种情况下可以将所有的信息存放在table内,所以迭代函数通常不需要第二个参数. 下面我们重写allwords迭代器,这一次我们不是使用闭包而是使用带有两个域(line,pos)的table. 开始迭代的函数是很简单的,他必须返回迭代函数和初始状态:
1 local iterator -- to be defined later
2
3 function allwords ()
4 local state = {line = io.read(), pos = 1}
5 return iterator, state
6 end
- 真正的处理工作是在迭代函数内完成:
1 function iterator (state)
2 while state.line do -- repeat while there are lines
3 -- search for next word
4 local s, e = string.find(state.line, "%w+", state.pos)
5 if s then -- found a word?
6 -- update next position (after this word)
7 state.pos = e + 1
8 return string.sub(state.line, s, e)
9 else -- word not found
10 state.line = io.read() -- try next line...
11 state.pos = 1 -- ... from first position
12 end
13 end
14 return nil -- no more lines: end loop
15 end
- 我们应该尽可能的写无状态的迭代器,因为这样循环的时候由for来保存状态,不需要创建对象花费的代价小;如果不能用无状态的迭代器实现,应尽可能使用闭包;尽可能不要使用table这种方式,因为创建闭包的代价要比创建table小,另外Lua处理闭包要比处理table速度快些.后面我们还将看到另一种使用协同来创建迭代器的方式,这种方式功能更强但更复杂.
真正的迭代器
- 迭代器的名字有一些误导,因为它并没有迭代,完成迭代功能的是for语句,也许更好的叫法应该是'生成器';但是在其他语言比如java,C++迭代器的说法已经很普遍了,我们也将沿用这种术语. 有一种方式创建一个在内部完成迭代的迭代器.这样当我们使用迭代器的时候就不需要使用循环了;我们仅仅使用每一次迭代需要处理的任务作为参数调用迭代器即可,具体地说,迭代器接受一个函数作为参数,并且这个函数在迭代器内部被调用. 作为一个具体的例子,我们使用上述方式重写allwords迭代器:
1 function allwords (f)
2 -- repeat for each line in the file
3 for l in io.lines() do
4 -- repeat for each word in the line
5 for w in string.gfind(l, "%w+") do
6 -- call the function
7 f(w)
8 end
9 end
10 end
- 如果我们想要打印出单词,只需要
1 allwords(print)
- 更一般的做法是我们使用匿名函数作为作为参数,下面的例子打印出单词'hello'出现的次数:
1 local count = 0
2 allwords(function (w)
3 if w == "hello" then count = count + 1 end
4 end)
5 print(count)
- 用for结构完成同样的任务:
1 local count = 0
2 for w in allwords() do
3 if w == "hello" then count = count + 1 end
4 end
5 print(count)
- 真正的迭代器风格的写法在Lua老版本中很流行,那时还没有for循环. 两种风格的写法相差不大,但也有区别:一方面,第二种风格更容易书写和理解;另一方面,for结构更灵活,可以使用break和continue语句 ;在真正的迭代器风格写法中return语句只是从匿名函数中返回而不是退出循环.