🔒 Locked

Inheritance causing code duplication?

Started by Nairou Mar 20, 2009 at 8:55 PM 11 replies 2k views

Original Post

128

Mar 20, 2009 at 8:55 PM

Okay, so I'm creating a tree class, to use as the basis for other tree-like classes. The tree consists of nothing but nodes, essentially other instances of the tree class, and so a lot of functions take and receive smart pointers to itself. For example:

class tree;
typedef boost::shared_ptr<tree> tree_p;

class tree {
  public:
   // ...
   tree_p parent( void );
   tree_p insertNode( tree_p newNode );
   // ...
  private:
   std::list<tree_p> children;
}

And that works fine. But then I create another class, which inherits from the tree class, such as a bone class for animation. The problem is, all of the member functions for managing the tree within the bone class all input and output tree pointers, not bone pointers. If I want the parent() function to return a bone pointer rather than a tree pointer, I'd have to create a new copy of that function to override the original. So then I'm left wondering whether to keep the tree class around, or if I should just move all of it's functionality directly into the bone class (and into every other class that would otherwise have inherited from the tree class). Except that I thought inheritance was supposed to reduce this sort of code duplication... What am I missing?

Antheus

216

Antheus

Mar 20, 2009 at 9:10 PM

Quote:
Original post by Nairou

Except that I thought inheritance was supposed to reduce this sort of code duplication... What am I missing?

A tree node is a tree node. It can also be a bone.

Bone.parent() may be a bone, but it might be something else, the only guarantee is that it's a tree node.

Once a tree is defined, there exist methods for manipulating it. If abstraction is justified, then the interface defined by tree will apply to all descendants.

For example, to process everything in tree, there might be a virtual update() function. It would do nothing for base tree node, but for bone it would do something useful.

Then iterating the tree involves recursively calling virtual update() function on all children.

The need to know a specific instance, or whether something is of a specific instance is typically a big warning sign about improper abstraction, improper expectations, or improper use.

Usually, there should be no need for descendants of tree node to know exact types of its children or parent. Descendants however know about their own type, and can use that.

Nairou

Author

128

Nairou

Mar 20, 2009 at 9:41 PM

But does that mean, then, that a function calling Bone.parent(), and expecting to receive a Bone pointer, would actually have to cast the resulting tree pointer to get a bone? Or is it transparent enough to allow the pointer to be dropped into a Bone pointer and Just Work? Beyond that, is it still just as transparent when you have it wrapped up in a smart pointer?

swiftcoder

Mod

2,296

swiftcoder

Mar 20, 2009 at 10:05 PM

template <typename Inherit>class tree{	typedef boost::shared_ptr<Inherit> tree_p;		// ...};class Bone : public tree<Bone>{	// ...};

Template magic is a wonderful thing...

Antheus

216

Antheus

Mar 20, 2009 at 10:18 PM

Quote:
Original post by swiftcoder
*** Source Snippet Removed ***
Template magic is a wonderful thing...

What happens when I put tree as a child of tree, assuming Joint and Bone are unrelated?

template <typename Inherit>class tree{	typedef boost::shared_ptr<Inherit> tree_p;        tree_p parent( );        tree_p insertNode( tree_p newNode );        std::list<tree_p> children;};

tree<Bone> root;tree<Joint> child;root.addChild(child); ??child.getParent();    ??

swiftcoder

Mod

2,296

swiftcoder

Mar 21, 2009 at 6:36 AM

Quote:
Original post by Antheus
Quote:
Original post by swiftcoder
*** Source Snippet Removed ***
Template magic is a wonderful thing...
What happens when I put tree as a child of tree, assuming Joint and Bone are unrelated?
tree<Bone> root;tree<Joint> child;root.addChild(child); ??child.getParent(); ??

You don't. A limitation of this approach is that it only supports monomorphic trees.

loufoque

Mar 21, 2009 at 8:05 AM

May I know why you're using shared_ptr?
I don't see any case of shared ownership here.

Nairou

Author

128

Nairou

Mar 21, 2009 at 9:52 AM

I'm using the shared_ptr more for memory management than for shared ownership, though the shared ownership could certainly come into play. Each node in my tree class is just a pointer to another tree, rather than an actual embedded member, which means that I can remove a node from a tree and insert it into another tree (or a different position within the same tree) without recreating anything. I could just use the bare pointers, but then I'd have to keep track of what trees referred to what other trees and which ones should be deleted. shared_ptr handles all of that for me.

Zahlman

257

Zahlman

Mar 21, 2009 at 1:08 PM

Quote:
Original post by Nairou
I'm using the shared_ptr more for memory management than for shared ownership, though the shared ownership could certainly come into play. Each node in my tree class is just a pointer to another tree, rather than an actual embedded member, which means that I can remove a node from a tree and insert it into another tree (or a different position within the same tree) without recreating anything. I could just use the bare pointers, but then I'd have to keep track of what trees referred to what other trees and which ones should be deleted. shared_ptr handles all of that for me.

If the nodes are not polymorphic, then just storing instances would work fine. Otherwise (or if your real fear is that the instances are expensive to copy and will be moved around a lot) you might consider something like mr_edd's value_ptr instead of boost::shared_ptr. There is also boost::ptr_list to consider, although if I'm thinking clearly (I haven't had breakfast yet) it probably won't help you here.

Nairou

Author

128

Nairou

Mar 21, 2009 at 2:34 PM

I'm not familiar with value_ptr, I'll have to look into that. Is there some downside to using boost::shared_ptr in this way? My impression was that it didn't add any overhead except at creation/destruction.

My thinking was that it would be smarter to store them as pointers, as there was little downside to doing so and it allows me to move them around (or unplug them completely) without copying anything.

SiCrane

Mod

473

SiCrane

Mar 21, 2009 at 3:22 PM

Quote:
Original post by Zahlman
If the nodes are not polymorphic, then just storing instances would work fine.

Unfortunately, that's not technically legal.

Zahlman

257

Zahlman

Mar 22, 2009 at 8:18 PM

Quote:
Original post by SiCrane
Quote:
Original post by Zahlman
If the nodes are not polymorphic, then just storing instances would work fine.

Unfortunately, that's not technically legal.

... Wow, that's incredibly unfortunate. :(

NotAYakk

Mar 23, 2009 at 2:52 AM

btw, list is a good idea when you need a fast splice(). Other than that, list isn't an efficient std container.

Having your trees have weak_ptrs to their parent, and the accessors return shared_ptrs to their parent, can sometimes be useful.

If you want polymorphic trees, you can implement:

  template<typename T>  shared_ptr<T> parent();

in the parent class that calls dynamic_cast for you. If your trees are mostly monomorphic, you could maintain a flag that says if the type of the pointer is the same as this object's type, and if so, use static_cast (depending on your compilers implementation of dynamic_cast, this could be much faster)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.