现在的位置: 首页 > 综合 > 正文

在 vector , map , list 间取得平衡

2013年06月23日 ⁄ 综合 ⁄ 共 814字 ⁄ 字号 评论关闭
在 vector , map , list 间取得平衡

来自:[http://www.codingnow.com/2004/board/view.php?paster=776]

我想做一个数据结构,可以有序的存放数据,方便查找,而插入数据效率又不会太低。

当数据几乎不变 vector 是最好的解决方案。我们只需要把数据放进去,sort 之后,用 binary_search 就 ok 了。

如果经常插入数据,我们不得不考虑用 list ,这样可以达到最快的插入速度,但实在不利于检索。

map 是许多程序员的最爱,stl 的 map 多用 RB tree 来实现。有着快速的插入速度,同时具有媲美二分查找的查找速度。不过它需要记录很多额外的信息,三个指针和一个颜色值。而且,map 的插入效率还是另人担忧。

云风在这里提出一种数据结构仅供参考:

我希望用一种散开的数组来保存有序的数据,物理上线形的数据来保证其可以被二分查找,而一些离散的性质可以让插入操作不会去做大量的数据移动。我希望看到的数据在内存中保存的状态如下:

X....X........XX...X.............X

我们把 X 看作数据,“." 看作冗余信息。无论实际数据还是冗余数据都是等长的,线形分布在内存。我们可以用 vector 在实现。当然我们需要用 1bit 来区分数据的类型,这个 bit 不需要单独记录,大多数情况下都可以借用数据本身。例如,如果数据节点中有一个字是有效指针,我们可以用空指针来表明这个节点是一个冗余节点。

然后我们在冗余节点中放上偏移量来关联离散的节点:

X....X 变成 X 4 -2 -3 -4 X 中间的数字偏移量表示了离该节点最近的数据节点的位置。有了这些信息,我们就可以方便的做二分查找了。

至于插入节点,如果有冗余节点,我们可以替换掉它,如果没有则需要向前或向后移动,但移动量一般比密集的数组要小。

详细的算法不再给出,本文仅仅记录一下突然的灵感。

没有仔细考虑该算法,权当可行,先摘录下来,将来用时再做考虑!

抱歉!评论已关闭.