Solved

which one is fast BST,CMAP OR STL MAP

Posted on 2009-05-13
4
713 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

Enroll in May's Course of the Month

May’s Course of the Month is now available! Experts Exchange’s Premium Members and Team Accounts have access to a complimentary course each month as part of their membership—an extra way to increase training and boost professional development.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
notReplace  challenge 53 152
Use of condition with 'serial' in ansible 2 102
Unix Command -- Challenging  question 7 106
import as existing maven project 3 77
Introduction: Displaying information on the statusbar.   Continuing from the third article about sudoku.   Open the project in visual studio. Status bar – let’s display the timestamp there.  We need to get the timestamp from the document s…
Introduction: Ownerdraw of the grid button.  A singleton class implentation and usage. Continuing from the fifth article about sudoku.   Open the project in visual studio. Go to the class view – CGridButton should be visible as a class.  R…
The viewer will learn how to use and create keystrokes 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.

734 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