Solved

which one is fast BST,CMAP OR STL MAP

Posted on 2009-05-13
4
715 Views
Last Modified: 2013-12-14
hi,

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

BST (BINARY SEARCH TREE)
CMAP (MFC)
STL MAP (c++)
0
Comment
Question by:davinder101
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
4 Comments
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24381737
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.
0
 
LVL 40

Expert Comment

by:mrjoltcola
ID: 24381746
>>BST and STL map is usually implemented as a binary tree,

I meant "STL map is usually implemented as a binary tree (BST)"
0
 

Author Comment

by:davinder101
ID: 24382389
you mean to say BST and stl map are one and same thing

and STL maps  should preferred than CMap ?

0
 
LVL 40

Accepted Solution

by:
mrjoltcola earned 500 total points
ID: 24384568
>>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.

0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
If you use Adobe Reader X it is possible you can't open OLE PDF documents in the standard. The reason is the 'save box mode' in adobe reader X. Many people think the protected Mode of adobe reader x is only to stop the write access. But this fe…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.

624 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question