已排序表格

wiki

新版本

-- Ordered Table
-- Written by Rici Lake. The author disclaims all rights and responsibilities,
-- and relinquishes the software below to the public domain.
-- Have fun with it.
--
-- The function Ordered creates a table which can iterate in order of its
-- entries. You'll need to modify pairs as indicated on the Lua wiki
-- (GeneralizedPairsAndIpairs) in order to use this feature.
--
-- Since stock Lua does not have constructors, you cannot "seed" the
-- table with an initializer. A patch for this is forthcoming; this function
-- was extracted from the tests for that patch.
--
-- The table does not allow deletion, so it might not be appropriate
-- for all cases. You can set a key to nil, which removes it from
-- the iteration, but the key is actually permanently in the table,
-- and setting it to a new value will restore it to its original place
-- in the table. Obviously, that's not ideal, but it was simple and
-- efficient, and it is always possible to compact a table by copying it.
--
-- Rather than use what seems to be the classic implementation, with
-- three tables: <key->ordinal, ordinal->key, ordinal->value>, we
-- use a regular key->value table, with an auxiliary linked list
-- key->nextkey.
-- 
-- The advantage of this setup is that we don't need to invoke a
-- metamethod for any case other than setting a new key (or a key
-- which has been previously set to nil), which is a significant
-- speed-up. It also makes it easy to implement the stability
-- guarantee. The disadvantage is that there is effectively a
-- memory-leak.
--
-- The table is fully stable; during an iteration, you can perform
-- an arbitrary modification (since keys are not ever actually deleted).
 
local function Ordered()
  -- nextkey and firstkey are used as markers; nextkey[firstkey] is
  -- the first key in the table, and nextkey[nextkey] is the last key.
  -- nextkey[nextkey[nextkey]] should always be nil.
 
  local key2val, nextkey, firstkey = {}, {}, {}
  nextkey[nextkey] = firstkey
 
  local function onext(self, key)
    while key ~= nil do
      key = nextkey[key]
      local val = self[key]
      if val ~= nil then return key, val end
    end
  end
 
  -- To save on tables, we use firstkey for the (customised)
  -- metatable; this line is just for documentation
  local selfmeta = firstkey
 
  -- record the nextkey table, for routines lacking the closure
  selfmeta.__nextkey = nextkey
 
  -- setting a new key (might) require adding the key to the chain
  function selfmeta:__newindex(key, val)
    rawset(self, key, val)
    if nextkey[key] == nil then -- adding a new key
      nextkey[nextkey[nextkey]] = key
      nextkey[nextkey] = key
    end
  end
 
  -- if you don't have the __pairs patch, use this:
  -- local _p = pairs; function pairs(t, ...)
  --    return (getmetatable(t).__pairs or _p)(t, ...) end
  function selfmeta:__pairs() return onext, self, firstkey end
 
  return setmetatable(key2val, selfmeta)
end

使用例

There is no example yet

按照鍵的插入順序進行遍戀（舊版本）

舊版本需要鍵非數字型態，雖然它並未檢查這一點。它也不允許刪除。建構函式會採用表格引數，做為 orderedTable 的基礎。已建立表格的項目不會索引，表示無法使用提供的反覆運算器對它們進行遍戀。這通常很有用。範例僅顯示一個應用程式。

function orderedTable(t)
  local currentIndex = 1
  local metaTable = {}
    
  function metaTable:__newindex(key,value)
    rawset(self, key, value)
    rawset(self, currentIndex, key)
    currentIndex = currentIndex + 1
  end
  return setmetatable(t or {}, metaTable)
end

function ordered(t)
  local currentIndex = 0
  local function iter(t)
    currentIndex = currentIndex + 1
    local key = t[currentIndex]
    if key then return key, t[key] end
  end
  return iter, t
end

使用例

function show(t)
  print (t.__name .. ":")
  for k, v in ordered(t) do print(k, v) end
end

tab = orderedTable {__name = "table 1"}
tab.firstName = "Rici"
tab.lastName = "Lake"
tab.maternalLastName = "Papert"
show(tab)

鍵插入順序遍戀的其他實現

下列兩個版本皆允許刪除鍵，但如果在遍戀期間刪除鍵，則將會失敗。此外，它們使用 table.remove 刪除鍵和值，可能導致二次遞減。

• MakingLuaLikePhp（PHP 表格章節）
• Beginning Lua Programming，第 262 頁（請參閱 LuaBooks）。可在 [1]（請參閱第 08 章/orderedtbl.lua）的下載連結取得線上程式碼 (。），然而請注意，此程式碼需要更正（第 306 頁中註明）以讓 {__mode = "k"} 成為 RealTbls、NumToKeys 及 KeyToNums 表格的 metatable。

其他遍戀，包括根據鍵排序的遍戀

• OrderedAssociativeTable
• SortedIteration
• OrderedTableSimple