472,958 Members | 2,322 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

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

Need advice to choise complex data structure (STL)

Hi, I'm need some advice about lists and vectors. I'm doing a program
who needs to have sequential access of a non ordered unit of objects
whose size decreases almost each time the sequence is finished (at the
begining I have about 2500 objects in the unit, after the first acces I
have 2499, then 2435, then 1720 and so on).

The problem is that sometimes after a whole sequence the number of
objects in the unit remains unchanged. After some calculations it seems
that for those 2500 objets I'll need to acces about 180 000 objects
(about 20 acces per object in my unit). The objects in my unit have an
attribute which is used in the whole program as some kind of index.

I was thinking of using a list since I needed sequential acces then I
though of using a multimap which allows me to use de index and stop
using sequential acces but I'm not really sure.

Can somebody give me some advice about the best data structure to use
in my case?

Thanks

Dec 6 '05 #1
3 3115
On 6 Dec 2005 07:05:17 -0800, "Sigmathaar" <si********@gmail.com>
wrote:
Hi, I'm need some advice about lists and vectors. I'm doing a program
who needs to have sequential access of a non ordered unit of objects
whose size decreases almost each time the sequence is finished (at the
begining I have about 2500 objects in the unit, after the first acces I
have 2499, then 2435, then 1720 and so on).

The problem is that sometimes after a whole sequence the number of
objects in the unit remains unchanged. After some calculations it seems
that for those 2500 objets I'll need to acces about 180 000 objects
(about 20 acces per object in my unit). The objects in my unit have an
attribute which is used in the whole program as some kind of index.

I was thinking of using a list since I needed sequential acces then I
though of using a multimap which allows me to use de index and stop
using sequential acces but I'm not really sure.

Can somebody give me some advice about the best data structure to use
in my case?

Thanks


Since you haven't told us what your "sequence" actually does, we can't
really say. I think almost all of the STL containers support forward
iterators for the kind of sequential access that you describe, but
there might be some that don't.

You say the container is unordered, so a map or multimap might not be
the most efficient solution. An implementation of std::map will most
likely keep the data sorted by key to ensure fastest access.

Vectors must store their data in a contiguous memory block. Since it
sounds like you will be doing a lot of deletions at various places
within the vector, this will cause the vector to do a lot of copying
of objects and re-arranging them.

Without knowing more details as to what you are actually doing, I
would say that std::list would probably work OK and also be the most
efficient for deletions and insertions.

--
Bob Hairgrove
No**********@Home.com
Dec 6 '05 #2
The program creates a directory tree from a unit of objects, each
object has the next attribute :

- father : used as an idex, this is the name of the folder that
contaits the folder of the object. if father=0 the object is the root.

The data structure contains all the objects and I have a list of
"fathers". For each "father" the program will locate the "sons" and put
them into a list. After that the program creates one folder per son
into their respective father folder (ex : something/father/son). Every
time a son is located in the object list the object containing it is
destroyed (we only care about the name) that's why the number of object
decreases. Sometimes one "father" may not have a "son" if that's the
case the object list will remain unchanged. The size of the unit of
objects will decrease until there is no more objects left.

Knowing this which data structure will be the best one : a list of a
map (eventually a multimap) or something else?

Dec 6 '05 #3
On 6 Dec 2005 07:46:04 -0800, "Sigmathaar" <si********@gmail.com>
wrote:
The program creates a directory tree from a unit of objects, each
object has the next attribute :

- father : used as an idex, this is the name of the folder that
contaits the folder of the object. if father=0 the object is the root.

The data structure contains all the objects and I have a list of
"fathers". For each "father" the program will locate the "sons" and put
them into a list. After that the program creates one folder per son
into their respective father folder (ex : something/father/son). Every
time a son is located in the object list the object containing it is
destroyed (we only care about the name) that's why the number of object
decreases. Sometimes one "father" may not have a "son" if that's the
case the object list will remain unchanged. The size of the unit of
objects will decrease until there is no more objects left.

Knowing this which data structure will be the best one : a list of a
map (eventually a multimap) or something else?


I would use std:list for this.

--
Bob Hairgrove
No**********@Home.com
Dec 6 '05 #4

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

Similar topics

0
by: Doug R | last post by:
Hello, I have a system that I am writing to automaticly import Credit Transaction data into a SQL Server 2000 Database. I am using a VB.Net application to detect when the file arives and prep...
7
by: seia0106 | last post by:
Hello, Writing a program in c++ that should use complex numbers I have two choices before me. 1- define a struct for complex data i.e struct {float real,imag; }ComplexNum; 2-use an array...
11
by: ma740988 | last post by:
I'm perusing a slide with roughly 12 bullets spread across 3 pages. Each bullet reflects 'advice'. I'm ok with all but 1 bullet, more specifically the bullet that states: " Avoid the STL unless...
3
by: ChadDiesel | last post by:
Hello everyone. I need some advice on table structure for a new project I've been given. One of our customers sends us an Excel spreadsheet each week containing their order. Currently, someone...
3
by: Doug Bell | last post by:
Hi I am putting together a functional specification in preparation for writing a VB Dot Net upgrade an existing Access (VBA) and VB system. It is currently a tiered system with an IBM AS400...
6
by: encoad | last post by:
Hi everyone, I'm new to C# and I am building website which allows users to fill out various forms. All is going well, however I'm having a bit of trouble with one particular issue. The main...
20
by: DemonFox | last post by:
i have started my midterm exersize than is on binary treescan anyone help me on the basics i have started and i have made the following on my tree.h file: struct treenode { int data;...
2
by: nomad | last post by:
I am writing a c++ program and will be implementing a console menu driven prompt. The menu will have several options, and sub-menus may also have multiple options. What is the best data structure...
2
by: jehugaleahsa | last post by:
Hello: I have a bunch of related items that are either parents, children or not directly related to each other. In my case, I have a bunch of database tables joined with foreign keys. Another...
2
by: DJRhino | last post by:
Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...
0
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
0
tracyyun
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
4
NeoPa
by: NeoPa | last post by:
Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :...
3
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...
1
by: Teri B | last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and...
0
NeoPa
by: NeoPa | last post by:
Introduction For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...
0
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
2
by: GKJR | last post by:
Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...

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.