Stable Array
by Xibalba Studios
View and activate on the Corona Store
This is a data structure much like a stock Lua array, except that removing objects doesn’t entail moving other objects, neither by shifting them down nor backfilling the liberated slot. Doing this naively in Lua would lead to holes, of course, such that the # operator becomes a crapshoot, to say nothing of ipairs() no longer iterating all elements, in general.
The no-holes point might be enough justification for some people. My own chief use cases have been reciprocal parent-child or sibling relationships in data structures. In Lua 5.1, cycles (which aren’t terribly hard to introduce) can make such constructions invisible to the garbage collector. When the appropriate “links” are simply fixed positions in an array, on the other hand, no cycles need occur. (At times a weak table will suffice, of course.)
(The trick is that vacated elements are commandeered to maintain a FIFO queue of free slots, to that adding a new item is O(1) while keeping the array compact; since these slots are obviously not nil, no holes. Explicit storage / retrieval of nil and NaN values basically comes for free under this design, and thus is supported. Storing number elements requires some indirection and extra space, unfortunately, to disambiguate them from the slot indices.)