V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
tioover
V2EX  ›  程序员

关于可生长的数组的实现还有一个C问题。

  •  
  •   tioover ·
    tioover · 2013-10-09 09:10:12 +08:00 via Android · 3777 次点击
    这是一个创建于 4048 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我想实现可生长的数组,没查到这方面的资料,自己想了想,应该是用链表的形式将多个数组串联。这是不是最佳的解决方案?
    但是不知道数组长度的增长应该用什么规律,等比数列?
    还有,我打算实现惰性删除,但是不准备多一个专门用来标记是否删除的成员,于是想用原本的数据域设为一个特殊值的方法来删除,问题是这个特殊值怎么设置?NULL 指针明显不妥,我现在是让指针指向结构体本身。但是这样非常不直接。
    所以除了NULL 不知道还有什么不会被用到的指针…
    15 条回复    1970-01-01 08:00:00 +08:00
    wang2191195
        1
    wang2191195  
       2013-10-09 09:18:11 +08:00 via iPhone
    参考nginx的数组策略或者c++ vector的策略
    爪机无力
    Golevka
        2
    Golevka  
       2013-10-09 09:27:23 +08:00
    同时具有O(1)的indexing, O(1)的pushback外加O(1)的removal, 同时还要保持original order ... 我感觉这玩意儿已经不是array就能解释的东西了.
    bengol
        3
    bengol  
       2013-10-09 09:29:45 +08:00
    "我想实现可生长的数组,没查到这方面的资料" STL vector的source code不是参考么?
    wpp
        4
    wpp  
       2013-10-09 09:33:21 +08:00
    @Golevka 如果不需要保持“original order ”的话,可以使用数组每个节点分配一个索引,然后把这个索引返回给申请分配者用来做remove,这样 “O(1)的indexing, O(1)的pushback外加O(1)的removal ”就都有了,
    yetone
        5
    yetone  
       2013-10-09 09:38:34 +08:00
    Golevka
        6
    Golevka  
       2013-10-09 09:42:33 +08:00
    @wpp 其实我的本意是remove a[i]时可以直接把a[-1]换到a[i]上. 另外我还好骑楼主的懒删除要不要在remove一个元素后把所有后续元素的index前移
    yingluck
        7
    yingluck  
       2013-10-09 09:59:11 +08:00
    G++编译器貌似能识别动态数组
    tioover
        8
    tioover  
    OP
       2013-10-09 10:28:37 +08:00 via Android
    @Golevka 惰性删除不是用在数组上的,是用在树上面的。
    数组的惰性删除,我觉得必须有一个链表记录被删除的index…
    Golevka
        9
    Golevka  
       2013-10-09 10:49:03 +08:00
    @tioover 你把这两件事写在一个主题里容易造成误♂解, 其实我感觉在数组里实现惰性删除带来的麻烦太多而收效甚微.

    至于树的懒删除, 如果你的数据域和treenode不绑在一起(例如{node *left, node *right, void *data}这种)那就好办了, 因为data是你自己控制的. 于是你可以用一个简单粗暴的办法例如 static void *_nil; 然后用&_nil作为空数据域... 好吧其实和用treenode作为_nil没什么两样

    如果你的数据和treenode是绑在一起的, 如果不用额外的成员做标记的话就必须对payload的性质做一些假设, 例如[payload都是指针类型并且不会乱指]之类的, 否则你根本没办法找到一个永远都有效的nil (让payload指向treenode也并不总是有效的)
    icenan2
        10
    icenan2  
       2013-10-09 10:58:26 +08:00
    看下cplusplus的STL实现,vector的增长好像确实是等比数列
    luikore
        11
    luikore  
       2013-10-09 11:31:50 +08:00
    http://en.wikipedia.org/wiki/Dynamic_array

    楼主不如说说应用场景, 可能 gap buffer 会满足你的要求
    tioover
        12
    tioover  
    OP
       2013-10-09 12:59:21 +08:00
    @luikore 编程练习而已……
    stackpop
        13
    stackpop  
       2013-10-09 13:30:48 +08:00
    数组要实现随机访问,显然用链表是不行的。

    vector是每次需要扩张都会double一下空间。

    元素本身的存储地址是已经改变了,重新申请的新地址。
    Precious
        14
    Precious  
       2013-10-09 16:43:02 +08:00
    @Golevka +1
    建议楼主 基本存储结构肯定是类似链表的东西 链表中的节点可以是数组..都可以
    要保证查询速度,再做个索引。还需要注意索引创建和更新的代价
    ...楼主研究顺利 成功了开源出来大家学习学习
    tioover
        15
    tioover  
    OP
       2013-11-22 13:02:05 +08:00
    = =
    本来想写的
    结果发现……
    B+Tree
    孤陋寡闻了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2691 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:38 · PVG 22:38 · LAX 06:38 · JFK 09:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.