Which STL Container?

Question

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?

Answer 1

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'