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])

一种选择是在地图中使用迭代器，有没有更简单的方法？

4

2 回答 2

2

妥协是像大多数 std::set 实现一样的红黑树。插入、搜索和删除的时间为 O(log n)。树基本上是最终的折衷数据结构。他们在任何事情上都没有什么了不起的，但他们总是把工作做得足够好。

否则，使用链表和向量来分析您的代码，并确定调整向量大小是否真的很糟糕（这取决于您执行此操作的频率）。

可能有更好（不优雅但非常有效）的解决方案可以解决您的问题。您还没有提到您将如何使用该列表，但如果您可以将一个值留作未使用，您可以使用一个向量并将一个元素简单地标记为已删除，而不是实际删除它。或者使用一个向量和一个单独的位集（或 C++03 vector<bool>）告诉你一个项目是否被删除或有效。要删除它，您只需翻转位图中的位。迭代时，只记得在处理内容之前检查删除位图。如果内存不是问题，只有速度很重要，易用性/清晰度很重要，请将 替换vector<object>为vector<pair<bool, object>>删除bool标志的位置。

于 2012-05-04T07:22:09.287 回答
0

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

于 2012-05-04T07:16:29.993 回答