Re: Holes

[Greg Falcon <veloso@...>]

On Thu, Dec 16, 2010 at 12:26 PM, Joshua Phillips
<jp.sittingduck@gmail.com> wrote:
> Perhaps a better idea to solve the '"holes" problem' is to store the
> largest number key with each table, so that table.maxn can be O(1),
> but adding new number keys would be a little slower.

That doesn't remove the cost, it just moves it elsewhere.  Under this scheme,
  table.maxn(t)
becomes O(1) but
  t[table.maxn(t)]=nil
becomes O(N), since you'd have to recalculate the cached value for maxn.

That might be useful in some cases (when deleting items is
infrequent), but in the general case, you wouldn't want to make table
element removal significantly slower to improve the much less
important table.maxn.

Greg F