c++ - 从 STL 列表中删除特定节点

Question

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

• 最后插入
• 从任何位置移除

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

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

Answer 1

折衷方案将是像大多数 std::set 实现一样的红黑树。插入、搜索和删除的复杂度为 O(log n)。树基本上是最终的折衷数据结构。他们没什么了不起的，但他们总能把工作做好。

否则，使用链表和 vector 分析您的代码，并确定调整 vector 大小是否真的像它可能的那样糟糕(这取决于您这样做的频率)。

---

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