表的深入应用

10.1 table 库详解

table.insert

local t = {1, 2, 3}

-- 在末尾插入
table.insert(t, 4)
-- t = {1, 2, 3, 4}

-- 在指定位置插入
table.insert(t, 2, "new")
-- t = {1, "new", 2, 3, 4}

table.remove

local t = {1, 2, 3, 4, 5}

-- 移除末尾元素
local last = table.remove(t)
print(last)               --> 5
-- t = {1, 2, 3, 4}

-- 移除指定位置元素
local third = table.remove(t, 3)
print(third)              --> 3
-- t = {1, 2, 4}

table.sort

local t = {3, 1, 4, 1, 5, 9, 2, 6}

-- 默认升序排序
table.sort(t)
-- t = {1, 1, 2, 3, 4, 5, 6, 9}

-- 自定义排序
table.sort(t, function(a, b)
  return a > b           -- 降序
end)

-- 复杂对象的排序
local people = {
  {name = "张三", age = 25},
  {name = "李四", age = 30},
  {name = "王五", age = 20},
}

table.sort(people, function(a, b)
  return a.age < b.age
end)

注意：Lua 的排序是不稳定的（相同值顺序不确定）。Lua 5.3 之后增加了稳定性保证。

table.concat

高效连接大量字符串的利器：

-- 字符串连接
local parts = {"a", "b", "c"}

-- 连接所有元素
local s = table.concat(parts)
print(s)                  --> abc

-- 指定分隔符
s = table.concat(parts, ", ")
print(s)                  --> a, b, c

-- 指定范围
s = table.concat(parts, "-", 2, 3)
print(s)                  --> b-c

-- 性能对比（永远用 concat 代替 .. 拼接）
local items = {}
for i = 1, 1000 do
  items[i] = tostring(i)
end

local result = table.concat(items, ",")
-- 如果不用 concat：
-- result = items[1]
-- for i = 2, 1000 do
--   result = result .. "," .. items[i]  -- 每次创建新字符串，极慢
-- end

table.move（Lua 5.3+）

local src = {1, 2, 3, 4, 5}
local dest = {10, 20, 30}

-- 从 src 的 2~4 复制到 dest 的 3~5
table.move(src, 2, 4, 3, dest)
-- dest = {10, 20, 1, 2, 3}

-- 在同一个表内移动
local t = {1, 2, 3, 4, 5}
table.move(t, 1, 3, 3, t)
-- t = {1, 2, 1, 2, 3}（后移）

---

10.2 表作为栈与队列

栈（LIFO）

local stack = {}

-- push
function stack:push(v)
  table.insert(self, v)
end

-- pop
function stack:pop()
  return table.remove(self)
end

-- peek
function stack:peek()
  return self[#self]
end

-- 使用
stack:push(1)
stack:push(2)
stack:push(3)

print(stack:pop())        --> 3
print(stack:peek())       --> 2

队列（FIFO）

local queue = {}

-- enqueue（入队）
function queue:enqueue(v)
  table.insert(self, v)
end

-- dequeue（出队）
function queue:dequeue()
  return table.remove(self, 1)  -- 移除第一个元素
end

-- 使用
queue:enqueue("first")
queue:enqueue("second")
queue:enqueue("third")

print(queue:dequeue())    --> first
print(queue:dequeue())    --> second

-- 注意：频繁 dequeue（移出第一个元素）性能差
-- 大量操作时考虑用两个栈模拟队列

双向队列

local deque = {}

-- 表头插入
function deque:push_front(v)
  table.insert(self, 1, v)
end

-- 表尾插入
function deque:push_back(v)
  table.insert(self, v)
end

-- 表头移除
function deque:pop_front()
  return table.remove(self, 1)
end

-- 表尾移除
function deque:pop_back()
  return table.remove(self)
end

---

10.3 多维表

二维数组（矩阵）

-- 创建 3×3 矩阵
local matrix = {}
for i = 1, 3 do
  matrix[i] = {}
  for j = 1, 3 do
    matrix[i][j] = i * j
  end
end

-- 访问
print(matrix[2][3])       --> 6

-- 按行遍历
for i = 1, #matrix do
  for j = 1, #matrix[i] do
    io.write(matrix[i][j] .. " ")
  end
  io.write("\n")
end
-- 输出：
-- 1 2 3
-- 2 4 6
-- 3 6 9

稀疏矩阵

-- 用嵌套表只存储非零值
local sparse = {}
sparse[1] = {[2] = 10}
sparse[3] = {[1] = 20, [4] = 30}

-- 访问时处理 nil
local function get_value(mat, i, j)
  local row = mat[i]
  if row then
    return row[j] or 0
  end
  return 0
end

print(get_value(sparse, 1, 2))    --> 10
print(get_value(sparse, 2, 1))    --> 0（不存在）

使用元表实现默认值

local function matrix_with_default(default)
  return setmetatable({}, {
    __index = function(_, key)
      return setmetatable({}, {
        __index = function(_, _)
          return default
        end
      })
    end
  })
end

local m = matrix_with_default(0)
print(m[1][2])            --> 0（无需检查 nil）
m[1][2] = 42
print(m[1][2])            --> 42

---

10.4 表作为集合

local Set = {}

function Set:new()
  return setmetatable({}, {__index = Set})
end

function Set:add(item)
  self[item] = true
end

function Set:remove(item)
  self[item] = nil
end

function Set:contains(item)
  return self[item] ~= nil
end

function Set:union(other)
  local result = Set:new()
  for k in pairs(self) do
    result:add(k)
  end
  for k in pairs(other) do
    result:add(k)
  end
  return result
end

function Set:intersection(other)
  local result = Set:new()
  for k in pairs(self) do
    if other:contains(k) then
      result:add(k)
    end
  end
  return result
end

-- 使用
local a = Set:new()
a:add("apple")
a:add("banana")

local b = Set:new()
b:add("banana")
b:add("cherry")

local c = a:union(b)
print(c:contains("apple"))  --> true
print(c:contains("cherry")) --> true

---

10.5 表的性能考虑

数组部分 vs 哈希部分

Lua 的表内部由数组部分和哈希部分组成：

-- 纯数组：只有数组部分
local arr = {1, 2, 3, 4, 5}

-- 纯字典：只有哈希部分
local dict = {a = 1, b = 2}

-- 混合：两部分都有
local mix = {1, 2, key = "value"}

批量插入优化

-- 方式一：直接赋值（较快）
local t = {}
for i = 1, 100000 do
  t[i] = i
end

-- 方式二：table.insert（稍慢但更安全）
local t = {}
for i = 1, 100000 do
  table.insert(t, i)
end

-- 方式三：预分配空间（Lua 5.2+ 可以这样）
local t = {}
for i = 1, 100000 do
  t[#t + 1] = i          -- 和直接赋值几乎一样快
end

避免高频 rehash

-- 如果知道最终大小，可预先填充 nil
local MAX_SIZE = 10000
local t = {}

-- 先给数组部分占位
for i = 1, MAX_SIZE do
  t[i] = nil             -- 不过度占位可能更好
end

-- 实际使用时再赋值
for i = 1, MAX_SIZE do
  t[i] = i * 2
end

---

10.6 表的复制与比较

浅拷贝

local function shallow_copy(t)
  local result = {}
  for k, v in pairs(t) do
    result[k] = v
  end
  return result
end

local original = {a = 1, nested = {b = 2}}
local copy = shallow_copy(original)
copy.a = 100
print(original.a)           --> 1（不受影响）
copy.nested.b = 200
print(original.nested.b)    --> 200（受影响！浅拷贝的局限）

深拷贝

local function deep_copy(t, seen)
  seen = seen or {}
  
  -- 非表类型直接返回
  if type(t) ~= "table" then
    return t
  end
  
  -- 防止循环引用
  if seen[t] then
    return seen[t]
  end
  
  local result = {}
  seen[t] = result
  
  for k, v in pairs(t) do
    result[deep_copy(k, seen)] = deep_copy(v, seen)
  end
  
  return result
end

-- 测试
local original = {
  a = 1,
  nested = {b = 2, c = {d = 3}}
}

-- 循环引用测试
original.self = original

local copy = deep_copy(original)
copy.nested.b = 999
print(original.nested.b)    --> 2（不受影响）
print(copy.self.nested.b)   --> 999（循环引用被正确处理）

表比较

local function table_equals(t1, t2, seen)
  seen = seen or {}
  
  if t1 == t2 then return true end
  if type(t1) ~= "table" or type(t2) ~= "table" then
    return false
  end
  
  if seen[t1] then return seen[t1] == t2 end
  seen[t1] = t2
  
  -- 比较 key 数量
  local count1, count2 = 0, 0
  for k in pairs(t1) do
    count1 = count1 + 1
    if t2[k] == nil and not table_equals(nil, t2[k]) then
      return false
    end
  end
  for k in pairs(t2) do
    count2 = count2 + 1
  end
  if count1 ~= count2 then return false end
  
  -- 比较每个元素
  for k, v in pairs(t1) do
    if not table_equals(v, t2[k], seen) then
      return false
    end
  end
  
  return true
end

local a = {1, 2, {3, 4}}
local b = {1, 2, {3, 4}}
local c = {1, 2, {3, 5}}

print(table_equals(a, b))  --> true
print(table_equals(a, c))  --> false

---

10.7 本章小结

函数	用途	示例
table.insert	插入元素	table.insert(t, pos, v)
table.remove	移除元素	table.remove(t, pos)
table.sort	排序	table.sort(t, comp)
table.concat	字符串拼接	table.concat(t, sep, i, j)
table.move	复制元素（5.3+）	table.move(src, a, b, c, dest)

练习题

1. 用 table 实现一个优先队列（支持 push 和 pop_min）
2. 写一个函数 flatten(t)，将嵌套的 table 展开为一维数组
3. 实现一个环形缓冲区（固定大小，超过后覆盖最旧数据）
4. 用 table.concat 生成 CSV 字符串
5. 实现一个 LRU 缓存（最近最少使用淘汰策略）