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

问题描述

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?

解决方案

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]

• Insertion, removal, and access are O(log(n))
• Iteration is ordered by index

hash_map or std::tr1::unordered_map [a hash table]

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

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