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

From:

Ulrich Eckhardt <eckhardt@satorlaser.com>

Newsgroups:

microsoft.public.vc.stl

Date:

Wed, 15 Apr 2009 10:27:46 +0200

Message-ID:

<2digb6-1pd.ln1@satorlaser.homedns.org>

Sachin wrote:

Does the Find operation of map container provides optimized way of
searching key values ?

Define what you mean with "optimized".

My needs are
1. Storing millions of record with kay being a string ( always fixed
length 20 characters )
2. and i will have to constantly search the map for a given key .

is Map the best suite or should i implement other search algorithms?
Which Algorithm STL::map implements in find operation ?

Generally, the complexity of std::map operations are documented, see e.g.
the STL's home page at SGI's. Basically, the implementation uses a balanced
tree so you can do a binary search.

In any case, using a hash map or some special container that makes use of
additional info about the key may be faster. Since those probably can be
implemented with the same interface, I'd start off with

typedef std::map<...> my_registry_type;

so that you can lateron replace it after profiling.

Uli

--
Sator Laser GmbH
Gesch??ftsf??hrer: Thorsten F??cking, Amtsgericht Hamburg HR B62 932