Best way to iterate and remove

[nuno]

Hi everyone!

When I was learning love2d from a tutorial, the recommended way to iterate a list and remove objects was to add them to a temporary list "to remove". In the end of the iteration, we iterate the "to remove" list and remove them in the main list. This was a solution presented to avoid conflicts of removing objects while iterating, and I've been using it since then (iterating using ipairs). But is this the recommend way to do this?

I'm having some strange bugs, very rarely, were it seems 2 objects are being removed at the same time, I suspect the problem might be somewhere in this process.
How do you do it?

thanks

[micha]

There are two issues with removing multiple items from a list.
1) After each removal, the following items get resorted, to leave no gap in the list. So if you want to delete items 1 and 2 from a list, then after deleting no 1, the former no 2 becomes no 1. So a straight forward iteration would actually remove the first and the third items. To prevent that, you can simply iterate over the list backwards.

2) Each time, one element gets removed, all following items are sorted again. That takes time. So if you remove many items and know it in advance, then instead of going "remove, sort, remove, sort, remove, sort ..." you can save time by going "remove,remove,remove,..., sort" and only sort once in the end. This method is slightly faster, but takes a bit more effort in implementation. You can probably find a working implementation somewhere on the web.

I believe your issue is more related to the first points and unless you have really many items, I wouldn't bother about the second point.

[kikito]

To prevent that, you can simply iterate over the list backwards.

Micha means doing this:

Code: Select all

local function remove_items(tbl)
    for i=#tbl,1,-1 do -- i starts at the end, and goes "down"
      if should_be_removed(tbl[i]) then
        table.remove(tbl, i)
      end
   end      
end

[nuno]

Hi Micha, thanks for the reply!

Yes, I understood the issue in 1 was the reason the tutorial suggested to use a temporary list to hold the objects to remove. But I didnt understand, from your reply, if this solves it or not.

here's a small sample:

Code: Select all

 for k,v in ipairs(smoke) do
    if v.time >=v.life then
      table.insert(remSmoke,k)
    end
  end  
for k,v in ipairs(remSmoke) do
    table.remove(smoke,v)
  end

it uses the index to remove, so maybe the problem persists, right?

[nuno]

To prevent that, you can simply iterate over the list backwards.

Micha means doing this:

Code: Select all

local function remove_items(tbl)
    for i=#tbl,1,-1 do -- i starts at the end, and goes "down"
      if should_be_removed(tbl[i]) then
        table.remove(tbl, i)
      end
   end      
end

Hi Kikito,
Thanks, so I will replace my remove iterations with that!

[Robin]

Note that it generally is much faster to do this:

Code: Select all

local function remove_items(tbl, should_be_removed)
    for i=#should_be_removed,1,-1 do -- i starts at the end, and goes "down"
      table.remove(tbl, should_be_removed[i])
   end      
end

[kikito]

Note that it generally is much faster to do this: ...

That is true only if you already have the should_be_removed table. If you have to produce it from tbl and then remove the elements, then the version I proposed is faster (same number of ifs and deletions, but less additions and one less intermediate table).

[Robin]

Oh, yeah. I thought it was a table you where using, not a function. My mistake!

[vrld]

Not an answer to your question, but still good to know: If your table is not a list (i.e. does not have numeric indices), you can savely remove (but not add) items while iterating with pairs():

Code: Select all

for k,v in pairs(tbl) do
    if should_remove(v,k) then
        tbl[k] = nil
    end
end

[Lafolie]

Not an answer to your question, but still good to know: If your table is not a list (i.e. does not have numeric indices), you can savely remove (but not add) items while iterating with pairs():

Code: Select all

for k,v in pairs(tbl) do
    if should_remove(v,k) then
        tbl[k] = nil
    end
end

Could you explain this? I understand that pairs is stochastic in its iteration patterns, but how does this result in the safe removal of elements? Is the table buffered before the loop body begins execution?