Oh -- that is clever. Complicated to code up though, and, as you say, trades away memory for algorithmic efficiency. You'll need to tweak my code if you want it to work neatly across a range of basic types. Replace the lua_compare calls with something that switches on the type in the register. It's still potentially a pretty simple C function though.
In the name of completeness, I feel I should admit that for all the time I spent gossiping on the list about different iterators, the sorted table iteration I'm actually using is a relatively simple wrapper around table.sort(key(t)). It's more or less just a brute force solution, with a little extra effort added in to make it deletion safe.
--
-- returns an iterator that traverses the given table's current
-- keys in sorted order.
--
-- example use: for k,v in rpairs(t) do
--
-- the behavior is very similar to spairs, which iterates over
-- all of a table's keys in sorted order.
--
-- the difference is in how key insertions are handled. rpairs
-- will never iterate over keys that didn't exist at the start
-- of the loop, while spairs will iterate over such keys if
-- they're larger than the key that inserted them.
--
-- rpairs is faster than spairs -- O(n log n), rather than
-- O(n^2). spairs is more memory efficient, it triggers no
-- allocations, while rpairs requires O(n) temporary memory.
-- my hunch is that rpairs is often going to be a wiser choice
-- than spairs, though perhaps not always.
--
function rpairs(t,sortfun)
local keys=keys(t)
table.sort(keys,sortfun)
local k2i={}
for i,k in ipairs(keys) do
k2i[k]=i
end
local function iterate(state,k)
local i= (k==nil and 1) or 1 + k2i[k]
local k= keys[i]
if k==nil then
return
end
-- don't iterate over keys with nil values
if v==nil then
return iterate(state,k)
end
return k,t[k]
end
return iterate
end
