避免用作陣列的表中的間隙

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