Re: pairs(t, skey) and ipairs(t, skey)

[Dirk Laurie <dirk.laurie@...>]

2013/10/6 Tim Hill <drtimhill@gmail.com>:
>
> I think there is some confusion of scope here. The implementation
> of the # function is (not surprisingly) O(1) but the entire set of logic
> to *realize* that behavior is O(n) since there is code for each
> __newindex() call. That was the point of my original post, since
> Roberto had raised concerns that my suggested design was O(n) ..
> though, like Dirk's design, it was O(n) for __newindex() calls, and
> was O(1) for the actual call to #.

My code is O(1) per __newindex call. Merely storing something in
a table is also O(1) per call, so O(1) per call is optimal.

There's a once-only startup pass over the whole table, which
amortizes to O(1) per table entry.

If you wish to track the largest index actually present in the table,
that would be O(n) per __newindex, unless you invest in maintaining
a priority queue.