首页 > 代码库 > Chapter7 迭代器
Chapter7 迭代器
结合泛型for的所有功能，写出更加简单，高效的迭代器。
1、迭代器和closure
迭代器是一种可以遍历集合中所有元素的机制。在Lua中用函数去表示它。
每调用一次，就返回下一个元素。
迭代器在两次成功调用期间，都需要保持一些状态，这样才能知道它所在的位置及如何步进到下一个位置。
closure为此提供了一个很好的机制，一个closure就是一种可以访问upvalue的函数。
这些变量就可用于在成功调用之间保持状态值，从而使closure记住它在一次遍历中所在的位置。
因此，一个典型的closure结构包括两个函数：closure本身、创建该closure的工厂函数。
下面写一个迭代器函数，与ipairs不同的是它不返回每个元素的索引，仅返回元素的值：
function values(t) local i = 0 return function ()
i = i + 1
return t[i]
endend
该例中，values是一个工厂（闭合函数）。每次调用它就创建一个closure(迭代器本身)。
这个closure把它的状态保存在外部变量t和 i 中。每次调用这个迭代器，它就从 t 中返回下一个值。
直到最后一个元素，返回nil，迭代结束。
如果用while来实现：
t = {10,20,30}iter = values(t) --用工厂函数创建迭代器while true do local element = iter() --调用迭代器 if element == nil then break end print(element)end用while实现，可以清晰看到迭代器的工作流程，是不是 浅显易懂 ^_^。
如果用泛型for就更便捷了。你会发现，它就是为这种迭代而生设计的：
t = {10,20,30}for element in values (t) do print(element)end泛型for为一次迭代循环做了所有的薄记工作，它在内部保存了迭代器函数，因此不需要iter变量。
它在每次新迭代时调用迭代器，并在迭代器返回nil时结束循环。
一个更高级的迭代器：遍历当前输入文件中所有的单词-----allwords
for word in allwords() do print(word)end
为了完成这个功能，需要保持两个值：当前行的内容（line）和该行中所处的位置（pos）。
迭代器的主要部分是string.find函数，用"%w+"去匹配一个或多个数字/字符。
如果找到，迭代器就会更新当前pos为该单词之后的第一个字符，并返回该单词。
否则就读取新的一行反复这个搜索过程。若没有剩余的行，就返回nil，表示结束：
function allwords() local line = io.read() --初始化第一行 local pos = 1 --起始位置，初始化为1 return function() --迭代器函数 while line do --line为真，重复循环遍历 local s,e = string.find(line,"%w+",pos) if s then --找到了一个word pos = e + 1 --word后的下一个位置 return string.sub(line,s,e) --返回这个word else line = io.read() --开始找新的一行 pos = 1 --同时初始化pos为1 end end return nil --所有行都遍历完 endend
可以看到，编写迭代器不太容易，但是使用起来很方便。通常Lua用户不会自己定义迭代器。
后面会用有状态的closure重写allwords，把line和pos保存到一个table里，看上去就更加简洁了^_^。
2、迭泛型for语义
泛型for提供保存状态的机制可以简化上面的while循环（每次创建一个新的closure）。
泛型for在循环过程内部保存了迭代器函数。实际上它保存着3个值：一个迭代器函数，一个恒定状态，一个控制变量。
泛型for的语法：
for <var-list> in <exp-list> do <body>end
var-list是一系列由逗号分开的变量名。exp-list也是一系列由逗号分开的表达式。
通常，exp-list只有一个元素，即“调用工厂函数”。比如：
for k,v in pairs(t) do print(k,v) end--orfor line in io.lines() do io.write(line,"\n")end
var-list中的第一个变量叫作控制变量。在循环过程中，它的值不能为nil。为nil则循环终止。
for语句第一件做的事是计算exp的值————返回三个值（1 iterator ; 2 invariant state ; 3 initial value）供for语句使用。
第三个值用来初始化for的控制变量。这有点类似于多重赋值。
在初始化步奏后，for会以恒定状态和控制变量来调用迭代器函数。然后for将迭代器函数的返回值赋给变量列表中的变量。
一个更明朗的例子：
for var_1,..., var_n in <explist> do <block> end-- equal belowdo local _f,_s,_var = <explist> while true do local var_1, ... ,var_n = _f(_s, _var) --首先第一次调用恒定状态和控制变量 _var = var_1 if _var == nil then break end <block> endend
因此，如果迭代器函数为f，恒定状态为s，控制变量为a0。
在循环过程中控制变量依次为a1 = f（s，a0），a2 = f（s，a1）依此类推。直到ai为nil，循环结束。
3、无状态的迭代器
一种自身不保存任何状态的迭代器。
因此，可以在多个循环中使用同一个无状态的迭代器，避免创建新的closure开销。
在每次迭代中，for循环都会用恒定状态和控制变量去调用迭代器。
一个无状态的迭代器可以根据这两个值来为下一次迭代生成下一个元素。比如ipairs，迭代一个数组的所有元素：
a = {"one","two","three"}for i,v in ipairs(a) do print(i,v)endipairs工厂函数和迭代器可以用lua编写出来：
local function iter (a,i) i = i + 1 local v = a[i] if v then return i,v endendfunction ipairs(a) return iter,a,0end
函数pairs与ipairs类似，用于遍历一个table中的所有元素。不同的是，它的迭代器函数是Lua中的一个基本函数next。
function pairs(t) return next,t,nilend
在调用next(t,k)时，此调用会将table中的任意次序的一组值返回：此table的下一个key，和对应的值。
而调用next(t,nil)时返回table的第一组值。若没有下一组值时，next返回nil。
for k,v in next,t do <loop body>end
ext-list会调整为三个返回值，next，t和nil 。结果和pairs(t)一样。
无状态迭代器遍历链表（Lua中很少用，但有时会用到链表）：
local function getnext(list,node) if not node then return list --返回list头 else return node.next --返回下一个list endendfunction traverse(list) return getnext , list , nil --控制变量为nilend
这里将链表的头节点作为恒定状态(traverse返回的第二个值)，将当前节点作为控制变量。
getnext第一次被调用时，node为nil。之后调用则返回node.next.
list = nilfor line in io.lines() do list = {val = line, next = list }end --for循环结束后，list是包含最后一行的值，在链表里可以当成node head，下面的迭代器就用它开始遍历整个链表for node in traverse(list) do --这里的list是链表节点头，也是一个table print(node.val)end
这里的链表在遍历的时候，是从最后一行开始往前遍历。与c语言中的链表遍历刚好相反。
4、复杂状态的迭代器
通常，迭代器需要保存很多状态，可是泛型for却只提供一个恒定状态和一个控制变量的保存。
一个最简单的办法是用closure，或者可以将迭代器所需要的所有状态打包为一个table，保存在恒定状态中。
closre可以通过这个table保存任意多的数据，还可以在循环过程中改变这些数据。
由于这种迭代器可以在恒定状态中保存所有数据，所以它们通常可以忽略泛型for提供的第二个参数(控制变量)。
改写allwords例子,把line和pos保存到table里：
local iterator --在后面定义function allwords() local state = {line=io.read(),pos = 1} return iterator,state --这里省略了第三个返回值，控制变量，也就是泛型for为迭代器提供的第二个参数end
iterator函数：
function iterator(state) while state.line do -- 如果为有效的行内容才进入循环 local s,e = string.find(state.line,"%w+",state.pos) if s then --找到一个单词 state.pos = e + 1 return string.sub(state.line,s,e) else state.line = io.read() --读新的一行 state.pos = 1 --从第一个位置开始 end end return nil --所有行已经读完end
通常一个基于closure实现的迭代器会比一个使用table的迭代器更为高效。
因为创建一个closure比table廉价，并且访问“upvalue”比访问table字段更快。
以后还可以使用协同程序(coroutine)编写迭代器。功能最强，但是开销大。
5、真正的迭代器
其实真正做迭代的是for循环，迭代器只是为每次迭代提供一些成功后的返回值。
把迭代器称作“生成器(generator)”更准确。
有一种创建迭代器的方式：在迭代器中做实际的迭代操作。
当使用这种迭代器时，就不需要写一个循环了。但是，需要一个描述在每次迭代时需要做什么的参数，并用此参数来调用迭代器。
确切地说，迭代器接收一个函数作为参数，并在其内部的循环中调用这个函数。
接下来再重写allwords：
function allwords(f) for line in io.lines() do for word in string.gmatch(line,"%w+") do f(word) --调用函数 end endend
如果只想打印word：
allwords(print)还可以使用一个匿名函数作为循环体。
下面的代码计算了"hello"在文件中出现的次数：
local count = 0allwords(function (w) if w == "hello" then count = count + 1 end end) print (count)--如果用之前的迭代器，就是下面的风格local count = 0for w in allwords() do if w == "hello" then count = count + 1 endendprint(count)
生成器风格的迭代器更加灵活，它允许两个或多个并行（比如两个文件逐个单词对比）的迭代过程，允许在迭代中使用break和return。
对于真正的迭代器来说，return语句只能从匿名函数中返回，而不能从做迭代的函数中返回。
Chapter7 迭代器