lua - Safely remove items from an array table while iterating

Question

This question is similar to How can I safely iterate a lua table while keys are being removed but distinctly different.

Summary

Given a Lua array (table with keys that are sequential integers starting at 1), what's the best way to iterate through this array and delete some of the entries as they are seen?

Real World Example

I have an array of timestamped entries in a Lua array table. Entries are always added to the end of the array (using table.insert).

local timestampedEvents = {}
function addEvent( data )
  table.insert( timestampedEvents, {getCurrentTime(),data} )
end

I need to occasionally run through this table (in order) and process-and-remove certain entries:

function processEventsBefore( timestamp )
  for i,stamp in ipairs( timestampedEvents ) do
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    end
  end
end

Unfortunately, the code above approach breaks iteration, skipping over some entries. Is there any better (less typing, but still safe) way to do this than manually walking the indices:

function processEventsBefore( timestamp )
  local i = 1
  while i <= #timestampedEvents do -- warning: do not cache the table length
    local stamp = timestampedEvents[i]
    if stamp[1] <= timestamp then
      processEventData( stamp[2] )
      table.remove( timestampedEvents, i )
    else
      i = i + 1
    end
  end
end

Answer 1

the general case of iterating over an array and removing random items from the middle while continuing to iterate

If you're iterating front-to-back, when you remove element N, the next element in your iteration (N+1) gets shifted down into that position. If you increment your iteration variable (as ipairs does), you'll skip that element. There are two ways we can deal with this.

Using this sample data:

    input = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p' }
    remove = { f=true, g=true, j=true, n=true, o=true, p=true }

We can remove input elements during iteration by:

1. Iterating from back to front.

   for i=#input,1,-1 do
       if remove[input[i]] then
           table.remove(input, i)
       end
   end
   

2. Controlling the loop variable manually, so we can skip incrementing it when removing an element:

   local i=1
   while i <= #input do
       if remove[input[i]] then
           table.remove(input, i)
       else
           i = i + 1
       end
   end
   

For non-array tables, you iterate using next or pairs (which is implemented in terms of next) and set items you want removed to nil.

Note that table.remove shifts all following elements every time it's called, so performance is exponential for N removals. If you're removing a lot of elements, you should shift the items yourself as in LHF or Mitch's answer.