不会使迭代器(和指针)无效的容器 [英] Container that does not invalidate iterators (and pointers)

问题描述

我目前正在寻找一种容器，该容器提供一些插入(insert或push_back)和一些除去(擦除，pop_back不足)的方法，并且在调用这两种方法时不会使迭代器或指针无效.

I am currently looking for container that provides some inserting (insert or push_back) and some removing (erase, pop_back is not sufficient) methods, and that does not invalidate iterators nor pointers when calling these two methods.

更清楚地讲，我想要一组元素，可以在其中添加元素(我不在乎)，而在哪里可以删除任何元素(所以我不在乎).另外，我将具有指向特定元素的外部指针，并且如果我从集合中添加或删除元素，我希望它们保持有效.

More clearly, I want a set of elements where I can add an element (I do not care where), and where I can remove any element (so I do care where). In addition, I would have external pointers to specific elements, and I want them to remain valid if I add or remove an element from the set.

据我所知，有两个标准容器可以满足我的需求: set 和 list .但是，总的来说，我不喜欢将这样的容器用于如此简单的需求.由于 list 在内部涉及指针，并且不提供对其元素的随机访问，因此我认为这不是一个好选择.一个 set 可以对其元素进行随机访问，但是还涉及指针，并且随机访问本身并不是在恒定时间内完成的.我认为 set 会比 list 更好，但我已经想到了其他事情.

There are, to my knowledge, two standard containers that answer my needs : set and list. However, generally speaking, I do not like to use such containers for such simple needs. Since a list is involving pointers internally and does not provide random access to its elements, I think it is not a good choice. A set has random access to its elements, but is also involving pointers, and the random access itself is not done in constant time. I think that a set would be a better solution than a list, but I have thought about something else.

一个简单的向量在删除元素时不尝试保持元素连续是怎么回事?当删除此容器中间的元素时，其位置将为空，并且不会发生其他任何事情.这样，任何迭代器或指针都不会失效.另外，在添加元素时，容器将搜索一个空位置，如果没有此类孔，则使用简单的 push_back .

What about a simple vector that does not try to keep the elements contiguous when an element is removed ? When removing an element in the middle of this container, its position would be empty, and nothing else would happen. This way, no iterator or pointer would be invalidated. Also, when adding an element, the container would search for an empty position, and use a simple push_back if there is no such hole.

很显然，由于 push_back 可以使用 vector 使迭代器无效，因此我将使用 deque 作为实现的基础.我还将使用某种堆栈来跟踪孔的去除情况.这样，除了满足我的无效请求外，还可以在固定时间内完成添加，删除和访问元素的操作.

Obviously, since push_back can invalidate iterators with a vector, I would use a deque as the basis of implementation. I would also use some sort of stack to keep track of the holes from removing elements. This way, adding, removing, and accessing an element would be done in constant time, in addition to satisfying my no-invalidation needs.

但是，仍然存在一个问题:在此容器上进行迭代或仅通过索引访问元素时，我们需要考虑漏洞.这就是问题开始超越优势的地方.

However, there is still one problem : when iterating over this container or simply accessing an element by index we would need to take the holes into account. And that is where the problems start to surpass the advantages.

因此，我的问题是:您如何看待我对那个容器的想法?更重要的是，对于我的原始问题，您将使用什么 set ， list 或其他?另外，如果您对最后一个问题有一个很好的解决方案(在我的容器上反复进行)，请随时向我展示.

Hence my question : what do you think about my idea for that container ? More importantly, what would you use for my original problem, a set, a list or something else ? Also, if you have a nice and clean solution to the last problem (iterating over my container), feel free to show me.

推荐答案

要求1:插入(插入或推回)和一些删除(擦除，而不仅仅是最后一个元素)

Requirement 1: inserting (insert or push back) and some removing (erase, and not only the last element)

• 符合条件的候选人: deque ， forward_list ， list ， map ， multi_map ， set ， multiset ， unordered_map ， unordered_multimap ， unordered_set ， unordered_multiset 和 vector

• Compliant candidates: deque, forward_list, list, map, multi_map, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset, and vector

已排除的候选项:数组(无 insert 或 push_back )，队列，优先级队列和 stack (无 erase ，仅 pop )

Eliminated candidates: array (no insert or push_back), queue, priority_queue and stack (no erase, only pop)

要求2:在调用这两个方法时不会使迭代器或指针无效

Requirement 2: does not invalidate iterators nor pointers when calling these two methods

• 符合条件的候选人也满足要求1: forward_list ， list ， map ， multi_map ，设置，多集，
• 消除擦除: deque (迭代器仅在擦除第一个元素时才有效)和 vector (在擦除开始后的所有元素)
• 取消插入:出队(在大多数情况下)， unordered_map ， unordered_multimap ， unordered_set 和 unordered_multiset (如果增长需要重新哈希)和 vector (如果增长需要重新分配)

• Compliant candidates from also satifying requirement 1: forward_list, list, map, multi_map, set, multiset,
• Eliminated on erase: deque (iterator remain valid only when erasing first element), and vector (all elements after the start of erasure)
• Eliminated on insert: dequeue (in most of the cases), unordered_map, unordered_multimap, unordered_set and unordered_multiset (in case the growth requires a rehash) and vector (in case growth requires of reallocation)

要求3:外部指针应保持有效

与需求2大致相同的结果.但是， unordered_map ， unordered_multimap ， unordered_set 和 unordered_multiset 会让人满意此要求是因为对元素的引用仍然有效.

Approximaletly the same result than for requirement 2. However unordered_map, unordered_multimap, unordered_set and unordered_multiset would satifsy this requirements because references to elements remain valid.

要求4:随机访问元素

• 符合条件1和2的候选者: map 和 multimap
• 几乎符合条件的候选者: set 和 multiset 没有随机访问权限，但是可以使用成员 find()(O(登录))
• 不符合规定:列表(尽管算法 find()可以在O(n)中提供解决方法).

• Complying candidates satisfying requirement 1 and 2: map and multimap
• Almost complying candidates: set and multiset do not have a random access, but can satisfy it using member find() (O(logn))
• Non compliant: list (although algorithm find() could provide a workaround in O(n)).

问题1的答案: set 或 list 哪个更好?

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

It depends on your other requirements. In a set each value can only be stored once. If your elements are all unique , choose the set. If not you'd better opt for the list or the multiset.

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

I do not know the elements that you're storing, but is the whole element the search argument ? Or is there a key ? In the latter case, you'd really go for a map.

问题2的答案:替代容器呢?

我不会为您选择双端队列.

I wouldn't opt for deque for your alternative.

如果可以预见最大元素数量，则可以简单地保留足够的容量以避免重新分配.(满足要求1、3和4).如果您有一个空元素"来表示孔，那么您也可以满足要求2.在最坏的情况下，您可以选择对元素进行矢量排序的方法和一个有效的指示符.

If you can foresee the maximum number of elements, you could simply reserve enough capacity to avoid reallocation. (satisfying requirement 1, 3 and 4). If you have an "empty element" to represent holes, you could then also satisfy requirement 2. In worst case you could opt for a vector sotring your element and an indicator if it's valid.

如果无法确定这样的最大值，我宁愿选择一个 map 来证明它是灵活的并且可以满足您的所有要求.

If such a maximum is not determinable, I'd rather go for a map which proves to be flexible and satisfy all your requirements.

这篇关于不会使迭代器(和指针)无效的容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！