哪个STL容器？
我需要一个容器（不一定是 STL 容器），它可以让我轻松执行以下操作：
- 在任意位置插入和删除元素
- 按索引访问元素
- 以我使用的任何顺序迭代元素
std::list，但它不会让我在任何位置插入（确实如此，但为此我必须迭代所有元素，然后在我想要的位置插入，这很慢，因为列表可能很大） 。那么您能推荐一些有效的解决方案吗？
I need a container (not necessarily a STL container) which let me do the following easily:
- Insertion and removal of elements at any position
- Accessing elements by their index
- Iterate over the elements in any order
I used std::list, but it won't let me insert at any position (it does, but for that I'll have to iterate over all elements and then insert at the position I want, which is slow, as the list may be huge). So can you recommend any efficient solution?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（10）
std::vector
[此处填充“15 个字符”]
std::vector
[padding for "15 chars" here]
我并不完全清楚“以任意顺序迭代元素”是什么意思 - 这是否意味着您不关心顺序，只要可以迭代即可，或者您希望能够任意使用迭代定义的标准？这些是非常不同的条件！
假设您的意思是迭代顺序并不重要，那么我会想到几种可能的容器：
std::map[通常是红黑树]hash_map或std::tr1::unordered_map[哈希表]It's not completely clear to me what you mean by "Iterate over the elements in any order" - does this mean you don't care about the order, as long as you can iterate, or that you want to be able to iterate using arbitrarily defined criteria? These are very different conditions!
Assuming you meant iteration order doesn't matter, several possible containers come to mind:
std::map[a red-black tree, typically]hash_maporstd::tr1::unordered_map[a hash table]这张图会对你有很大帮助，我想是的。
This diagram will help you a lot, I think so.
vector或deque都适合。vector将提供更快的访问速度，但deque将提供更快的插入和删除。Either a
vectoror adequewill suit.vectorwill provide faster accesses, butdequewill provide faster instertions and removals.不幸的是，你不可能在恒定的时间内拥有所有这些。决定是否要进行更多插入或读取，并以此为基础做出决定。
例如，向量将允许您在恒定时间内通过索引访问任何元素，以线性时间迭代元素（所有容器都应该允许这样做），但插入和删除需要线性时间（比列表慢）。
Well, you can't have all of those in constant time, unfortunately. Decide if you are going to do more insertions or reads, and base your decision on that.
For example, a vector will let you access any element by index in constant time, iterate over the elements in linear time (all containers should allow this), but insertion and removal takes linear time (slower than a list).
您可以尝试 std::deque，但它不会提供恒定时间删除中间的元素，但它支持
末尾的元素数
序列
中间的元素。
You can try std::deque, but it will not provide the constant time removal of elements in middle but it supports
of elements at the end of the
sequence
elements in the middle.
一个向量。当您擦除任何项目时，将最后一个项目复制到要擦除的项目上（或交换它们，以更快者为准）并 pop_back。要在某个位置插入（但如果顺序无关紧要，为什么要插入！？），push_back 该位置的项目并用要插入的项目覆盖（或交换）。
A vector. When you erase any item, copy the last item over one to be erased (or swap them, whichever is faster) and pop_back. To insert at a position (but why should you, if the order doesn't matter!?), push_back the item at that position and overwrite (or swap) with item to be inserted.
通过“以任何顺序迭代元素”，您的意思是您需要按索引向前和向后支持，还是意味着顺序并不重要？
您需要一棵称为未排序计数树的特殊树。这允许 O(log(n)) 索引插入、O(log(n)) 索引删除和 O(log(n)) 索引查找。它还允许向前或向后进行 O(n) 迭代。使用这些的一个例子是文本编辑器，其中编辑器中的每一行文本都是一个节点。
以下是一些参考资料：
By "iterating over the elements in any order", do you mean you need support for both forward and backwards by index, or do you mean order doesn't matter?
You want a special tree called a unsorted counted tree. This allows O(log(n)) indexed insertion, O(log(n)) indexed removal, and O(log(n)) indexed lookup. It also allows O(n) iteration in either the forward or reverse direction. One example where these are used is text editors, where each line of text in the editor is a node.
Here are some references:
订单统计树在这里可能很有用。它基本上只是一棵普通的树，只不过树中的每个节点都包含其左子树中的节点计数。这支持所有基本运算，且复杂度不低于对数。在插入过程中，每当您在左子树中插入一个项目时，都会增加该节点的计数。在删除过程中，只要从左子树中删除，就会减少节点的计数。要索引到节点 N，请从根开始。根在其左子树中具有节点计数，因此您检查 N 是否小于、等于或大于根的计数。如果小于，则以同样的方式在左子树中搜索。如果它更大，则沿右子树下降，将根的计数添加到该节点的计数，然后将其与 N 进行比较。继续，直到 A) 您找到了正确的节点，或者 B) 您确定存在更少的节点大于树中的 N 个项目。
An order statistic tree might be useful here. It's basically just a normal tree, except that every node in the tree includes a count of the nodes in its left sub-tree. This supports all the basic operations with no worse than logarithmic complexity. During insertion, anytime you insert an item in a left sub-tree, you increment the node's count. During deletion, anytime you delete from the left sub-tree, you decrement the node's count. To index to node N, you start from the root. The root has a count of nodes in its left sub-tree, so you check whether N is less than, equal to, or greater than the count for the root. If it's less, you search in the left subtree in the same way. If it's greater, you descend the right sub-tree, add the root's count to that node's count, and compare that to N. Continue until A) you've found the correct node, or B) you've determined that there are fewer than N items in the tree.
（来源：adrinael.net）
但听起来你正在寻找一个具有以下属性的单个容器：
这是不可能的。一种利益会带来一种损害。选择容器意味着妥协。
(source: adrinael.net)
But it sounds like you're looking for a single container with the following properties:
And that's impossible. One benefit causes a detriment. Choosing a container is about compromise.