Link List with Tree behaviour

Hi there

I like to know if any class avilable before proceeding on my work.

I need a inverted list behaviour for sequential access of elements for
both direction (previous(),next()) also search element if exist or not
and locate position. Since sequential iteration for search is costly I
like to have access by b-tree behaviour.

Hence I will deal with some large counts of elements (in several K),
memory utilization and search time is my concern.

I'm planning to use sorted arrays as list elements (as clusters)
(enable me b-seacrh in node and reduce node count). planning to
construct a balanced b-tree over these nodes (by include left & right
links).

Any help will be appritiated.

re: Link List with Tree behaviour

MTT wrote:[color=blue]
> I need a inverted list behaviour for sequential access of elements for
> both direction (previous(),next()) also search element if exist or not
> and locate position. Since sequential iteration for search is costly I
> like to have access by b-tree behaviour.
>
> Hence I will deal with some large counts of elements (in several K),
> memory utilization and search time is my concern.[/color]

I believe std::set will work fine for you here. You can iterate through
it in both directions, and check if an element exists and get an
iterator to its position with find(). It will order the elements
according to a less-than predicate which you specify. You might also
consider SGI's non-standard hash_set
(http://www.sgi.com/tech/stl/hash_set.html), a hash-table based set
which has similar capabilities and space/time advantages in some
applications.
--
Derrick Coetzee
I grant this newsgroup posting into the public domain. I disclaim all
express or implied warranty and all liability. I am not a professional.

re: Link List with Tree behaviour

MTT wrote:[color=blue]
> Hi there
>
> I like to know if any class avilable before proceeding on my work.
>
> I need a inverted list behaviour for sequential access of elements[/color]
for[color=blue]
> both direction (previous(),next()) also search element if exist or[/color]
not[color=blue]
> and locate position. Since sequential iteration for search is costly[/color]
I[color=blue]
> like to have access by b-tree behaviour.
>
> Hence I will deal with some large counts of elements (in several K),
> memory utilization and search time is my concern.
>
> I'm planning to use sorted arrays as list elements (as clusters)
> (enable me b-seacrh in node and reduce node count). planning to
> construct a balanced b-tree over these nodes (by include left & right
> links).
>[/color]

I am not sure if this is what you're after, but the
Boost Multi-index Containers Library
(http://boost.org/libs/multi_index/doc/index.html) allows
you to obtain (among other possibilites) a type of
container that behaves like a std::list while having
fast (O(log n)) key-based lookup at the same time. Check
the section entitled "A bidirectional list with fast lookup"
at the tutorial. Hope this helps,
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo