Re: key / value lookup
From: Priyesh (PriyeshPadmavilasom_at_cougarmtn.com)
Date: 10/14/04
- Next message: Igor Tandetnik: "Re: Looks like memory leak"
- Previous message: German: "Re: Looks like memory leak"
- In reply to: Stephen Howe: "Re: key / value lookup"
- Next in thread: Tom Widmer: "Re: key / value lookup"
- Messages sorted by: [ date ] [ thread ]
Date: Thu, 14 Oct 2004 07:18:57 -0700
Thanks for all your help. It helped me expand my options and have a better
understanding on the current data structures that i use.
"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:uJ10CJesEHA.3320@TK2MSFTNGP15.phx.gbl...
>
> "Priyesh" <PriyeshPadmavilasom@cougarmtn.com> wrote in message
> news:eXICgyVsEHA.2192@TK2MSFTNGP14.phx.gbl...
>> Thanks for your reply.
>>
>> The values are unique, with no correlation between keys and values. When
>> a
>> sorted vector is used, wouldnt the lookup times be higher compared to the
>> map version?
>
> No a sorted vector would be faster. map is usually implemented in terms of
> a
> balanced binary tree like Red-Black trees or AVL trees. vector also good
> locality of reference as the standard now guarantees it is a linear strip
> of
> memory (processor cache hits come into play) where as map does not (as
> each
> node could be allocated anywhere in memory, so searching has to trace
> pointers to nodes).
>
> Both are O(log N) to search but I expect a sorted vector to be faster.
>
> Where map wins out is when you have constantly insert or delete arbitrary
> keys. vector is O(N) then. If that does not apply, vector is a winner.
>
>> I suppose the map is using a hashtable
>
> Not normally. A unordered_map or hash_map or similar can have, with the
> right hashing function O(1) lookup.
>
>> so it is an array index
>> access to find the value. Could you please give your reasons otherwise?
>
> Since Dinkumware provides hash_map, map and vector, why don't you try each
> out an measure? Empirical tests are best.
>
> Stephen Howe
>
>
>
>
>
- Next message: Igor Tandetnik: "Re: Looks like memory leak"
- Previous message: German: "Re: Looks like memory leak"
- In reply to: Stephen Howe: "Re: key / value lookup"
- Next in thread: Tom Widmer: "Re: key / value lookup"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
