Thread: Help designing data structure

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    101

    Help designing data structure

    Hello!

    I'm trying to learn data structures in C++. I wanted to implement the diagram http://i84.photobucket.com/albums/k3...dataStruct.png

    I know how to this in Java but in C++ I'm sure about
    A- data types for the list of references,
    B- how should I make this references (pointers?) and
    C- if I should have nested classes.

    Please give your 2cents.
    Last edited by kotoko; 12-30-2010 at 04:35 PM.

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    A. Unless you have some reason not to, use a vector.

    B. Pointers, or rather a so called "smart" pointer would make sense. References are types in C++, but they don't require additional storage, so you can't make a vector of them.

    C. It depends on how this design is put to use.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    A - you don't have any lists of reference, so that's pretty easy. Unless you mean "I want to model the tables of references as a list", in which case, go ahead. (Although lists don't offer random access -- you have to go through the list in order whenever you want to do something. Depending on what you actually intend to do, that may or may not be a good thing.)

    B - If the people who did this are speaking Java, then "ref" just means "Help! I'm doing Java!" since everything is a ref in Java. And in that case, you yourself would need to decide whether you really do need references to objects or just plain objects. (For instance, I personally would expect "Piece of Clothing" to own its own "Clothing Type" object, rather than just link to an external clothing type object. But then, I wouldn't have the "Clothing Type" object contain a table inside it either, so that's already a wash.) If you want to store that as a reference, then by all means (that does mean that the Clothing Type has to already exist before you construct any Piece of Clothing). As to the lists/tables, I don't know if I've ever seen STL containers of reference objects. I don't know if there's a good reason for it, but there probably is. You can store pointers to objects instead if you want. Someone will come along soon and tell you to use smart pointers here, I'm pretty sure.

    C - I have no idea what you mean here. I don't see any reason to do any inheritance; I don't see any reason to define a class inside another class. You may have an object containing a member that is an instance of another class, but that is neither exceptional nor what I would think of when I think of "nested class".

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    A You mean stl vectors? (C++ STL Tutorial) I would like to have a hashtable if I was in Java because of the O(1) complexity of finding stuff. I found out about maps (map - C++ Reference) would that be appropriate?

    B Smart pointers are objects so you can use them in vectors, right?

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    A. Sure you can use a map, it looks like a hash table, so if that is what you need then go for it.

    B. Yes. But pay attention to what tabstop is saying. A C++ design would probably be a lot different. For example, I would create one object out of this design, Clothing. An outfit is just a set of clothing so I don't think it requires a dedicated type of its own, and I personally see a lot of redundancy in the picture.

  6. #6
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    (My previous post was in reply to whiteflags, so this one is for you tabstop)

    A - "I want to model the tables of references as a list". About the random access you're quite right, I do need it and would like to ask you too if do you think the Map object is appropriate.

    B - I need references to objects (smart pointers was mentioned by whiteflags). This is because one Piece of Clothing can be a part of many Outfits and I will probably have to list Pieces of Clothing by Tag, Outfit and Clothing Type. This is why I thought it would be best to just have one object Piece of Clothing and then pointers (smart or not) to it. Also to make editing a Piece of Clothing possible.

    C - Not my brightest moment, lets just forget about nested.

  7. #7
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    About redundancy and C++ design. This is one (ok two) big reasons I wrote the post in the first place. What would a good C++ design be like?

    In the end I want to be able to know other Pieces of Clothing with the same Tag, in the same Outfit and of the same type. Having one object and then pointers was what I came up with to be able to do this quick, with only one copy of the each object so I could edit it after creation.

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    A map requires a [key]=value pair. I don't see any natural keys for any of your tables, really.

    And I am pretty sure you're a level off, so to speak, in terms of your desire for searching. If you want to list Pieces of Clothing that fit a particular Tag, Outfit, or Clothing Type, that requires zero searching at all, as far as these data structures go. Once I hand you an Outfit, the container inside it contains (pointers to) all the Pieces of Clothing that go with it, no searching needed. That container could be a list, a vector, a queue, or a deque, and no one would notice or care -- because all you have to do is iterate through that container to list off all the Pieces of Clothing. Same thing if I hand you a Tag, or a Clothing Type. You may want to think about how your program will store all the Clothing Types that will show up in your database (and why aren't we doing this in SQL anyway), but that's a completely separate question from figuring out what a Clothing Type, itself, actually is.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Well, I just have a couple of things to say about this:

    In the end I want to be able to know other Pieces of Clothing with the same Tag, in the same Outfit and of the same type.
    All of these things are features of clothing which you could compare in instances to see if they are same or different.

    with only one copy of the each object so I could edit it after creation.
    I don't see a point in that. Most C++ objects are mutable anyway. If you are managing several outfits, then you would want to use separate instances of clothing anyway.

  10. #10
    Registered User nathandelane's Avatar
    Join Date
    Dec 2010
    Posts
    9

    Smile

    It seems like you're off to a great start in creating this program. In your last post (the last one I read anyway, #7) you said some things that could be important when you are thinking about object-oriented design. Take these as your formal requirements. Here they are again:

    1. Other Pieces of Clothing with the same Tag.
    2. In the same Outfit.
    3. And of the same type.

    So you have Pieces of Clothing, Tags, Outfits, and Pieces of Clothing can be combined into Outfits. I think of Outfits as a collection of specific pieces of clothing, for example a hat, a belt, a bottom, a top, and a pair of shoes (just for example). These are all pieces of clothing. Maybe I'm totally wrong about this, so let me know if I am, but I'm just spinning the wheels in my head for a minute.

    Outfit (structure or class)
    - IHat: hat
    - IBelt: belt
    - IBottom: bottom
    - ITop: top
    - IShoes: shoes

    The I before each of the clothing items represents an interface. Interface could mean base class, interface, virtual class, abstract class, etc. It's just what all objects of a similar type have in common. I would define another interface as well, IPieceOfClothing or something similar that would represent all of the components that hats, belts, bottoms, and tops have in common, such as a pattern, color, or size:

    IPieceOfClothing
    - string: patternOrColor
    - string: size
    - string: material

    So the interfaces IHat, IBelt, IBottom, and ITop would inherit from or extend the functionality of IPieceOfClothing:

    IPieceOfClothing: IHat
    IPieceOfClothing: IBelt
    IPieceOfClothing: IBottom
    IPieceOfClothing: ITop
    IPieceOfClothing: IShoes

    But each of these piece of clothing types might have their own properties. Here's an example:

    IHat
    - string: styleOrType

    IBelt
    - int: widthInCentimeters
    - int: relativeLength

    IBottom
    - string: length
    - bool: isFormal

    ITop
    - string: style
    - bool: isFormal

    IShoes
    - string: style
    - bool: isFormal

    These are just some ideas. I'm not certain what you want to use the Tags for. So maybe you can explain that some more.
    Last edited by nathandelane; 12-30-2010 at 05:35 PM.

  11. #11
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    @tabstop I'm sorry, I'm not understanding how I can do this without having multiple copies of the same Piece of Clothing

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by kotoko View Post
    @tabstop I'm sorry, I'm not understanding how I can do this without having multiple copies of the same Piece of Clothing
    Well, that's ... well ... I don't know. There is never a point at which you need two copies of the same Piece of Clothing. I can't even come up a circumstance in which you might think you need two Pieces of Clothing, assuming we're storing pointers in all of our tables.

  13. #13
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    So I think there is one important goal of the architecture that I not explaining right: I really don't want to duplicate the instances of the same Piece of Clothing. This is to make suggestions based on the connection between objects.

    @nathandelane the tags are for stuff like formal, fat, summer. For when you want to be using this Piece of Clothing or Outfit (each get their own tags).

    Also a Tag is a bit more than a string, it really needs to know what Pieces of Clothing and/or Outfits it is associated with.

    Knowing this, do smart pointers make more sense? (Yes a database makes even more but I want to put that aside for now)

  14. #14
    Registered User
    Join Date
    Apr 2008
    Posts
    101
    @tabstop I think we might be having what we call in Portuguese a deaf men conversation. What I'm saying is I do not want to duplicate. What I understand from your suggestion is that I will have to duplicate. What I'm asking is is this really what you are suggesting (to have duplicate).

  15. #15
    Registered User nathandelane's Avatar
    Join Date
    Dec 2010
    Posts
    9

    Smile

    Quote Originally Posted by tabstop View Post
    Well, that's ... well ... I don't know. There is never a point at which you need two copies of the same Piece of Clothing. I can't even come up a circumstance in which you might think you need two Pieces of Clothing, assuming we're storing pointers in all of our tables.
    @kotoko

    I think if you have a vector of IPieceOfClothing objects, then that can be where they live, and the outfits can "borrow" those objects by pointing to them, hence pointers.

    For example (Not actual C++ code, and probably a specialized collection using multiple vectors would help a little more):

    Code:
    vector<* IPieceOfClothing> piecesOfClothing = 
    {
    	IHat fedora(name: "Fedora", patternOrColor: "Brown"),
    	ITop redShirt(name: "Red Shirt", patternOrColor: "Red Plaid"),
    	IShoes grayTennisShoes(name: "Gray Tennis Shoes", style: "Tennis Shoes", isFormal: false, patternOrColor: "Gray"),
    	IBottom tanShorts(name: "Tan Shorts", patternOrColor: "Tan")
    }
    From this I can create one Outfit:

    Code:
    Outfit notSoCoolOutfit
    {
    	IHat: * fedora,
    	IBelt: * NULL,
    	ITop: * redShirt,
    	IShoes: * grayTennisShoes,
    	IBottom: * tanShorts
    }
    In the Outfit notSoCoolOutfit I only point to the items in the piecesOfClothing vector. I don't actually have copies.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Packet Container Class
    By ChaoticXSinZ in forum C++ Programming
    Replies: 2
    Last Post: 11-01-2010, 12:07 AM
  2. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  3. HUGE fps jump
    By DavidP in forum Game Programming
    Replies: 23
    Last Post: 07-01-2004, 10:36 AM
  4. C diamonds and perls :°)
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 05-16-2003, 10:19 PM
  5. Dynamic Data Structure -- Which one is better?
    By Yin in forum C++ Programming
    Replies: 0
    Last Post: 04-10-2002, 11:38 PM