1
wang2191195 2013-10-09 09:18:11 +08:00 via iPhone
参考nginx的数组策略或者c++ vector的策略
爪机无力 |
2
Golevka 2013-10-09 09:27:23 +08:00
同时具有O(1)的indexing, O(1)的pushback外加O(1)的removal, 同时还要保持original order ... 我感觉这玩意儿已经不是array就能解释的东西了.
|
3
bengol 2013-10-09 09:29:45 +08:00
"我想实现可生长的数组,没查到这方面的资料" STL vector的source code不是参考么?
|
4
wpp 2013-10-09 09:33:21 +08:00
@Golevka 如果不需要保持“original order ”的话,可以使用数组每个节点分配一个索引,然后把这个索引返回给申请分配者用来做remove,这样 “O(1)的indexing, O(1)的pushback外加O(1)的removal ”就都有了,
|
5
yetone 2013-10-09 09:38:34 +08:00
|
6
Golevka 2013-10-09 09:42:33 +08:00
@wpp 其实我的本意是remove a[i]时可以直接把a[-1]换到a[i]上. 另外我还好骑楼主的懒删除要不要在remove一个元素后把所有后续元素的index前移
|
7
yingluck 2013-10-09 09:59:11 +08:00
G++编译器貌似能识别动态数组
|
8
tioover OP @Golevka 惰性删除不是用在数组上的,是用在树上面的。
数组的惰性删除,我觉得必须有一个链表记录被删除的index… |
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也并不总是有效的) |
10
icenan2 2013-10-09 10:58:26 +08:00
看下cplusplus的STL实现,vector的增长好像确实是等比数列
|
11
luikore 2013-10-09 11:31:50 +08:00
|
13
stackpop 2013-10-09 13:30:48 +08:00
数组要实现随机访问,显然用链表是不行的。
vector是每次需要扩张都会double一下空间。 元素本身的存储地址是已经改变了,重新申请的新地址。 |
14
Precious 2013-10-09 16:43:02 +08:00
@Golevka +1
建议楼主 基本存储结构肯定是类似链表的东西 链表中的节点可以是数组..都可以 要保证查询速度,再做个索引。还需要注意索引创建和更新的代价 ...楼主研究顺利 成功了开源出来大家学习学习 |
15
tioover OP = =
本来想写的 结果发现…… B+Tree 孤陋寡闻了 |