有序表简单实现

wiki

我们不使用 nextindex 表，因为与非关联表存储键相比，遍历它需要更长的时间，而且存储键的表被放置在 __index 表中以实现快速查找。在简单的测试中，这种方法的基准测试结果比其他方法好，而且我们可以通过 <this>:del( key ) 删除项目。

--[[
   LUA 5.1 compatible
   
   Ordered Table
   keys added will be also be stored in a metatable to recall the insertion oder
   metakeys can be seen with for i,k in ( <this>:ipairs()  or ipairs( <this>._korder ) ) do
   ipairs( ) is a bit faster
   
   variable names inside __index shouldn't be added, if so you must delete these again to access the metavariable
   or change the metavariable names, except for the 'del' command. thats the reason why one cannot change its value
]]--
function newT( t )
   local mt = {}
   -- set methods
   mt.__index = {
      -- set key order table inside __index for faster lookup
      _korder = {},
      -- traversal of hidden values
      hidden = function() return pairs( mt.__index ) end,
      -- traversal of table ordered: returning index, key
      ipairs = function( self ) return ipairs( self._korder ) end,
      -- traversal of table
      pairs = function( self ) return pairs( self ) end,
      -- traversal of table ordered: returning key,value
      opairs = function( self )
         local i = 0
         local function iter( self )
            i = i + 1
            local k = self._korder[i]
            if k then
               return k,self[k]
            end
         end
         return iter,self
      end,
      -- to be able to delete entries we must write a delete function
      del = function( self,key )
         if self[key] then
            self[key] = nil
            for i,k in ipairs( self._korder ) do
               if k == key then
                  table.remove( self._korder, i )
                  return
               end
            end
         end
      end,
   }
   -- set new index handling
   mt.__newindex = function( self,k,v )
      if k ~= "del" and v then
         rawset( self,k,v )
         table.insert( self._korder, k )
      end      
   end
   return setmetatable( t or {},mt )
end
-- CHILLCODE�

t = newT()

t["a"] = "1"
t["ab"] = "2"
t["abc"] = "3"
t["abcd"] = "4"
t["abcde"] = "5"
t[1] = 6
t[2] = 7
t[3] = 8
t[4] = 9
t[5] = 10

print(">> t:pairs()")
for k,v in t:pairs() do
   print( k,v )
end
print(">> t:ipairs()")
for i,k in t:ipairs() do
   print( i,k,t[k] )
end
print(">> t:opairs()")
for i,v in t:opairs() do
   print( i,v )
end
print(">> t:del( 3 )")
t:del( 3 )
print(">> t:del( \"abc\" )")
t:del( "abc" )
print(">> t:opairs()")
for i,v in t:opairs() do
   print( i,v )
end
print(">> t.abc = 11")
t.abc = 11
print(">> t:opairs()")
for i,v in t:opairs() do
   print( i,v )
end
print(">> t.del = nil")
t.del = nil
print(">> t:del( 1 )")
t:del( 1 )
print(">> t:opairs()")
for i,v in t:opairs() do
   print( i,v )
end

>> t:pairs()
1       6
2       7
3       8
4       9
a       1
ab      2
abcd    4
abcde   5
5       10
abc     3
>> t:ipairs()
1       a       1
2       ab      2
3       abc     3
4       abcd    4
5       abcde   5
6       1       6
7       2       7
8       3       8
9       4       9
10      5       10
>> t:opairs()
a       1
ab      2
abc     3
abcd    4
abcde   5
1       6
2       7
3       8
4       9
5       10
>> t:del( 3 )
>> t:del( "abc" )
>> t:opairs()
a       1
ab      2
abcd    4
abcde   5
1       6
2       7
4       9
5       10
>> t.abc = 11
>> t:opairs()
a       1
ab      2
abcd    4
abcde   5
1       6
2       7
4       9
5       10
abc     11
>> t.del = nil
>> t:del( 1 )
>> t:opairs()
a       1
ab      2
abcd    4
abcde   5
2       7
4       9
5       10
abc     11

其他迭代，包括按键排序的迭代

• OrderedTable
• SortedIteration
• SortedIterationSimple