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
]]--
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 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

for k,v in t:hidden() do
   print( k,v )
end

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:spairs()")
for i,v in t:spairs() 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

Other iterations, including iteration sorted by key

• OrderedTable
• SortedIteration
• SortedIterationSimple