• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 719
  • Last Modified:

which one is fast BST,CMAP OR STL MAP


i want to know that which one  which one of these will be faster and efficient in respect of searching method

STL MAP (c++)
  • 3
1 Solution
Binary tree searches are Order O(log n)
Hash searches will approximate Order O(1)

MFC CMap is a hash table

BST and STL map is usually implemented as a binary tree, as far as I know, so the BST vs STL MAP in your question will be the same speed.

A properly implemented hash table will be faster for random retrieval than a BST, as retrieval is constant, whereas tree is log N. Trees are more scaleable for huge datasets, however, as they don't require resizing like hash tables.

Given a choice in typical in-memory applications, for speed, I will choose a hash table.

The downside to CMap is it is not portable outside of MFC, so if I want portable code I will use STL containers.
>>BST and STL map is usually implemented as a binary tree,

I meant "STL map is usually implemented as a binary tree (BST)"
davinder101Author Commented:
you mean to say BST and stl map are one and same thing

and STL maps  should preferred than CMap ?

>>you mean to say BST and stl map are one and same thing

Yes, to my knowlege. I checked, specifically for a project last year and the STL implementation was implementing std::map as BST.

>>and STL maps  should preferred than CMap ?

No. I said STL maps are more _portable_, which may or may not be "preferred" for you. If you are a MFC programmer, then portability is not a concern, so if CMap is faster (and it probably is, being a hash table) then use it.

I just prefer to use STL for consistency.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now