473,890 Members | 1,408 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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(),nex t()) 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 1932
MTT wrote:
I need a inverted list behaviour for sequential access of elements for
both direction (previous(),nex t()) 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(),nex t()) 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
15612
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 = myList
2
3020
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, or is it just academic wankery and theoretical flim > > flam ? :) > >B-trees are specifically designed for disk storage. Seeking to a >page takes much longer than reading a page of several kilobytes. >B-trees read the keys for a many-way...
2
1393
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 list until last node where next field is null and free each node. please suggest. thanks lee
25
5375
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 to. The parent id of root of the tree is 0. The length of list is not known. What will be the optimal solution? Node* convertToTree(Node* listHead);
10
9788
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
2177
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. === PEP: xxx Title: Unification of for-statement and list-comprehension syntax
1
3256
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 unable to check it using compilation) but did not find anything that answers my question. I am trying to implement a tree as a doubly linked list.
1
2957
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 <typename Tclass Tree{ private: Tree<T*left;
0
11222
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10918
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10460
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9625
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
8015
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7169
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5845
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6041
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4674
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

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.