IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    Lua 稀疏数组

    云风的 BLOG发表于 2016-08-28 23:50:42
    love 0

    Lua 的 table 可以做数组用,但是前提是数组里不能有空洞。也就是不能在数组里保存 nil ,否则取长度和迭代的行为都是不确定的。

    能不能用比较小的额外代价在 Lua 中实现一个支持空洞的数组呢?

    首先,我们定义一下,带空洞的 array 的正确行为应该是怎样的:

    1. 数组只能用正整数做 key ,设置其它 key 会抛出 error 。

    2. 可以用 pairs 迭代数组,和普通的 table 一样,迭代器会跳过那些值为 nil 的键值对。但要求迭代器一定从 1 开始从小到大按次序迭代。

    3. 用取长度 (#) 操作符,可以正确的返回数组的大小,即最大一个正整数 key 。

    4. ipairs 的行为不变,会在第一个 nil 处停下来。


    我想,可以依旧用 table 来充当数组,而只需要重定义这个数组对象的 __newindex __pairs 和 __len 三个元方法就可以了。

    我们可以认为,在触发 __newindex 时,如果 key 在 lua_rawlen 返回的范围内,那么新的值还是保存在 table 的 array part 的,不用特别干预。

    而如果在 hash part, 可以额外把这个 key 记录下来,我想以负数为下标就可以了。

    每当 pairs 迭代前,或是取 # 长度前,我们可以对稀疏部分,哪些负数下标记录的额外 key 做一次排序去重整理。之后的运算复杂度就可以控制在 log(n) 内。

    实现的代码见 github 上的仓库。



沪ICP备19023445号-2号
友情链接