有序表 简单实现

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

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

• 有序表
• 排序迭代
• 简单排序迭代