Re: adventures with iterators
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: adventures with iterators
- From: Dirk Laurie <dirk.laurie@...>
- Date: Sat, 1 Dec 2012 06:55:28 +0200
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