避免用作数组的表中的间隙

Created: November-22, 2018

定义我们的条款

通过阵列这里我们指的是作为一个序列的 Lua 表。例如：

-- Create a table to store the types of pets we like.
local pets = {"dogs", "cats", "birds"}

我们将此表用作序列：由整数键控的一组项。许多语言将此称为数组，我们也将如此。但严格地说，在 Lua 中没有阵列这样的东西。只有表，其中一些是类似数组的，其中一些类似哈希（或类似字典，如果你愿意），其中一些是混合的。

我们的 pets 阵列的一个重点是没有间隙。第一个项目 pets[1] 是字符串 dogs，第二个项目 pets[2] 是字符串 cats，最后一个项目 pets[3] 是 birds。Lua 的标准库和为 Lua 编写的大多数模块假设 1 是序列的第一个索引。因此，无间隙阵列具有来自 1..n 的项目，而不会丢失序列中的任何数字。（在极限情况下，n = 1，并且数组中只有一个项目。）

Lua 提供内置函数 ipairs 来迭代这些表。

-- Iterate over our pet types.
for idx, pet in ipairs(pets) do
  print("Item at position " .. idx .. " is " .. pet .. ".")
end

这将打印“位置 1 处的物品是狗”，“位置 2 处的物品是猫。”，“位置 3 处的物品是鸟类”。

但是如果我们做以下事情会发生什么？

local pets = {"dogs", "cats", "birds"}
pets[12] = "goldfish"
for idx, pet in ipairs(pets) do
  print("Item at position " .. idx .. " is " .. pet .. ".")
end

诸如该第二示例的阵列是稀疏阵列。序列中存在空白。这个数组看起来像这样：

{"dogs", "cats", "birds", nil, nil, nil, nil, nil, nil, nil, nil, "goldfish"}
-- 1        2       3      4    5    6    7    8    9    10   11       12

零值不会占用任何记忆; 内部 lua 只保存 [1] = "dogs"，[2] = "cats"，[3] = "birtds" 和 [12] = "goldfish" 的值

要回答当前的问题，ipairs 将在鸟类之后停止; 除非我们调整代码，否则永远不会到达 pets[12] 的金鱼。这是因为 ipairs 从 1..n-1 迭代，其中 n 是找到的第一个 nil 的位置。Lua 将 table[length-of-table + 1] 定义为 nil。因此，按照正确的顺序，当 Lua 试图得到三项数组中的第四项时，迭代停止。

什么时候？

稀疏数组出现问题的两个最常见的地方是（i）当试图确定数组的长度和（ii）尝试迭代数组时。特别是：

当使用 # 长度运算符时，长度运算符在找到的第一个 nil 处停止计数。
当使用 ipairs() 函数时，如上所述，它会在找到的第一个 nil 处停止迭代。
当使用 table.unpack() 函数时，因为此方法在找到的第一个 nil 处停止解包。
使用（直接或间接）访问上述任何功能的其他功能时。

为了避免这个问题，编写代码非常重要，这样如果你希望表是一个数组，则不会引入间隙。可以通过以下几种方式介绍差距：

如果在错误的位置向数组添加内容。
如果将 nil 值插入数组中。
如果从数组中删除值。

你可能会想，“但我绝不会做任何这些事情。” 好吧，不是故意的，但这是一个事情可能出错的具体例子。想象一下，你想为 Lua 编写一个过滤方法，比如 Ruby 的 select 和 Perl 的 grep。该方法将接受测试函数和数组。它迭代数组，依次调用每个项目的测试方法。如果项目通过，则该项目将添加到结果数组中，该数组在方法结束时返回。以下是一个错误的实现：

local filter = function (fun, t)
  local res = {}
  for idx, item in ipairs(t) do
    if fun(item) then
      res[idx] = item
    end
  end

  return res
end

问题是当函数返回 false 时，我们跳过序列中的数字。想象一下调用 filter(isodd, {1,2,3,4,5,6,7,8,9,10})：每次将数组中的偶数传递给 filter 时，返回表中都会有间隙。

这是一个固定的实现：

local filter = function (fun, t)
  local res = {}
  for _, item in ipairs(t) do
    if fun(item) then
      res[#res + 1] = item
    end
  end

  return res
end

提示

使用标准函数：table.insert(<table>, <value>) 始终附加到数组的末尾。table[#table + 1] = value 就此而言。table.remove(<table>, <index>) 将移回所有后续值以填补间隙（这也可能使其变慢）。
在插入之前检查 nil 值，避免像 table.pack(function_call()) 这样的东西，这可能会将 nil 值隐藏到我们的表中。
插入后检查 nil 值，必要时通过移动所有连续值填充间隙。
如果可能，请使用占位符值。例如，将 nil 更改为 0 或其他一些占位符值。
如果留下空白是不可避免的，应该妥善记录（评论）。
写一个 __len() 元方法并使用 # 运算符。

示例 6：

tab = {"john", "sansa", "daenerys", [10] = "the imp"}
print(#tab) --> prints 3
setmetatable(tab, {__len = function() return 10 end})
-- __len needs to be a function, otherwise it could just be 10
print(#tab) --> prints 10
for i=1, #tab do print(i, tab[i]) end
--> prints:
-- 1 john
-- 2 sansa
-- 3 daenerys
-- 4 nil
-- ...
-- 10 the imp

for key, value in ipairs(tab) do print(key, value) end
--> this only prints '1 john \n 2 sansa \n 3 daenerys'

另一种方法是使用 pairs() 函数并过滤掉非整数索引：

for key in pairs(tab) do
    if type(key) == "number" then
        print(key, tab[key]
    end
end
-- note: this does not remove float indices
-- does not iterate in order