Re: adventures with iterators

[Dirk Laurie <dirk.laurie@...>]

2012/12/1 Sven Olsen <sven2718@gmail.com>:
> A few days ago, I had cause to write an iterator that traverses the
> keys of a table in sorted order.  It was done as a non-allocating C
> function, and while slower than pairs, I've realized that it gives me
> another tool for handling cases where a table may need to
> change inside a traversal.
...
> Each iterator call traverses the entire table, so walking through a
> table with spairs() is a O(n^2) operation. The upside is that it's
> non-allocating, and has sensible behavior in the case of table
> modifications.

You are already allowed to delete, only insertion is illegal.
Insertion when a key does not yet exist triggers __newindex.  So
there is a nearly non-allocating solution if you have are not yet
using __newindex ("nearly" means involving the new items only).
The solution below does not give access to the new items: you can
modify xpairs (exercise for the reader) to have that too if __index
is still available.

function xpairs(t)
-- iterate over existing pairs, allow insertion of new ones
--    but access to them only afterwards
   local mt=getmetatable(t)
   local newmt
   if not mt then
      newmt={}; setmetatable(t,newmt); mt=newmt; newmt=nil end
   if mt.__newindex then
      error("xpairs can't be used if __newindex is already used")
   end
   local cache={}
   mt.__newindex = function(tbl,idx,item)
      cache[idx]=item
   end
   local new
   return function()
      new=next(t,new)
      if new then return new else
         if newmt then setmetatable(t,nil) else mt.__newindex = nil end
         for k,v in pairs(cache) do t[k]=v end
      end
   end
end