Need advice to choise complex data structure (STL)

Discussion in 'C++' started by Sigmathaar, Dec 6, 2005.

  1. Sigmathaar

    Sigmathaar Guest

    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
     
    Sigmathaar, Dec 6, 2005
    #1
    1. Advertising

  2. On 6 Dec 2005 07:05:17 -0800, "Sigmathaar" <>
    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
     
    Bob Hairgrove, Dec 6, 2005
    #2
    1. Advertising

  3. Sigmathaar

    Sigmathaar Guest

    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?
     
    Sigmathaar, Dec 6, 2005
    #3
  4. On 6 Dec 2005 07:46:04 -0800, "Sigmathaar" <>
    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
     
    Bob Hairgrove, Dec 6, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jeff

    complex data structure

    Jeff, Jun 26, 2004, in forum: Perl
    Replies:
    5
    Views:
    520
  2. =?Utf-8?B?UGV0ZXI=?=

    List Control, multiple choise from the code

    =?Utf-8?B?UGV0ZXI=?=, Oct 13, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    1,227
    N. Demos
    Oct 13, 2004
  3. Ram
    Replies:
    3
    Views:
    441
    Barry Schwarz
    Mar 24, 2009
  4. TNG

    Newbie, Language choise in cookie

    TNG, Mar 6, 2005, in forum: ASP General
    Replies:
    2
    Views:
    149
    Bullschmidt
    Mar 7, 2005
  5. Klaas Seelen

    retrieving the choise of a combo box

    Klaas Seelen, Apr 18, 2005, in forum: ASP General
    Replies:
    5
    Views:
    149
    Klaas Seelen
    Apr 18, 2005
Loading...

Share This Page