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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4062 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

数组

指针

null

15 条回复 • 1970-01-01 08:00:00 +08:00

wang2191195

2013-10-09 09:18:11 +08:00 via iPhone

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

Golevka

2013-10-09 09:27:23 +08:00

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

bengol

2013-10-09 09:29:45 +08:00

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

wpp

2013-10-09 09:33:21 +08:00

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

yetone

2013-10-09 09:38:34 +08:00

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

Golevka

2013-10-09 09:42:33 +08:00

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

yingluck

2013-10-09 09:59:11 +08:00

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

tioover

2013-10-09 10:28:37 +08:00 via Android

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

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也并不总是有效的)