哪个STL容器？ [英] Which STL Container?

问题描述

我需要一个容器（不一定是一个STL容器），它让我可以轻松做到：

I need a container (not necessarily a STL container) which let me do the following easily:

• 插入和删除元素任何位置


• 按索引访问元素


• 以任何顺序迭代元素

我使用 std :: list ，但它不会让我插入任何位置（它的确，但为了我必须遍历所有的元素然后插入在我想要的位置，这是慢，因为列表可能是巨大的）。所以，你能推荐任何有效的解决方案吗？

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?

推荐答案

我不完全清楚你的意思是迭代任何顺序 - 这是否意味着你不关心顺序，只要你可以迭代，或者你想能够使用任意定义的标准迭代？这些是非常不同的条件！

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 [通常为红黑树]

std::map [a red-black tree, typically]

• 插入，删除和访问都是O（log（n））


• 迭代按索引排序

hash_map 或 std :: tr1 :: unordered_map [哈希表]

• 插入，删除和访问都是（约）O（1）


• 迭代是随机 >
  

• Insertion, removal, and access are all (approx) O(1)
• Iteration is 'random'

这篇关于哪个STL容器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！