Nel*_*eal 3 c++ containers c++11
我目前正在寻找提供一些插入（插入或 push_back）和一些删除（擦除，pop_back 不够）方法的容器，并且在调用这两个方法时不会使迭代器或指针无效。
更清楚的是，我想要一组元素，我可以在其中添加元素（我不在乎在哪里），以及在哪里可以删除任何元素（所以我很在乎在哪里）。此外，我会有指向特定元素的外部指针，并且如果我从集合中添加或删除元素，我希望它们保持有效。
据我所知，有两个标准容器可以满足我的需求：set和list. 但是，一般来说，我不喜欢将这样的容器用于这种简单的需求。由于 alist在内部涉及指针并且不提供对其元素的随机访问，我认为这不是一个好的选择。Aset对其元素进行随机访问，但也涉及指针，并且随机访问本身不是在恒定时间内完成的。我认为 aset将是比 a 更好的解决方案list，但我已经考虑过其他事情。
当一个元素被移除时，一个不尝试保持元素连续的简单向量呢？当移除此容器中间的元素时，其位置将为空，并且不会发生任何其他事情。这样，任何迭代器或指针都不会失效。另外，在添加元素时，容器会搜索一个空位置，push_back如果没有这样的孔，则使用简单的。
显然，由于push_back可以vector使用 a使迭代器无效，我将使用 adeque作为实现的基础。我还会使用某种堆栈来跟踪删除元素的漏洞。这样，除了满足我的无失效需求之外，添加、删除和访问元素将在恒定时间内完成。
然而，仍然存在一个问题：当迭代这个容器或简单地通过索引访问一个元素时，我们需要考虑这些漏洞。这就是问题开始超越优势的地方。
因此我的问题是：您如何看待我对那个容器的想法？更重要的是，你会用什么来解决我原来的问题， a set， alist还是别的什么？另外，如果您对最后一个问题（迭代我的容器）有一个漂亮而干净的解决方案，请随时向我展示。
要求 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：调用这两个方法时不会使迭代器和指针失效
forward_list, list, map, multi_map, set, multiset,deque迭代器仅在擦除第一个元素时保持有效），和vector（擦除开始后的所有元素）dequeue（在大多数情况下）， ， ，和（当生长需要刷新）和（如果生长需要重新分配的） unordered_mapunordered_multimapunordered_setunordered_multisetvector要求 3：外部指针应保持有效
与要求 2 的结果大致相同。但是 unordered_map，unordered_multimap，unordered_set和unordered_multiset将满足此要求，因为对元素的引用仍然有效。
要求 4：随机访问元素
map和multimap set并且multiset没有随机访问，但可以使用成员find()（O（logn））来满足它find()可以在 O(n) 中提供解决方法）。 问题 1 的答案： aset或 a哪个更好list？
这取决于您的其他要求。在一个集合中，每个值只能存储一次。如果您的元素都是唯一的，请选择集合。如果不是，您最好选择列表或多重集。
我不知道您存储的元素，但整个元素是搜索参数吗？或者有钥匙吗？在后一种情况下，您真的会去寻找地图。
问题 2 的答案：替代容器呢？
我不会选择 deque 作为您的替代方案。
如果您可以预见元素的最大数量，您可以简单地保留足够的容量以避免重新分配。（满足要求 1、3 和 4）。如果你有一个“空元素”来表示孔，那么你也可以满足要求 2。在最坏的情况下，你可以选择一个向量来排序你的元素和一个指示符（如果它是有效的）。
如果无法确定这样的最大值，我宁愿选择一种map 证明灵活并满足您所有要求的方法。