Solved

which one is fast BST,CMAP OR STL MAP

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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Introduction: Dynamic window placements and drawing on a form, simple usage of windows registry as a storage place for information. Continuing from the first article about sudoku.  There we have designed the application and put a lot of user int…
Introduction: The undo support, implementing a stack. Continuing from the eigth article about sudoku.   We need a mechanism to keep track of the digits entered so as to implement an undo mechanism.  This should be a ‘Last In First Out’ collec…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

685 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