473,327 Members | 1,920 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

Link List with Tree behaviour

MTT
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.

Jul 22 '05 #1
2 1914
MTT wrote:
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 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.
Jul 22 '05 #2
MTT wrote:
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).


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

Jul 22 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

26
by: Alex Panayotopoulos | last post by:
Hello all, Maybe I'm being foolish, but I just don't understand why the following code behaves as it does: - = - = - = - class listHolder: def __init__( self, myList= ): self.myList =...
2
by: barnesc | last post by:
>barnesc at engr.orst.edu wrote: > > So my question is: are there any other *practical* applications of a > > B-tree based list/set/dict ? In other words, is this module totally > > worth coding,...
2
by: Yang Lee | last post by:
Hi, I have a single link list. at the end of the program or in a loop i want to destroy this link list. so is it enough to free the pointer to this link list or do i have to traverse whole link...
25
by: prabhat143 | last post by:
Hi, Given a singly linked, null terminated list, how can it be converted to tree? Each node in the list has three attributes: it's ID, it's parent ID and of course, the next node it's pointing...
10
by: free2cric | last post by:
Hi, I have a single link list which is sorted. structure of which is like typedef struct mylist { int num; struct mylist *next;
6
by: Heiko Wundram | last post by:
Hi all! The following PEP tries to make the case for a slight unification of for statement and list comprehension syntax. Comments appreciated, including on the sample implementation. ===...
1
by: Amit Bhatia | last post by:
User-Agent: OSXnews 2.081 Xref: number1.nntp.dca.giganews.com comp.lang.c++:817435 Hi, I searched online to see if this is valid or not (since my classes are still very incomplete, I am...
1
by: hn.ft.pris | last post by:
I have the following code: Tree.h defines a simple binary search tree node structure ########## FILE Tree.h ################ #ifndef TREE_H #define TREE_H //using namespace std; template...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.