Solved

nested dynamic data structure

Posted on 2002-04-10
17
266 Views
Last Modified: 2010-04-02
I have a possible need to use a nested dynamic data structure and was wondering if there is a common or well known approach to designing one.

I have data in 14 different kinds of blocks where each block contains several data types. I can have a variable
amount of 6 of these blocks.

The set of 14 blocks itself is a block which I will have
a varied amount.

I was going to make structures for each of the 14 blocks to handle the different data types in each type of block,
but I'm not sure how to encompass a set of variable length list of these structures.

unfortunately I didn't run into anything like this while going to school.

I wanted to see if someone could point me in the right direction with links to references of similiar problems or a description of how one might tackle this problem.
0
Comment
Question by:mitchguy
  • 7
  • 6
  • 4
17 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 6932962
Your explanation is a little ambiguous.

Could you provide an example of what you're trying to do?
0
 

Author Comment

by:mitchguy
ID: 6932985
an analogy to what I'm trying to do would be if I needed
to keep records for a dynamic list of people. If each person can have nickels, dimes and pennies. I need to add  new people as they come and each person can add nickels, dimes and pennies as much as they want. A variable length lists of variable length list.

Hope this helps, it's the best I can think of with out going into the details of my work.
0
 
LVL 2

Expert Comment

by:LoungeLizard
ID: 6933760
I don't think there is a standard pattern, if thats what you're after. Typically, you would use a container that keeps a (variable) "list" of references to the actual objects. The objects themselves could then contain (once again a variable) "list" of references to other objects and so on. The "lists" could be hashmaps, deque's or whatever, depending on your needs. All this is provided in the STL so you have to do precious little to set up such a structure. With the STL functionality you cab have many layers of dynamic structures, as you call it.

The only thing you have to be careful of is keeping track of who creates and destroys the objects if you want to use pointers to objects in stead of the actual objects.

I don't know if this answers your question. If not, just shout
0
 
LVL 30

Expert Comment

by:Axter
ID: 6933792
mitchguy,
You can do this, but you have to have a common interface.
0
 
LVL 30

Expert Comment

by:Axter
ID: 6933802
Example of a common interface class:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Xyz
{
public:
     int x;
     int y;
     int z;
     void OnTrigger(void)
     {
          cout << "Xyz" << endl;
     }
};

class Abc
{
public:
     string SomeStr;
     void OnTrigger(void)
     {
          cout << "Abc" << endl;
     }
};

class FooFoo
{
public:
     void OnTrigger(void)
     {
          cout << "FooFoo" << endl;
     }
};

class PureVirtualClass
{
public:
     virtual void OnTrigger(void)=0;
};

template<typename T>
class TargetClassHolder : public PureVirtualClass
{
public:
     TargetClassHolder(T &Src)
     {
          TargetClass = &Src;
     }
     void OnTrigger(void)
     {
          TargetClass->OnTrigger();
     }
     T *TargetClass;
};

class CHandleTrigger
{
public:
     template<typename T>
     void Register(T& Src)
     {
          m_Targets.push_back(new TargetClassHolder<T>(Src));
     }
     void RunAllTriggers(void)
     {
          for(vector<PureVirtualClass*>::iterator i = m_Targets.begin();i != m_Targets.end();++i)
          {
               (*i)->OnTrigger();
          }
     }
     static bool DeleteAndNullifyIterator(PureVirtualClass *& pObj)
     {
          delete pObj;
          pObj = NULL;
          return true;
     }
     ~CHandleTrigger()
     {//Delete the TargetClassHolder(s).  This does NOT delete the actual target class, only the TargetClassHolder
          m_Targets.erase(remove_if(m_Targets.begin(), m_Targets.end(),CHandleTrigger::DeleteAndNullifyIterator), m_Targets.end());
     }
private:
     //can do this here with any class derived from Trigger_vir
     vector<PureVirtualClass*> m_Targets;
};



int main(int argc, char* argv[])
{
     Abc abc;
     Xyz xyz;
     FooFoo foofoo;
     CHandleTrigger MyTriggerHandler;
     MyTriggerHandler.Register(abc);
     MyTriggerHandler.Register(xyz);
     MyTriggerHandler.Register(foofoo);
     MyTriggerHandler.RunAllTriggers();

     system("pause");
     return 0;
}

0
 
LVL 30

Expert Comment

by:Axter
ID: 6933814
With the above example, class CHandleTrigger is able to add any class to  m_Targets, which has an OnTrigger member function.
So the common interface for the above example is the OnTrigger member function.
0
 

Author Comment

by:mitchguy
ID: 6934623
LoungeLizard,
why is it better to use pointers than the object itself?

So if I want to add a new record I need to get a new object and a new pointer or would it be better to encapsulate a pointer in the object itself.
0
 
LVL 30

Expert Comment

by:Axter
ID: 6934654
mitchguy,
Did you look at the code I posted?

CHandleTrigger is able to store a pointer to any object, as long as that object has a common interface.
0
What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

 

Author Comment

by:mitchguy
ID: 6935283
Axter, is your code meant for visual c++?
I'm programming on Linux
0
 
LVL 30

Expert Comment

by:Axter
ID: 6935300
>>Axter, is your code meant for visual c++?

My code is for any standard C++ compiler.  Including Linux.

The only non-portable part of the code is system("pause"), which you can exclude, since it has nothing to do with the class examples.
0
 
LVL 2

Expert Comment

by:LoungeLizard
ID: 6935519
>>why is it better to use pointers than the object itself?

Well, it is not neccesarily better, but more often than not the same objects are used in various places, and then you create the object only once and refer to (either by pointer (*) or reference (&)) afterwards in stead of making local copies everytime you need it. In case of complex objects this would represent a signficant saving in terms of speed and memory
0
 

Author Comment

by:mitchguy
ID: 6935528
Axter,
I'm a little confused on how I can apply what you've
shown me to my problem. Lets say I have a file with the following data:
person1
N N N N N N D D D D D P P
person2
N N N D D P
person3
N D D P P P P
.
.
.
personN
N...D....P...

Where N, D and P are Nickels, Dimes and Pennies and there
can be any number of these in a row.

Would each person be a class in your example?
If Xyz's data members in your example were changed to
int D;
int N;
int P;
how could I store more than one of each type,
Or would D, N and P be classes?

Ideally I would like to insert any new person and their
data anywhere in my list.




0
 
LVL 2

Accepted Solution

by:
LoungeLizard earned 150 total points
ID: 6935604
Simple implementation using STL

#include <list>

class nickel
{
};

class dime
{
};

class penny
{
};

class person
{
  public:
    void addNickel(nickel * n) {myNickels.push_back(n);}
    void addDime(dime * m) {myDimes.push_back(m);}
    void addPenny(penny * p) {myPennies.push_back(p);}
   
    void removeLastNickel() {myNickels.erase(myNickels.end());}
    void removeLastDime() {myDimes.erase(myDimes.end());}
    void removeLastPenny() {myPennies.erase(myPennies.end());}
   
  private:
    list<nickel *> myNickels;
    list<dime *> myDimes;
    list<penny *> myPennies;
};

class group
{
  public:
    void addPerson(person * p) {myPersons.push_back(p);}
   
    void removeLastPerson() {myPersons.erase(myPersons.end());}
   
  private:
    list<person *> myPersons;
};

main()
{
  person p1, p2, p3;
  nickel n1, n2;
  dime d1, d2;
  penny pn1, pn2;
  group myGroup;
 
  p1.addNickel(&n1);

  myGroup.addPerson(&p1);
  myGroup.addPerson(&p2);
 
  // etc...
  // add and remove persons & money to your hearts content

}

See more of the STL here: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vcoriStandardCLibraryReference.asp


0
 

Author Comment

by:mitchguy
ID: 6935945
Lounge lizard,
If I add in your class example
int n;
inside of class nickel
how would I print that value out.
here's what I tried , but I just get an address.
 n1.five = 5;
 n2.five = 6;
 n3.five = 7;
 p1.addNickel(&n1);
 p1.addNickel(&n2);

 p2.addNickel(&n2);
 p2.addNickel(&n3);
 myGroup.addPerson(&p1);
 myGroup.addPerson(&p2);

 std::list <person *>::iterator ptr;
     ptr = myGroup.myPersons.begin();
while(ptr != myGroup.myPersons.end()){
     cout<<"person has "<<*ptr<<endl;
     ptr++;
}
0
 
LVL 2

Expert Comment

by:LoungeLizard
ID: 6935977
I'm not exactly sure what you want to do. Do you want to know how many nickels each person has, or do you want to add a value to the class nickel that you can manually modify?

Anyway, you are using the iterator incorrectly. *ptr will return the CONTENTS of the position in the list where the iterator is pointing to.

Since we have pointers in our list, that means you get a pointer. If you want to print something, you'll have to use (*ptr)->somePrintValue
0
 
LVL 30

Expert Comment

by:Axter
ID: 6935994
This is an example using the code I posted previously.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Penny
{
public:
    int GetValue()
    {
          return 1;
    }
};

class Nickel
{
public:
    int GetValue()
    {
          return 5;
    }
};

class Dime
{
public:
    int GetValue()
    {
          return 10;
    }
};

class Coins
{
public:
    virtual int GetValue()=0;
};

template<typename T>
class TargetClassHolder : public Coins
{
public:
    TargetClassHolder(T &Src)
    {
         TargetClass = &Src;
    }
    int GetValue()
    {
         return TargetClass->GetValue();
    }
    T *TargetClass;
};

class Person
{
public:
    template<typename T>
    void AddToPocket(T& Src)
    {
         m_Targets.push_back(new TargetClassHolder<T>(Src));
    }
    int GetTotal()
    {
          int Total = 0;
         for(vector<Coins*>::iterator i = m_Targets.begin();i != m_Targets.end();++i)
         {
              Total += (*i)->GetValue();
         }
           return Total;
    }
    static bool DeleteAndNullifyIterator(Coins *& pObj)
    {
         delete pObj;
         pObj = NULL;
         return true;
    }
    ~Person()
    {//Delete the TargetClassHolder(s).  This does NOT delete the actual target class, only the TargetClassHolder
         m_Targets.erase(remove_if(m_Targets.begin(), m_Targets.end(),Person::DeleteAndNullifyIterator),
m_Targets.end());
    }
private:
    //can do this here with any class derived from Trigger_vir
    vector<Coins*> m_Targets;
};



int main(int argc, char* argv[])
{
    Penny penny;
    Nickel nickel;
    Dime dime;
    Person MyTriggerHandler;
    MyTriggerHandler.AddToPocket(penny);
    MyTriggerHandler.AddToPocket(nickel);
    MyTriggerHandler.AddToPocket(dime);
    int Total = MyTriggerHandler.GetTotal();
    cout << "Total = " << Total << endl;

    system("pause");
    return 0;
}

0
 

Author Comment

by:mitchguy
ID: 6936019
Thank you both for all of your help. I will post some points for you also Axter.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now