How to represent child parent relationships?
Hi
I'd like to write some software which has child and parent relationships. Each object could have multiple parents ("owned" by the parent) and multiple children ("own" the children).
How exactly should I map these relationships? If a child object (C) has two parent objects (P1 and P2), should C have a reference to P1 and P2? Or, should P1 and P2 each refer to C? Or, should it be both?
Thanks
I'd like to write some software which has child and parent relationships. Each object could have multiple parents ("owned" by the parent) and multiple children ("own" the children).
How exactly should I map these relationships? If a child object (C) has two parent objects (P1 and P2), should C have a reference to P1 and P2? Or, should P1 and P2 each refer to C? Or, should it be both?
Thanks
Hey Roz,
It's difficult to give a correct answer without having more context about how the parent and children will be used. If the children need access to the parent/parent's data, then you should keep track of them. If the parent's need access to the children/children's data for future use, then you should keep track of them. This can be done in a variety of ways -- one example is using 2 vectors to hold the parent's and children of a relationship. So an object can have a member variable "std::vector<object_type> child" and a member variable "std::vector<object type> parent". When you want to add a parent to a certain object, you push the parent onto the object's parent vector (OBJECT_NAME.parent.push_back(PARENT_NAME)). I hope this makes sense? If anyone sees a problem with this please correct me!
It's difficult to give a correct answer without having more context about how the parent and children will be used. If the children need access to the parent/parent's data, then you should keep track of them. If the parent's need access to the children/children's data for future use, then you should keep track of them. This can be done in a variety of ways -- one example is using 2 vectors to hold the parent's and children of a relationship. So an object can have a member variable "std::vector<object_type> child" and a member variable "std::vector<object type> parent". When you want to add a parent to a certain object, you push the parent onto the object's parent vector (OBJECT_NAME.parent.push_back(PARENT_NAME)). I hope this makes sense? If anyone sees a problem with this please correct me!
If you are trying to model shared ownership (i.e., in terms of C++'s idiomatic ownership semantics), then the parents should probably hold a std::shared_ptr to each child.
If you need to link in both directions, care needs to be taken to avoid leaking memory by creating ownership cycles (use std::weak_ptr in one direction). Prefer not to do this, and avoid making the ownership graph too deep.
If you need to link in both directions, care needs to be taken to avoid leaking memory by creating ownership cycles (use std::weak_ptr in one direction). Prefer not to do this, and avoid making the ownership graph too deep.
Last edited on
hi, yes that makes sense
my application will need to determine the children and parents of a given object. i guess that you could link downwards only (i.e. just refer to an object's children) - this means to find a given object's parents you'd have to scan all objects for their children.
linking both ways solves this problem but isn't this recording the same piece of information twice (i.e. recording a parent's children and recording that children's parent is the same information). having done a little database programming, i thought that this was bad practice (im aware this is not db programming but thought it might be relevant)
my application will need to determine the children and parents of a given object. i guess that you could link downwards only (i.e. just refer to an object's children) - this means to find a given object's parents you'd have to scan all objects for their children.
linking both ways solves this problem but isn't this recording the same piece of information twice (i.e. recording a parent's children and recording that children's parent is the same information). having done a little database programming, i thought that this was bad practice (im aware this is not db programming but thought it might be relevant)
I think it's relevant.
But while we prefer not to repeat ourselves, it's not a total ban, especially where the repeated information is implicit.
It's kind of like storing the tail node of a linked list: while the tail node can always be found by walking the list, recording it explicitly has important benefits (e.g., it allows constant-time insertion at the end).
What's really important in those situations is that the invariants are maintained internally - that the tail node always points to the tail, or that the parent and child pointers always remain consistent from the user's perspective. As long as the duplicate information is limited in scope in some way, it's not so bad.
Another alternative is to lift each relationship into a object, à la the GoF's Mediator Pattern, sort of like @colorfulpup's suggestion.
But while we prefer not to repeat ourselves, it's not a total ban, especially where the repeated information is implicit.
It's kind of like storing the tail node of a linked list: while the tail node can always be found by walking the list, recording it explicitly has important benefits (e.g., it allows constant-time insertion at the end).
What's really important in those situations is that the invariants are maintained internally - that the tail node always points to the tail, or that the parent and child pointers always remain consistent from the user's perspective. As long as the duplicate information is limited in scope in some way, it's not so bad.
Another alternative is to lift each relationship into a object, à la the GoF's Mediator Pattern, sort of like @colorfulpup's suggestion.
Last edited on
The children are owned by multiple parents? To me, "ownership" means that when the owner is destroyed, the owned object must be destroyed also. Are you thinking along the same lines? If so then mbozzi is right (as usual) and you should use shared_ptr<> in the parents to point to the children.
It's okay to have a pointer (or some other reference) from the children to the parents. While this is redundant in terms of information, you need it for quick access.
Make sure that when adding a child to a parent, you update BOTH the child and the parent.
Make sure that when you delete an object, you remove it's children AND you remove it from its parents.
It's okay to have a pointer (or some other reference) from the children to the parents. While this is redundant in terms of information, you need it for quick access.
Make sure that when adding a child to a parent, you update BOTH the child and the parent.
Make sure that when you delete an object, you remove it's children AND you remove it from its parents.
hi @dhayden and @mbozzi - thanks this is very helpful
just one more question if you don't mind - suppose that when a child has multiple parents, those parents can have different levels of ownership in the child(e.g. P1 has 15%, P2 has 85%).What would be the best way to represent this?
How about each parent has 2 vectors - a vector holding a pointer to its children and a second vector holding the corresponding ownership % for each child. Should each child have two vectors - one with a point to its parents and one for the percentage owned (or should this information only exist in the parent)?
Hope that makes sense!
just one more question if you don't mind - suppose that when a child has multiple parents, those parents can have different levels of ownership in the child(e.g. P1 has 15%, P2 has 85%).What would be the best way to represent this?
How about each parent has 2 vectors - a vector holding a pointer to its children and a second vector holding the corresponding ownership % for each child. Should each child have two vectors - one with a point to its parents and one for the percentage owned (or should this information only exist in the parent)?
Hope that makes sense!
Rozick1, I think you need to explain the problem in some more detail. I have a feeling that the terms "parent", "child" and "ownership" mean something different in this problem than they normally mean computer science.
For example, a public company with stock holders seems to match your description. Each stockholder owns a portion of the company. But that doesn't mean they are in a parent/child relationship at all.
Details please!
For example, a public company with stock holders seems to match your description. Each stockholder owns a portion of the company. But that doesn't mean they are in a parent/child relationship at all.
Details please!
Topic archived. No new replies allowed.