Re: Mapping range of addresses

[shreyas krishnan <shreyas76 at gmail dot com>]

I understand a tree, perhaps height balanced  would give me a O(logn).
 I am also worried abt
the constant factor for these or in other words the quality of
compiler generated code for such mechanisms. Any ideas on that ?

Shrey 

On 9/19/05, Paul Koning <pkoning@equallogic.com> wrote:
> >>>>> "shreyas" == shreyas krishnan <shreyas76@gmail.com> writes:
> 
>  shreyas> Hi , I am looking for an efficient data structure to map
>  shreyas> from a range of addresses to a single address.  As it is
>  shreyas> used at runtime, I want it to be as efficient as possible,
>  shreyas> with perhaps updaing more important that retreiving.  Are
>  shreyas> there any examples of such data structure ( and optimized
>  shreyas> code to use it) in gcc,binutils ?
> 
> How many?  Order of 10, or 1000, or a million?
> 
> Read some algorithms textbooks for ideas.  Knuth vol. 3, Cormen
> Leiserson Rivest "Introduction to Algorithms", etc.
> 
> AVL trees take O(log(N)) time for insert, delete, and lookup.  Those
> are often a nice solution.
> 
>     paul
> 
>