我需要维护一个项目列表(一些对象),并支持以下操作:
-
结尾插入
-
从任何位置删除
STL列表似乎是正确的选择 . 但是,如何在恒定时间内完成第二次操作?我可以保存指向每个节点的指针并直接删除它们,但擦除需要一个迭代器,这样就无法工作了 .
用法示例:
items = list<myobj>..
items.push_back(obj1)
items.push_back(obj2)
items.push_back(obj3)
items.remove(obj2) // <- How to do this in constant time.
如果push_back以某种方式访问节点,我可以使用:
map[obj1] = items.push_back(obj1)
items.remove(map[obj1])
一种选择是在 Map 中使用迭代器,有没有更简单的方法?
2 回答
折衷方案是像大多数std :: set实现一样的红黑树 . 它是插入,搜索和删除的O(log n) . 树木基本上是最终的折衷数据结构 . 他们对任何事情都不是很了不起,但他们总能把工作做得很好 .
否则,使用链接列表和向量来分析代码,并找出调整向量的大小是否真的很糟糕(这取决于你执行它的频率) .
可能有一个更好(不优雅,但非常有效)的解决方案,可能只是照顾你的问题 . 您没有消耗该列表,但是如果您可以将值保留为未使用,则可以使用向量并将元素标记为已删除而不是实际删除它 . 或者使用向量并使用单独的位集(或C 03
vector<bool>
)告诉您项目是否已删除或有效 . 要删除它,您只需要翻转位图中的位 . 迭代时,只需记住在处理内容之前检查删除位图 . 如果内存不是问题且速度很重要且容易/清晰度很重要,请将vector<object>
替换为vector<pair<bool, object>>
,其中bool
是删除标志 .你可能想看看Boost.MultiIndex . 这允许您在数据结构上组合多个索引 . 因此,您可以以线性空间开销为代价,不断查找和删除任何元素 .