We help IT Professionals succeed at work.

a question on suitability of stl's map container

chandas
chandas asked
on
Hi guys, I have a simple question on STL's map<> container. My question is, how efficient is it to use the find algorithm with a map when the number of elements is very large? Particularly when the map is unordered? IS the algorithm faster if the map is ordered/sorted first?

Any fact based opinions will be greatly appreciated.

Thanks

Senkwe
Comment
Watch Question

maps are *always* ordered.  By default the sort order is established using operator< on the key, but you can add your own sort criteria.

maps are usually implemented as some sort of binary tree structure, so searching is usually efficient.

Author

Commented:
Thanks Jason for the response.

When are maps ordered? Does this happen implicitly when you call insert? And if so, do you have any idea on how efficient this is? What if what I have to insert is in the middle of some long lap of pairings?

Regards

Senkwe

Author

Commented:
Actually scrap that last comment, I've re-read Jasons post and seen the light via the sentence "By default the sort order is established using operator< on the key"

So going once, going twice for any more light shedding comments...

Regards

Senkwe

Thanks Jason.
To clarify, yes, objects are added when you insert them into the list.

This insertion is fairly efficient usually (but clearly it typically takes longer than inserting into say, a vector) - as I said it is usually a binary tree - so the insertion time should be related the depth of the tree.

Explore More ContentExplore courses, solutions, and other research materials related to this topic.