数据结构

队列和双向队列

虽然可以使用 Lua 的 table 库提供的 insert 和 remove 操作来实现队列，但这种方式
实现的队列针对大数据量时效率太低，有效的方式是使用两个索引下标，一个表示第一
个元素，另一个表示最后一个元素。

List = {first = 0, last = -1}function List:popleft ()
local first = self.first
if first > self.last then error("list is empty") end
local value = self[first]self[first] = nil -- to allow garbage collectionself.first = first + 1
return value
endfunction List:pushright(value)
local last = self.last + 1self.last = lastself[last] = value
endList:pushright(123)
print(List:popleft()) -->123

字符串缓冲

for line in io.lines() do
buff = buff … line … “\n”
end

为什么这样呢？Lua 使用真正的垃圾收集算法，但他发现程序使用太多的内存他就
会遍历他所有的数据结构去释放垃圾数据，一般情况下，这个算法有很好的性能（Lua
的快并非偶然的），但是上面那段代码 loop 使得算法的效率极其低下。
为了理解现象的本质，假定我们身在 loop 中间，buff 已经是一个 50KB 的字符串，
每一行的大小为 20bytes，当 Lua 执行 buff…line…"\n"时，她创建了一个新的字符串大小为
50,020 bytes，并且从 buff 中将 50KB 的字符串拷贝到新串中。也就是说，对于每一行，
都要移动 50KB 的内存，并且越来越多。读取 100 行的时候（仅仅 2KB），Lua 已经移动
了 5MB 的内存，
Lua的字符串和Java的字符串差不多，都是不可变的，不可变的意思是什么呢？
比如刚刚的result字符串，每一次进行连接操作之后，其实就产生了新的字符串，不再是原来的那个了。
于是，不断连接，就不断产生新的字符串，产生新字符串是需要复制操作，随着连接操作的不断进行着，字符串越来越大，复制操作也就越来越耗时。

local strs = {};
for i = 1, 30000, 1 do
strs[i] = "helloworld"
endlocal result = "";local startTime = os.clock();
for index, str in ipairs(strs) doresult = result .. str;
endlocal endTime = os.clock();
local useTime = endTime - startTime;print("消耗时间：" .. useTime .. "s");result = "";startTime = os.clock();
result = table.concat(strs);endTime = os.clock();
useTime = endTime - startTime;print("concat消耗时间：" .. useTime .. "s");--消耗时间：0.726s
--concat消耗时间：0.001s

元表与元方法

算数运算符元方法

__add重载+，相当于两个继承于同一个父类的子类，可以通过 s1+s2，调用父类的__add方法
local mt = {} --第一步：定义一个元表

    local mt = {} --第一步：定义一个元表 local MyTable = {}function MyTable.new(value) --第二步：创建表的时候同时指定对应的 metatable，这样一来， MyTable.new 创建的所有的集合都有相同的 metatable 了local t = {}setmetatable(t, mt)for k,v in ipairs(value) dot[k] = vendreturn tendfunction MyTable.add(a, b)local t = {}for k,v in ipairs(a) dot[k] = a[k] + b[k]endreturn tend--第三步，给 metatable 增加__add 函数，指定函数的行为在子表中实现或者创建一个函数实现，相当于运算符重载mt.__add = MyTable.add --除此之外还有__sub(减法), __mul(乘法), __div(除法), __unm(相反数), __mod(取余), __pow(乘幂)等算术方法mt.__sub = function(a, b) --也可以这么写local t = {}for k,v in ipairs(a) dot[k] = a[k] - b[k]endreturn tendlocal test1 = MyTable.new({1, 2})local test2 = MyTable.new({3, 4})local testAdd = test1 + test2local testSub = test1 - test2--第三步，给 metatable 增加__add 函数，指定函数的行为在子表中实现或者创建一个函数实现，相当于运算符重载mt.__add = MyTable.add --除此之外还有__sub(减法), __mul(乘法), __div(除法), __unm(相反数), __mod(取余), __pow(乘幂)等算术方法mt.__sub = function(a, b) --也可以这么写local t = {}for k,v in ipairs(a) dot[k] = a[k] - b[k]endreturn tendlocal test1 = MyTable.new({1, 2})local test2 = MyTable.new({3, 4})local testAdd = test1 + test2local testSub = test1 - test2

对于每一个算术运算符，metatable 都有对应的域名与其对应，除了__add、__mul
外，还有__sub(减)、__div(除)、__unm(负)、__pow(幂)，我们也可以定义__concat 定义
连接行为

库定义元方法

print(table)输出所有成员

tostring 是一个典型的例子。如前面我们所见，tostring 以简单的格式表示出 table：
print({})
–> table: 0x8062ac0
（注意：print 函数总是调用 tostring 来格式化它的输出）。然而当格式化一个对象的
时候，tostring 会首先检查对象是否存在一个带有__tostring 域的 metatable。如果存在则
以对象作为参数调用对应的函数来完成格式化，返回的结果即为 tostring 的结果

local mt = {} --定义一个元表local MyTable = {}function MyTable.new(value)local t = {}setmetatable(t, mt)for k,v in ipairs(value) dot[k] = vendreturn tendfunction MyTable.add(a, b)local t = {}for k,v in ipairs(a) dot[k] = a[k] + b[k]endreturn tend--[[function MyTable.tostring(set)local s = "{"local sep = ""for e in pairs(set) dos = s .. sep .. esep = ", "endreturn s .. "}"end
--]]function MyTable.tostring(set)local s = "{"s = table.concat(set,",")return"{" .. s .. "}"endmt.__add = MyTable.add --除此之外还有__sub(减法), __mul(乘法), __div(除法), __unm(相反数), __mod(取余), __pow(乘幂)等算术方法mt.__sub = function(a, b) --也可以这么写local t = {}for k,v in ipairs(a) dot[k] = a[k] - b[k]endreturn tendmt.__tostring = MyTable.tostringlocal test1 = MyTable.new({1, 2})local test2 = MyTable.new({3, 4})local testAdd = test1 + test2local testSub = test1 - test2print(test1)-->{1,2}

表相关元方法

__index

当我们访问一个表的不存在的域，返回结果为 nil，这是正确的，但并不
一定正确。实际上，这种访问触发 lua 解释器去查找__index metamethod：如果不存在，
返回结果为 nil；如果存在则由__index metamethod 返回结果。相当于面向对象的继承

mytable = setmetatable({key1 = "value1"}, {__index = function(mytable, key)if key == "key2" thenreturn "metatablevalue"elsereturn nilendend
})print(mytable.key1,mytable.key2)--》value1    metatablevalue

实例解析：
● mytable 表赋值为 {key1 = “value1”}。
● mytable 设置了元表，元方法为 __index。
● 在mytable表中查找 key1，如果找到，返回该元素，找不到则继续。
● 在mytable表中查找 key2，如果找到，返回 metatablevalue，找不到则继续。
● 判断元表有没有__index方法，如果__index方法是一个函数，则调用该函数。
● 元方法中查看是否传入 “key2” 键的参数（mytable.key2已设置），如果传入 “key2” 参数返回 “metatablevalue”，否则返回 mytable 对应的键值。
我们可以将以上代码简单写成：
mytable = setmetatable({key1 = “value1”}, { __index = { key2 = “metatablevalue” } })
print(mytable.key1,mytable.key2)

总结
Lua 查找一个表元素时的规则，其实就是如下 3 个步骤:
● 1.在表中查找，如果找到，返回该元素，找不到则继续
● 2.判断该表是否有元表，如果没有元表，返回 nil，有元表则继续。
● 3.判断元表有没有 __index 方法，如果 __index 方法为 nil，则返回 nil；如果 __index 方法是一个表，则重复 1、2、3；如果 __index 方法是一个函数，则返回该函数的返回值。
当__index指向的函数
__index = function(mytable, key)
第一个参数为表，第二个参数为key
当__index可以指向一个表本身

__newindex

__newindex metamethod 用来对表更新，__index 则用来对表访问。当你给表的一个
缺少的域赋值，解释器就会查找__newindex metamethod：如果存在则调用这个函数而不
进行赋值操作。像__index 一样，如果 metamethod 是一个表，解释器对指定的那个表，
而不是原始的表进行赋值操作。另外，有一个 raw 函数可以绕过 metamethod：调用
rawset(t,k,v)不掉用任何 metamethod 对表 t 的 k 域赋值为 v。__index 和__newindex
metamethods 的混合使用提供了强大的结构：从只读表到面向对象编程的带有继承默认
值的表。
以下实例演示了 __newindex 元方法的应用：
__newindex如果在元表中定义了，那么setmetatable后的原始表，缺少的索引赋值，其实是给元表中__newindex所指向的东西赋值赋值，不会改变原始表

mymetatable = {}
mytable = setmetatable({key1 = "value1"}, { __newindex = mymetatable })print(mytable.key1)mytable.newkey = "新值2"
print(mytable.newkey,mymetatable.newkey)mytable.key1 = "新值1"
print(mytable.key1,mymetatable.key1)

以上实例执行输出结果为：
value1
nil 新值2
新值1 nil

相当于给父类赋值，而不会改变子类的域

有默认值的表

local key = {} -- unique key
local mt = {__index = function (t) return t[key] end}
function setDefault (t, d)t[key] = dsetmetatable(t, mt)
endtab = {x=10, y=20}
print(tab.x, tab.z) --> 10 nil
setDefault(tab, 0)
print(tab.x, tab.q) --> 10 0

lua table名作为key值，可以保证key的唯一性

监控表

lua原始表：子类 元表：父类

t = {} 
-- original table (created somewhere)  
-- keep a private access to original table  
local _t = t  
-- create proxy  
t = {}  
-- create metatable  
local mt = {  __index = function (t,k)  print("*access to element " .. tostring(k))  
return _t[k] -- access the original table  
end,  __newindex = function (t,k,v)  print("*update of element " .. tostring(k) ..  " to " .. tostring(v))  _t[k] = v 
-- update original table  
end  
}  
setmetatable(t, mt) > t[2] = 'hello'  
*update of element 2 to hello  
> print(t[2])  
*access to element 2  
hello 

只读表

function readOnly (t)
local proxy = {}
local mt = { -- create metatable__index = t,__newindex = function (t,k,v)error("attempt to update a read-only table", 2)end}setmetatable(proxy, mt)
return proxy
enddays = readOnly{"Sunday", "Monday", "Tuesday", "Wednesday","Thursday", "Friday", "Saturday"}
print(days[1]) --> Sunday
days[2] = "Noday"

环境

动态名字访问全局变量

_G是一张表，保存了lua所用的所有全局函数和全局变量

function setfield (f, v)
local t = _G -- start with the table of globals
for w, d in string.gfind(f, "([%w_]+)(.?)") doif d == "." then -- not last field?t[w] = t[w] or {} -- create table if absentt = t[w] -- get the tableelse -- last fieldt[w] = v -- do the assignmentend
end
endfunction getfield (f)
local v = _G -- start with the table of globals
for w in string.gfind(f, "[%w_]+") dov = v[w]
end
return v
endsetfield("t.x.y", 10)
print(t.x.y) --> 10
print(getfield("t.x.y")) --> 10

声明全局变量

如何安全的赋值，访问全局变量
因为 Lua 所有的全局变量都保存在一个普通的表中，我们可以使用 metatables 来改变访
问全局变量的行为

local declaredNames = {}
function declare (name, initval)rawset(_G, name, initval)declaredNames[name] = true
end
setmetatable(_G, {__newindex = function (t, n, v)
if not declaredNames[n] thenerror("attempt to write to undeclared var. "..n, 2)
elserawset(t, n, v) -- do the actual set
end
end,__index = function (_, n)
if not declaredNames[n] thenerror("attempt to read undeclared var. "..n, 2)
elsereturn nil
end
end,
})declare ("a",1)print(a)

raw：原始的，未加工的。
rawset/rawget：对“原始的”表进行直接的赋值/取值操作。
所以，raw方法就是忽略table对应的metatable，绕过metatable的行为约束，强制对原始表进行一次原始的操作，也就是一次不考虑元表的简单更新

Packages

基本方法

complex = {}  
function complex.new (r, i) return {r=r, i=i} end 
-- defines a constant `i'  
complex.i = complex.new(0, 1)  
function complex.add (c1, c2)  
return complex.new(c1.r + c2.r, c1.i + c2.i)  
end  
function complex.sub (c1, c2)  
return complex.new(c1.r - c2.r, c1.i - c2.i)  
end 
return complex 

私有成员

方法1

local P = {}  
complex = P  
local function checkComplex (c)  
if not ((type(c) == "table") and tonumber(c.r) and tonumber(c.i)) then error("bad complex number", 3)  
end  
end  
function P.add (c1, c2)  checkComplex(c1);  checkComplex(c2);  
return P.new(c1.r + c2.r, c1.i + c2.i)  
end  
...  
return P 

方法二：返回时作为域

local function checkComplex (c)  
if not ((type(c) == "table")  
and tonumber(c.r) and tonumber(c.i)) then error("bad complex number", 3)  
end 
end  
local function new (r, i) return {r=r, i=i} end 
local function add (c1, c2)  checkComplex(c1);  checkComplex(c2);  
return new(c1.r + c2.r, c1.i + c2.i)  
end  
...  
complex = {  new = new,  add = add,  sub = sub,  mul = mul,  div = div,  
} 

其他技巧

local location = {  foo = "/usr/local/lua/lib/pack1_1.lua",  goo = "/usr/local/lua/lib/pack1_1.lua",  foo1 = "/usr/local/lua/lib/pack1_2.lua",  goo1 = "/usr/local/lua/lib/pack1_3.lua",  
} pack1 = {} setmetatable(pack1, {__index = function (t, funcname)  
local file = location[funcname]  
if not file then error("package pack1 does not define " .. funcname)  
end  
assert(loadfile(file))() 
-- load and run definition  
return t[funcname] 
-- return the function  
end})  
return pack1 

加载这个 package 之后，第一次程序执行 pack1.foo()将触发__index metamethod，接
着发现函数有一个相应的文件，并加载这个文件。微妙之处在于：加载了文件，同时返
回函数作为访问的结果

面向对象程序设计

类

定义方法的时候带上一个额外的参数，来表示方法作用的对象。
这个参数经常为 self 或者 this：

function Account.withdraw (self, v)  self.balance = self.balance - v  
end  a1 = Account; Account = nil 
...  
a1.withdraw(a1, 100.00) 
-- OK 

Lua 也提供了通
过使用冒号操作符来隐藏这个参数的声明。我们可以重写上面的代码

function Account:withdraw (v)  self.balance = self.balance - v  
end 
a:withdraw(100.00) Account = {  balance=0,  withdraw = function (self, v)  self.balance = self.balance - v  
end  
}  
function Account:deposit (v)  self.balance = self.balance + v  
end  
Account.deposit(Account, 200.00)  
Account:withdraw(100.00) 

Lua 中，使用前面章节我们介绍过的继承的思想，很容易实现 prototypes.更明确
的来说，如果我们有两个对象 a 和 b，我们想让 b 作为 a 的 prototype 只需要：
setmetatable(a, {__index = b})

这样，对象 a 调用任何不存在的成员都会到对象 b 中查找。术语上，可以将 b 看作
类，a 看作对象。回到前面银行账号的例子上。为了使得新创建的对象拥有和 Account
相似的行为，我们使用__index metamethod，使新的对象继承 Account。注意一个小的优
化：我们不需要创建一个额外的表作为 account 对象的 metatable；我们可以用 Account
表本身作为 metatable：

面向对象new

function Account:new (o)  o = o or {} 
-- create object if user does not provide one  setmetatable(o, self)  self.__index = self  
return o  
end a = Account:new{balance = 0}  
a:deposit(100.00) 

（当我们调用 Account:new 时，self 等于 Account；因此我们可以直接使用 Account
取代 self。然而，使用 self 在我们下一节介绍类继承时更合适）。有了这段代码之后，当
我们创建一个新的账号并且掉用一个方法的时候，有什么发生呢？
当我们创建这个新的账号 a 的时候，a 将 Account 作为他的 metatable（调用
Account:new 时，self 即 Account）。当我们调用 a:deposit(100.00)，我们实际上调用的是
a.deposit(a,100.00)（冒号仅仅是语法上的便利）。然而，Lua 在表 a 中找不到 deposit，因
此他回到 metatable 的__index 对应的表中查找，情况大致如下：
getmetatable(a).__index.deposit(a, 100.00)

a的metatable是Account，Account.__index也是Account（因为new函数中self.__index
= self）。所以我们可以重写上面的代码为：
Account.deposit(a, 100.00)

setmetatable(o, {__index = c})，设置父类的表一定要有__index,否则返回nil

继承

找不到的去父类，找到的执行子类方法

多重继承

实现的关键在于：将函数用作__index。记住，当一个表的 metatable 存在一个__index
函数时，如果 Lua 调用一个原始表中不存在的函数，Lua 将调用这个__index 指定的函数。
这样可以用__index 实现在多个父类中查找子类不存在的域。
多重继承意味着一个类拥有多个父类，所以，我们不能用创建一个类的方法去创建
子类。取而代之的是，我们定义一个特殊的函数 createClass 来完成这个功能，将被创建
的新类的父类作为这个函数的参数。这个函数创建一个表来表示新类，并且将它的
metatable 设定为一个可以实现多继承的__index metamethod。尽管是多重继承，每一个
实例依然属于一个在其中能找得到它需要的方法的单独的类。所以，这种类和父类之间
的关系与传统的类与实例的关系是有区别的。特别是，一个类不能同时是其实例的
metatable 又是自己的 metatable。在下面的实现中，我们将一个类作为他的实例的
metatable，创建另一个表作为类的 metatable：

local function search (k, plist)
for i=1, table.getn(plist) dolocal v = plist[i][k] -- try 'i'-th superclassif v then return v end
end
endfunction createClass (...)
local c = {} -- new class
-- class will search for each method in the list of its
-- parents (`arg' is the list of parents)setmetatable(c,{__index = function (t, k)
return search(k, arg)
end})-- define a new constructor for this new class
function c:new (o)o = o or {}setmetatable(o, {__index = c})
return o
end
-- return new class
return c
end--创建一个account类
Account = { }function Account:deposit (v)self.balance = self.balance + v
end
function Account:withdraw (v)self.balance = self.balance - v
end--创建一个类Named，Named 只有两个方法 setname and getname?
Named = {}
function Named:getname ()
return self.name
end
function Named:setname (n)self.name = n
end--创建一个类,继承Account, Named
NamedAccount = createClass(Account, Named)--创建一个Account类的对象
account = NamedAccount:new{name = "Paul",balance = 5} --一定要类创建对象时定义好name，balance，基类未调用不会定义
print(account:getname()) --> Paulaccount:deposit(5)
print(account.balance) -->10

Lua 在 account 中找不到 getname，因此他
查找 account 的 metatable 的__index，即 NamedAccount。但是，NamedAccount 也没有
getname，因此 Lua 查找 NamedAccount 的 metatable 的__index，因为这个域包含一个函
数，Lua 调用这个函数并首先到 Account 中查找 getname，没有找到，然后到 Named 中
查找，找到并返回最终的结果。当然，由于搜索的复杂性，多重继承的效率比起单继承
要低。一个简单的改善性能的方法是将继承方法拷贝到子类。使用这种技术，index 方法
如下：

setmetatable(c, {__index = function (t, k)  
local v = search(k, arg)  t[k] = v 
-- save for next access  
return v  
end}) 

相当于__index 函数返回时，找到了，保存在子类中，下次查找，不会再往父类中查找
私有
__index可以指定一个新table，这个table只有父类的域的一部分

单一方法

function newObject (value)  
return function (action, v)  if action == "get" then return value  elseif action == "set" then value = v  else error("invalid action")  end  
end  
end d = newObject(0)  
print(d("get")) 
--> 0  
d("set", 10)  
print(d("get")) 
--> 10