Random access to ditionaries.

Thread View: comp.lang.c++.leda

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Alex Beascoechea Wed, 18 Oct 1995 20:13

#141

Author: Alex Beascoechea
Date: Wed, 18 Oct 1995 20:13

17 lines
1326 bytes

I was trying to find a way to randomly access one element in one of LEDA's
dictionary structures. If a data structure is sorted by a linear order I would
like to efficiently access an element between 1..struct.size() maybe using
the array indirection operator. At the same time that insertion/deletion/search
keep being efficient.

E.g. give me the jth item in the sorted sequence A should be something like
A[j].

In particular I do not see why this could not be part of the sortseq interface,
and the access can probably be O(nlogn) , maybe adding some field to the
implementation?

The only way I see I could get access to the jth element now is by traversing
the data structure from the begining using the succ method j times. 

Or maybe I am missing something?

Re: Random access to ditionaries.

#142

Author: Alex Beascoechea
Date: Wed, 18 Oct 1995 20:58

7 lines
807 bytes

Alex Beascoechea <alex@cat.rpi.edu> wrote:

>In particular I do not see why this could not be part of the sortseq interface,
>and the access can probably be O(nlogn) , maybe adding some field to the
>implementation?
>
Of course I meant O(log n) :-)

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads