Solved

which one is fast BST,CMAP OR STL MAP

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

Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
MAC and PC - Cheap video editing tools 4 132
mapBully challenge 6 136
What is the Best Editor for PHP Development ? 5 75
Bartender label printing - switch on and off graphics 3 40
Jaspersoft Studio is a plugin for Eclipse that lets you create reports from a datasource.  In this article, we'll go over creating a report from a default template and setting up a datasource that connects to your database.
Have you tried to learn about Unicode, UTF-8, and multibyte text encoding and all the articles are just too "academic" or too technical? This article aims to make the whole topic easy for just about anyone to understand.
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.

831 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