Ordered Table Simple

wiki

We don't use a nextindex table, since it takes to long to traverse compared to a inassociative table holding the keys, also the table holding the keys is placed insided the __index table for a fast lookup, in simple tests this method had a better benchmark compared to the other, plus we can delete items via <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

Other iterations, including iteration sorted by key

• OrderedTable
• SortedIteration
• SortedIterationSimple