Re: looking for a fast re-usable non-pointer data structure ....

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Tony Gair wrote:
> 
> Does anyone know of  reasonably fast data structure to store a large amount
> of records.

It would help if you provided more information about what precisely you
want. PragmARC.Queue_Bounded is fast, non-pointer, and a data structure,
but since you're using an AVL tree I doubt that it does what you want.

Balanced tree structures tend to be slow for insertion and deletion, but
fast [O(log N)] for searching. You might be interested in a skip list.
Skip lists are approximately O(log N) for searching, and O(1) for
insertion and deletion; I do not understand why people continue to use
balanced trees given the existence of skip lists. See
PragmARC.Skip_List_Unbounded for an implementation of a skip list.

It should be reasonably simple to implement a bounded skip list, just as
it is to implement a bounded list.

-- 
Jeffrey Carter