[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: ipairs_remove - remove items from array while iterating it
- From: Philipp Janda <siffiejoe@...>
- Date: Sat, 02 Nov 2013 19:19:13 +0100
Am 02.11.2013 18:27 schröbte Thijs Schreijer:
Well noted! Also including the fix by Ashwin Hirchi (I love this list!)
local function ipairs_remove(tbl)
local i = 0
local shiftback = 0
local remove = function()
shiftback = shiftback + 1
i = i - 1
i = i + 1
if shiftback > 0 then
tbl[i] = tbl[i+shiftback]
if tbl[i] ~= nil then
return i, tbl[i], remove
for n = 1, shiftback-1 do
tbl[i+n] = nil
This contains some nasty side effects when not finishing the loop
(return, break, or goto). Only when the loop finishes the remaining
elements are cleared. So if you don't finish, they get duplicated.
If you modify the code to clear them while looping, then breaking the
loop results in a hole in the list (possibly even worse).
Maybe a for loop iterator is the wrong interface for this particular
problem. Maybe something like `table.foreachi_rm()`?
Or the "second loop" method in form of a `compact()` function ...
local n = #t
for i = 1, n do
if should_remove( t[ i ] ) then t[ i ] = nil end
compact( t, n ) -- or compact( t, 1, n )
So I think the remove() function should use table.remove() to clear the entry to prevent those sideeffects
That would make it O(n*m) again (m: elements to remove).
Having said that, I think the most elegant solution is backward traversal, as Pasi Mankinen already mentioned
... which is also O(n*m), although with less copy operations on average.