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

[tioover]

我想实现可生长的数组，没查到这方面的资料，自己想了想，应该是用链表的形式将多个数组串联。这是不是最佳的解决方案？
但是不知道数组长度的增长应该用什么规律，等比数列？
还有，我打算实现惰性删除，但是不准备多一个专门用来标记是否删除的成员，于是想用原本的数据域设为一个特殊值的方法来删除，问题是这个特殊值怎么设置？NULL 指针明显不妥，我现在是让指针指向结构体本身。但是这样非常不直接。
所以除了NULL 不知道还有什么不会被用到的指针…

[wang2191195]

参考nginx的数组策略或者c++ vector的策略
爪机无力

[Golevka]

同时具有O(1)的indexing, O(1)的pushback外加O(1)的removal, 同时还要保持original order ... 我感觉这玩意儿已经不是array就能解释的东西了.

[bengol]

"我想实现可生长的数组，没查到这方面的资料" STL vector的source code不是参考么？

[wpp]

@Golevka 如果不需要保持“original order ”的话，可以使用数组每个节点分配一个索引，然后把这个索引返回给申请分配者用来做remove，这样 “O(1)的indexing, O(1)的pushback外加O(1)的removal ”就都有了，

[yetone]

http://tengine.taobao.org/book/chapter_02.html#ngx-array-t-100

[Golevka]

@wpp 其实我的本意是remove a[i]时可以直接把a[-1]换到a[i]上. 另外我还好骑楼主的懒删除要不要在remove一个元素后把所有后续元素的index前移

[yingluck]

G++编译器貌似能识别动态数组

[tioover]

@Golevka 惰性删除不是用在数组上的，是用在树上面的。
数组的惰性删除，我觉得必须有一个链表记录被删除的index…

[Golevka]

@tioover 你把这两件事写在一个主题里容易造成误♂解, 其实我感觉在数组里实现惰性删除带来的麻烦太多而收效甚微.

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

如果你的数据和treenode是绑在一起的, 如果不用额外的成员做标记的话就必须对payload的性质做一些假设, 例如[payload都是指针类型并且不会乱指]之类的, 否则你根本没办法找到一个永远都有效的nil (让payload指向treenode也并不总是有效的)

[icenan2]

看下cplusplus的STL实现，vector的增长好像确实是等比数列

[luikore]

http://en.wikipedia.org/wiki/Dynamic_array

楼主不如说说应用场景, 可能 gap buffer 会满足你的要求

[tioover]

@luikore 编程练习而已……

[stackpop]

数组要实现随机访问，显然用链表是不行的。

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

元素本身的存储地址是已经改变了，重新申请的新地址。

[Precious]

@Golevka +1
建议楼主 基本存储结构肯定是类似链表的东西 链表中的节点可以是数组..都可以
要保证查询速度，再做个索引。还需要注意索引创建和更新的代价
...楼主研究顺利 成功了开源出来大家学习学习

[tioover]

= =
本来想写的
结果发现……
B+Tree
孤陋寡闻了