我目前正在寻找提供一些插入（insert 或push_back）和一些删除（erase，pop_back 不够）方法的容器，并且在调用这两个方法时不会使迭代器或指针无效。
更清楚地说，我想要一组元素，我可以在其中添加元素（我不关心在哪里），以及在哪里可以删除任何元素（所以我关心在哪里）。此外，我会有指向特定元素的外部指针，并且如果我从集合中添加或删除元素，我希望它们保持有效。
据我所知，有两个标准容器可以满足我的需求：set and list。不过，一般来说，我不喜欢使用这样的容器来满足这么简单的需求。自从一个list在内部涉及指针并且不提供对其元素的随机访问，我认为这不是一个好的选择。 Aset可以随机访问其元素，但也涉及指针，并且随机访问本身不是在恒定时间内完成的。我认为一个set将是一个比list，但我想到了别的事情。
一个简单的向量在删除元素时不尝试保持元素连续怎么样？当删除该容器中间的元素时，它的位置将为空，并且不会发生其他任何事情。这样，迭代器或指针就不会失效。另外，当添加元素时，容器会搜索空位置，并使用简单的push_back如果没有这个洞的话。
显然，自从push_back可以使迭代器无效vector，我会用一个deque作为实施的基础。我还会使用某种堆栈来跟踪删除元素的漏洞。这样，除了满足我的无失效需求之外，添加、删除和访问元素也可以在恒定时间内完成。
然而，仍然存在一个问题：当迭代这个容器或简单地通过索引访问元素时，我们需要考虑这些漏洞。这就是问题开始超过优势的地方。
因此我的问题是：您对我关于该容器的想法有何看法？
更重要的是，你会用什么来解决我原来的问题，aset, a list或者是其他东西 ？
另外，如果您对最后一个问题（迭代我的容器）有一个好的、干净的解决方案，请随时向我展示。
要求1：插入（插入或推回）和一些删除（擦除，不仅仅是最后一个元素）
符合要求的候选人：deque, forward_list, list, map, multi_map, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset, and vector
被淘汰的候选人：array (no insert or push_back), queue, priority_queue and stack (no erase, only pop)
要求2：调用这两个方法时不会使迭代器或指针失效
- 同时满足要求 1 的合格候选人：
forward_list, list, map, multi_map, set, multiset,
- 擦除时消除：
deque（迭代器仅在擦除第一个元素时保持有效），并且vector（擦除开始后的所有元素）
- 插入时消除：
dequeue（在大多数情况下），unordered_map, unordered_multimap, unordered_set and unordered_multiset（以防增长需要重新调整）和vector（如果增长需要重新分配）
要求3：外部指针应保持有效
与要求 2 的结果大致相同。但是unordered_map, unordered_multimap, unordered_set and unordered_multiset将满足要求，因为对元素的引用仍然有效。
要求4：随机访问元素
- 符合要求 1 和 2 的合格候选人：
map and multimap
- 几乎符合要求的候选人：
set and multiset没有随机访问，但可以使用成员来满足find()(O(logn))
- 不合规：列表（尽管算法
find()可以提供 O(n)) 的解决方法。
回答问题1：哪个更好，一个set or a list ?
这取决于您的其他要求。在一个集合中，每个值只能存储一次。如果您的元素都是独一无二的，请选择该集合。如果没有，您最好选择列表或多重集。
我不知道您要存储的元素，但整个元素是搜索参数吗？或者有钥匙吗？在后一种情况下，你真的会去找地图。
回答问题2：替代容器怎么样？
我不会选择双端队列作为您的替代方案。
如果您可以预见元素的最大数量，您可以简单地保留足够的容量以避免重新分配。 （满足要求1、3和4）。
如果您有一个“空元素”来表示孔，那么您也可以满足要求 2。在最坏的情况下，您可以选择一个向量来存储您的元素和一个指示符（如果它有效）。
如果这样的最大值无法确定，我宁愿选择map事实证明，它非常灵活，可以满足您的所有要求。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
