Re: Is STL::map Find operation the optimised ?

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

Alex Blekhman wrote:
"Sachin" wrote:
by optimized
i wanted to know if it is faster than any known Searching
algorithms like
1. linear search 2. B-tree etc

In additiona to other answers. Visual C++ provides
`stdext::hash_map' container, that provides lookups in constant
average time.

but...

If your map contains keys that are long and highly differentiated by
prefixes (i.e, they don't all start with only a few prefixes), then std::map
can actually end up being faster than a hash map, as the hash map requires
examining every character of a search string, while the ordered map's key
comparisions will be able to bail out after examining only a few characters
at the start of the key. For the exact case the OP mentioned (20
characters, millions of records), I would not expect hash_map to be slower.

The other case where std :: map will outperform a hashed map is when you use
an inappropriate hashing function that results in many hash collisions.

To make a long story short, both are great containers, both will give good
performance in most cases, which one is best depends on your application and
the only way to know for sure which one is better for your data is to time
both of them with your real data.

-cd


.

Relevant Pages

  • Re: Question for the math wizards...
    ... string of characters that isn't too long, ... bits per character with base-32 encoding, then we are limited to shipping ... to know if it was possible given m to map m via a function Fto an m' ... In real world terms, say n is 100 digits, m is 50 digits, and I want to ...
    (sci.crypt)
  • Re: Word count of minimum vocabulary
    ... >> Nor do I have to map a Japanese Kanji to a word when I read ... tie it up with any words -- whether Chinese words or Japanese ones. ... António> to add to 'ideograph being used as a logograph'? ... the characters, ...
    (sci.lang)
  • Re: Converting non-control ASCII chars to KeyEvent key codes?
    ... range lets us map letters quite easily, ... namely all non- control ASCII characters. ... array of key codes because some chars would map to more than ... presses and releases. ...
    (comp.lang.java.programmer)
  • Re: Converting non-control ASCII chars to KeyEvent key codes?
    ... map letters quite easily, but I'm after broader input, namely all ... whole String of characters to be fed to the Robot instance. ... presses and releases. ...
    (comp.lang.java.programmer)
  • Re: printing grep results in Perl
    ... The regex you are looking for should look something like this (Untested ... element that got into $_ was less than four characters long, ... EW> I have spent half the day looking at map and I still don't get it. ... substitution but a simple grab. ...
    (perl.beginners)