目標(biāo)：利用泛型for寫出高效迭代器
迭代器是一種支持指針類型的結(jié)構(gòu)，可以便利集合中的每個元素蒙谓。在Lua中常使用函數(shù)來描述迭代器斥季，每次調(diào)用會返回集合中的下一個元素。
迭代器需要保留上一次成功調(diào)用的狀態(tài)和下一次成功調(diào)用的狀態(tài)彼乌，也就是說必須知道它來自哪里和將要前往哪里泻肯。閉包提供的機制可以很容易實現(xiàn)這個任務(wù)。
閉包是一個內(nèi)部函數(shù)慰照，閉包可以訪問一個或多個外部函數(shù)的外部局部變量灶挟。每次閉包的成功調(diào)用后，這些外部局部變量都保存他們的值（狀態(tài)）毒租。如果要創(chuàng)建一個閉包必須要創(chuàng)建其外部局部變量稚铣，所以典型的閉包的結(jié)構(gòu)包含兩個函數(shù)：閉包自身、創(chuàng)建閉包的工廠函數(shù)墅垮。
迭代器（Iterator）是一種可以遍歷集合中所有元素的機制惕医。在Lua中，迭代器表示為函數(shù)算色，每調(diào)用一次函數(shù)即返回集合中下一個元素抬伺。每個迭代器都需要在每次成功調(diào)用之間保持一些狀態(tài)，這樣才能知道當(dāng)前所在位置以及如何步進(jìn)到下一個位置灾梦，閉包（closure）對此類任務(wù)提供了極佳的支持峡钓。
閉包
理解閉包之前妓笙，必須理清Lua中的函數(shù)：
- Lua中函數(shù)是“第一類值”，意味著Lua中的函數(shù)與基本數(shù)據(jù)類型的值（數(shù)值能岩、字符串寞宫、布爾值）具有相同的權(quán)力。
- 函數(shù)具有特定的詞法域拉鹃，即一個函數(shù)可以嵌套在另一個函數(shù)中辈赋，內(nèi)部函數(shù)可以訪問外部函數(shù)中的局部變量。
- 函數(shù)可以存儲到變量（全局變量或局部變量）或
table中膏燕，也可以作為實參傳遞給其他函數(shù)钥屈，還可以作為其他函數(shù)的返回值。
閉包（closure）是一種可以訪問其外部嵌套環(huán)境中的局部變量的函數(shù)煌寇。對于閉包而言焕蹄，函數(shù)中的局部變量可用于在成功調(diào)用之間保持狀態(tài)值，從而使閉包可以記住遍歷時所處的環(huán)境和位置阀溶。為了創(chuàng)建閉包必須創(chuàng)建它的"非局部變量（non-local variable腻脏，upvalue）"，因此閉包結(jié)構(gòu)通常涉及兩個函數(shù)：閉包本身银锻、用于創(chuàng)建閉包的工廠函數(shù)永品。
示例：迭代器之返回元素的值
-- 迭代器：返回元素的值
function values(tbl)
local i = 0
return function()
i = i + 1
return tbl[i]
end
end
-- test
local tbl = {1, 2, 3, 4, 5}
-- 創(chuàng)建迭代器
local iterator = values(tbl)
while true do
-- 調(diào)用迭代器
local ele = iterator()
if ele==nil then
break
end
print(ele)
end
解析：values本身是一個工廠，每當(dāng)調(diào)用工廠時會創(chuàng)建新的閉包即迭代器本身击纬，閉包函數(shù)將其狀態(tài)保存在外部變量tbl和i中鼎姐。每當(dāng)調(diào)用迭代器時會從列表tbl中返回下一個值，直到最后一個元素返回后更振，迭代器返回nil表示結(jié)束炕桨。
Lua通過閉包（closure）來處理內(nèi)部函數(shù)訪問“非局部變量（upvalue）”，一個閉包其實就是一個函數(shù)加上該函數(shù)所需訪問的所有“非局部變量（upvalue）”肯腕。
示例：遞歸之斐波拉契數(shù)列
-- 根據(jù)索引獲取對應(yīng)位置中斐波那契數(shù)列的值
function fibonacci(index)
if index>0 and index<=2 then
return 1
else
return fibonacci(index-1) + fibonacci(index-2)
end
end
-- 打印連續(xù)10個斐波那契數(shù)列數(shù)值
local i = 1
while i<=10 do
print(i, fibonacci(i))
i = i + 1
end
示例：遞歸階乘
local fact
fact = function(n)
if n==0 then
return 1
else
-- 調(diào)用fact時献宫，fact必須先定義，而非此函數(shù)自身实撒。
return n*fact(n-1)
end
end
-- TEST
print(fact(4)) -- 24
-- 簡化形式
local function fact(n)
if n==0 then
return 1
else
return n*fact(n-1)
end
end
-- TEST
print(fact(4)) -- 24
示例：創(chuàng)建遍歷當(dāng)前文件中所有單詞的迭代器
為了遍歷當(dāng)前文件中所有單詞姊途，需要保存兩個值：當(dāng)前行的內(nèi)容、當(dāng)前行所處的位置知态。有了這些信息就可以不斷地產(chǎn)生下一個單詞捷兰。
-- 迭代器
function iterator()
-- 獲取當(dāng)前行
local line = io.read()
-- 當(dāng)前位置
local pos = 1
-- 迭代器函數(shù)
return function()
-- 遍歷有效行
while line do
-- 獲取單詞起止下標(biāo)
local begin_index, end_index = string.find(line, "%w+", pos)
if begin_index then
pos = end_index + 1
-- 返回單詞
return string.sub(line, begin_index, end_index)
else
-- 進(jìn)入下一行
line = io.read()
pos = 1
end
end
return nil
end
end
-- 遍歷
for item in iterator() do
print(item)
end
$ lua
> dofile("test.lua")
this is a demo
this
is
a
demo
使用閉包實現(xiàn)時存在一個缺點，就是他需要為每個新的循環(huán)都創(chuàng)建一個新的閉包负敏。對于大多數(shù)情況而言贡茅，這也許并不會有什么問題。
泛型for
泛型for正是為迭代而設(shè)計的其做，泛型for為一次迭代循環(huán)做了所有的記錄友扰，其內(nèi)部保存了迭代器函數(shù)彤叉，因此無需iterator變量。并且在每次新迭代時調(diào)用迭代器村怪，并在迭代器返回nil時結(jié)束循環(huán)。
-- 迭代器：返回元素的值
function values(tbl)
local i = 0
return function()
i = i + 1
return tbl[i]
end
end
-- test
local tbl = {1, 2, 3, 4, 5}
-- 泛型for
for ele in values(tbl) do
print(ele)
end
泛型for在循環(huán)遍歷過程中浮庐，其內(nèi)部保存了迭代器函數(shù)甚负，而實際上是保存著3個值：迭代器函數(shù)、恒定狀態(tài)审残、控制變量梭域。
--[[
var-list 是一個或多個變量名的列表，以逗號分隔
exp-list 是一個或多個表達(dá)式的列表搅轿，以逗號分隔病涨。
通常表達(dá)式列表只有一個元素，即對迭代器函數(shù)的調(diào)用璧坟。
--]]
for <var-list> in <exp-list> do
<body>
end
-- eg
for k,v in pairs(tbl) do
print(k,v)
end
for i,v in ipairs(arr) do
print(i, v)
end
--[[
值得注意的是既穆，pairs()和ipairs()并非是迭代器，而只是一個表達(dá)式雀鹃。
表達(dá)式用于產(chǎn)生3個參數(shù)幻工，真正的迭代器是表達(dá)式內(nèi)部返回的用于查詢下一個元素的函數(shù)。
--]]
for做的第一件事情就是對in后面的表達(dá)式求值黎茎，這些表達(dá)式應(yīng)該返回3個值供for保存：迭代器函數(shù)囊颅、恒定狀態(tài)、控制變量的初值傅瞻。這里和多重賦值一樣踢代，只有最后一個表達(dá)式才會產(chǎn)生多個結(jié)果，并且只會保留前3個值嗅骄，多余的值會被丟棄胳挎，如果不夠的話，則以nil補足掸读。
- 在初始化完成后串远，
for會以恒定狀態(tài)和控制變量來調(diào)用迭代器函數(shù)。 - 然后
for將迭代器函數(shù)的返回值賦予變量列表中的變量儿惫，如果第一個返回值為nil那么循環(huán)就終止澡罚。否則，for執(zhí)行其循環(huán)體肾请。 - 隨后再次調(diào)用迭代器函數(shù)留搔，并重復(fù)這個過程。
泛型for中的pairs和ipairs有什么異同點呢铛铁？
-
ipairs用于迭代數(shù)組且不能返回nil隔显，若遇到nil則退出却妨。 -
pairs用于迭代表，可遍歷表的鍵名括眠，且可以返回nil彪标。
無狀態(tài)迭代器
無狀態(tài)迭代器是指自身不保存任何狀態(tài)的迭代器，可在多個循環(huán)中使用同一個無狀態(tài)迭代器掷豺，避免創(chuàng)建的新的閉包的開銷捞烟。
在每次迭代中for循環(huán)都會用恒定狀態(tài)和控制變量來調(diào)用迭代器函數(shù)，一個無狀態(tài)的迭代器可根據(jù)這兩個值來為下次迭代生成下一個元素当船。此類迭代器典型的例子就是ipairs题画，它可以用來迭代一個數(shù)組中所有的元素。
for i,v in ipairs(arr) do
print(i,v)
end
這里迭代狀態(tài)就是需要遍歷的table（恒定狀態(tài)德频，不會在循環(huán)中改變）以及當(dāng)前索引值（控制變量）苍息。ipairs用于創(chuàng)建迭代器的工廠函數(shù)和迭代器都很簡單。
-- 迭代器
local function iterator(array, index)
index = index + 1
local value = array[index]
if value then
return index, value
end
end
-- 創(chuàng)建迭代器的工廠函數(shù)
function ivpair(array)
return iterator, array, 0
end
-- 泛型for
local arr = {10, 20, 30}
for i,v in ivpair(arr) do
print(i,v)
end
- 當(dāng)Lua調(diào)用
for循環(huán)的ipair時會獲得3個值：迭代器函數(shù)iterator壹置、恒定狀態(tài)arr竞思、控制變量index的初始值0。 - 然后Lua調(diào)用迭代器
iterator(arr, 0)得到1,arr[1]蒸绩。 - 類此類推衙四，繼續(xù)調(diào)用迭代器，直到第一個
nil元素為止患亿。
函數(shù)pairs也是用于遍歷一個table中的所有元素传蹈，不同之處在于，pairs的迭代器函數(shù)是一個基礎(chǔ)函數(shù)next步藕。
-- 創(chuàng)建迭代器的工廠函數(shù)
function kvpair(tbl)
-- 迭代器為next
return next, tbl, nil
end
-- 泛型for
local tbl = {nickname="alice", gender=1}
for k,v in kvpair(tbl) do
print(k,v)
end
Lua在調(diào)用next(table, key)時惦界，key是table種的一個key，next調(diào)用會以table中的任意次序返回一組值：此table的下一個key以及這個key所對應(yīng)的值咙冗。而調(diào)用next(table, nil)時沾歪，返回table的第一組值。若沒有下一組值時雾消，next會返回nil灾搏。
可以不通過pairs調(diào)用而直接使用next
local tbl = {nickname = "alice", gender = 1}
for k,v in next,tbl do
print(k,v)
end
for循環(huán)
Lua中的for循環(huán)分為2種數(shù)值型、泛型立润，其中泛型又分為有狀態(tài)和無狀態(tài)狂窑。
數(shù)值型for
需要注意的是在數(shù)值型for中的初始值、步長桑腮、終止值的計算僅僅在最開始第一次循環(huán)就保存起來了泉哈，也就是說在數(shù)值for循環(huán)中即使對控制變量做了修改也不會影響循環(huán)的過程，這一點和C語言的循環(huán)是不同的。
local arr = {10, 20, 30}
for i,v in ipairs(arr) do
arr = nil -- for循環(huán)中的起始值丛晦、步長奕纫、終止值的計算只在最開始計算一次就保存起來了
print(i,v)
end
-- 循環(huán)變量i和v是for循環(huán)的局部變量，跳出for循環(huán)后局部變量就會被銷毀烫沙。
print(i,v) -- nil nil
泛型for
泛型循環(huán)有3個重要參數(shù)：迭代器匹层、初始狀態(tài)、初始狀態(tài)輸入斧吐，這種for循環(huán)如同一個有限狀態(tài)機又固，只要給定狀態(tài)轉(zhuǎn)移函數(shù)、初始狀態(tài)煤率、初始狀態(tài)輸入就可以自動運行下去，不停的產(chǎn)生出下一個狀態(tài)乏冀。那么循環(huán)怎么還有一個狀態(tài)呢蝶糯？這個狀態(tài)到底是個什么東西呢？
循環(huán)的目的是為了遍歷辆沦，而遍歷的目的卻是為了尋找下一個值昼捍。
在C語言中for循環(huán)遍歷線性結(jié)構(gòu)的對象
for(int i=0; i<size; i++){
//...
}
但是對于非線性結(jié)構(gòu)，要遍歷就沒有那么簡單肢扯，是不可以直接使用++來查詢下一個元素的妒茬。
而在C++中的如STL的一些容器和Lua中的table，遍歷時都會使用到迭代器（Iterator）蔚晨，雖然形式不同乍钻，但本質(zhì)上無論C++的迭代器、Lua的迭代函數(shù)或是樹铭腕、圖的遍歷算法银择，都是一個有限狀態(tài)機，為的是查找下一個元素累舷。
