首页 文章

从STL列表中删除特定节点

提问于
浏览
1

我需要维护一个项目列表(一些对象),并支持以下操作:

  • 结尾插入

  • 从任何位置删除

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 回答

  • 2

    折衷方案是像大多数std :: set实现一样的红黑树 . 它是插入,搜索和删除的O(log n) . 树木基本上是最终的折衷数据结构 . 他们对任何事情都不是很了不起,但他们总能把工作做得很好 .

    否则,使用链接列表和向量来分析代码,并找出调整向量的大小是否真的很糟糕(这取决于你执行它的频率) .


    可能有一个更好(不优雅,但非常有效)的解决方案,可能只是照顾你的问题 . 您没有消耗该列表,但是如果您可以将值保留为未使用,则可以使用向量并将元素标记为已删除而不是实际删除它 . 或者使用向量并使用单独的位集(或C 03 vector<bool> )告诉您项目是否已删除或有效 . 要删除它,您只需要翻转位图中的位 . 迭代时,只需记住在处理内容之前检查删除位图 . 如果内存不是问题且速度很重要且容易/清晰度很重要,请将 vector<object> 替换为 vector<pair<bool, object>> ,其中 bool 是删除标志 .

  • 0

    你可能想看看Boost.MultiIndex . 这允许您在数据结构上组合多个索引 . 因此,您可以以线性空间开销为代价,不断查找和删除任何元素 .

相关问题