容器，不会使迭代器（和指针）无效

Question

我目前正在寻找提供一些插入（插入或push_back）和一些删除（擦除，pop_back是不够的）方法的容器，并且这不会使迭代器或指针无效调用这两种方法。更清楚地说，我想要一组元素，我可以添加一个元素（我不关心在哪里），以及在哪里可以删除任何元素（所以我在意在哪里）。另外，我会有指向特定元素的外部指针，并且如果我从集合中添加或删除元素，我希望它们保持有效。

据我所知，有两个标准容器可以满足我的需求：set和list。但是，一般来说，我不喜欢使用这样的容器来满足这样简单的需求。由于list在内部涉及指针，并不提供随机访问其元素，我认为这不是一个好的选择。 A set对其元素具有随机访问权限，但也涉及指针，并且随机访问本身不是在恒定时间内完成的。我认为set会比list更好的解决方案，但我想过其他的东西。

那么当一个元素被删除时，一个简单的向量不会试图保持元素是连续的呢？当移除该容器中间的元素时，其位置将是空的，并且不会发生其他情况。这样，没有迭代器或指针会失效。此外，添加元素时，容器将搜索空位置，如果没有这样的空洞，则使用简单的push_back。

很明显，因为push_back可以使vector无效迭代器，所以我会使用deque作为实现的基础。我也会使用某种堆栈来跟踪删除元素的洞。通过这种方式，除了满足我的无效化需求外，还可以在一段时间内添加，删除和访问元素。

但是，仍然存在一个问题：在遍历这个容器或仅仅通过索引访问元素时，我们需要考虑这些漏洞。这就是问题开始超越优势的地方。

因此，我的问题是：你怎么看待我对这个容器的想法？ 更重要的是，你会用我的原始问题，set，list还是其他什么？ 另外，如果你对最后一个问题有很好的解决方案（遍历我的容器），请随时向我展示。

Answer 1

要求1：插入（插入或推回）和一些去除（擦除，而不仅是最后一个元素）

• 符合候选：deque，forward_list，list，map，multi_map，set ，multiset，unordered_map，unordered_multimap，unordered_set，unordered_multiset，和vector

• 淘汰候选：array（无insert或push_back），queue，priority_queue和stack（无erase，仅pop）

要求2：调用这两种方法时，不会失效的迭代器也不指针

• 符合条件的候选人也符合要求1：forward_list，list,map,multi_map，set，multiset，
• 上擦除被淘汰：deque（擦除第一要素，只有当迭代器仍然有效），并vector（擦除开始后的所有元素）
• 在插入时被淘汰：在大多数情况下dequeue（ ），unordered_map，unordered_multimap，unordered_set和unordered_multiset（以防生长需要刷新）和vector（如果生长需要重新分配）

要求3：外部指针应继续有效

Approximaletly比要求。然而unordered_map，unordered_multimap，unordered_set和unordered_multiset会因为元素的引用保持有效satifsy这个要求同样的结果。

要求4：随机存取元件

• 符合满足要求1和2的候选：map和multimap
• 几乎符合候选：set和multiset不具有随机访问，但是能够满足它使用成员find()（O（logn））
• 不符合：列表（虽然算法find()可以在O（n）中提供解决方法）。

回答问题1：哪个更好，一set或list？

这取决于你的其他要求。在一个集合中，每个值只能存储一次。如果您的元素都是唯一的，请选择该组。如果没有，你最好选择列表或multiset。

我不知道你存储的元素，但是整个元素是搜索参数吗？还是有钥匙？在后一种情况下，你真的会去找一张地图。

回答问题2：什么替代容器？

我不会选择deque为您的替代。

如果你能预见元素的最大数量，你可以简单地预留足够的能力，以避免重新分配。 （满足要求1,3和4）。 如果你有一个“空元素”来表示洞，那么你也可以满足要求2.在最坏的情况下，你可以选择一个向量来存储你的元素和一个指标，如果它是有效的。

如果这样的最大值无法确定，我宁愿去一个map这被证明是灵活，满足您的所有需求。