Lua 稀疏数组
Lua 的 table 可以做数组用，但是前提是数组里不能有空洞。也就是不能在数组里保存 nil ，否则取长度和迭代的行为都是不确定的。
能不能用比较小的额外代价在 Lua 中实现一个支持空洞的数组呢？
首先，我们定义一下，带空洞的 array 的正确行为应该是怎样的：
数组只能用正整数做 key ，设置其它 key 会抛出 error 。
可以用 pairs 迭代数组，和普通的 table 一样，迭代器会跳过那些值为 nil 的键值对。但要求迭代器一定从 1 开始从小到大按次序迭代。
用取长度 (#) 操作符，可以正确的返回数组的大小，即最大一个正整数 key 。
ipairs 的行为不变，会在第一个 nil 处停下来。
我想，可以依旧用 table 来充当数组，而只需要重定义这个数组对象的 __newindex __pairs 和 __len 三个元方法就可以了。
我们可以认为，在触发 __newindex 时，如果 key 在 lua_rawlen 返回的范围内，那么新的值还是保存在 table 的 array part 的，不用特别干预。
而如果在 hash part， 可以额外把这个 key 记录下来，我想以负数为下标就可以了。
每当 pairs 迭代前，或是取 # 长度前，我们可以对稀疏部分，哪些负数下标记录的额外 key 做一次排序去重整理。之后的运算复杂度就可以控制在 log(n) 内。
实现的代码见 github 上的仓库。
Comments
Posted by: lk | (4) September 13, 2016 04:01 PM
Posted by: dearbaba | (3) September 10, 2016 10:50 AM
Posted by: dearbaba | (2) September 10, 2016 08:33 AM
Posted by: 过河卒 | (1) September 1, 2016 03:10 PM