Copy Constructors and polymorphic member pointers

[chpicker]

How do you write a copy constructor for a class that contains a member variable which is a pointer to a polymorphic base class? Here's a snapshot of the relevant classes. It's a linked list class:

class node {
public:
	node();
	~node();
};

class headnode:public node {
public:
	headnode() {pNext=new tailnode;}
	headnode(const headnode& rhs);
	~headnode() {delete pNext};
private:
	node* pNext;
};

class datanode:public node {
public:
	datanode(data* theData,node* next):pData(theData),pNext(next) {}
	datanode(const datanode& rhs);
	~datanode() {delete pData; delete pNext;}
private:
	node* pNext;
	data* pData;
};

class tailnode:public node {
public:
	tailnode() {}
	tailnode(const tailnode& rhs);
	~tailnode() {}
};

class LinkedList {
public:
	LinkedList() {pHead=new headnode;}
	LinkedList(const LinkedList& rhs) {pHead=new headnode(*(rhs.pHead));
	~LinkedList() {delete pHead;}
private:
	headnode* pHead;
};

How do I go about coding the copy constructors for headnode and datanode? The Linked List itself is what will be copied in my code when I pass the whole list by value to my function. (Yes, I have to pass it by value. This is very important.)

The LinkedList class creates a new headnode by passing the original. I think I did that right. The headnode's copy constructor then needs to duplicate the pNext node, but it's a node pointer that could be pointing to either a datanode or a tailnode. The datanode class has the same problem. How do you code that? I know it's possible to switch on the runtime type of the pointer, but I don't know how to do it, and I've heard it's a sign of poor class design to resort to that process anyway.

Is there some way to code a copy constructor for the base node class that will take a subclass reference as a parameter and create the right object? That doesn't sound possible to me, as "new node" only allocates enough memory for a node, not a headnode.

What can I do here? How do you code a copy constructor for a class with polymorphic pointers as member variables?

Ian

 

[PerFnurt]

1. Reinventing the wheel might be fun, but C++ already comes with a very generic linked list, std::list. If you're really determined to do it yourself I suggest you use templates instead, there's a lot to win by chosing that.

2. Copying members that are pointers is generally tricky. Who owns the data pointed to? Who shall delete it? Should everyone have their own (new:ed) instance? Then why use a pointer at all?

3. You can't invoke copy constructors of the derived classes if all you "see" is the base class.

> it's a sign of poor class design to resort to that process anyway.

Yeah. And it is cheating.

>Is there some way to code a copy constructor for the base node class that will take a subclass reference

Not really. Besides, that would result in the base class having depandacy to its sub class which is also rather poor design.


/Per
[sub]
www.perfnurt.se[/sub]

 

[chpicker]

Ugh. I was afraid of that.

1. I actually didn't know there was an included class, although to be honest the ones that I've seen confuse me. Take the identifier "std::list"...what's the scope operator in there? What does it do? What does the "std" represent? I've tried to stay away from them for the time being until I learn more.

I am actually using the LinkedList classes described in the book that I learned C++ from. I actually did modify it to be a template, too, because not only do I need lists of more than one class, I actually need a list of lists. Setting the list up as a template made that much easier.

2. I have all of this worked out already. I'm pretty confident on the methods used. My plan was to delegate all object creation to the object that points to it. So, the LinkedList creates a copy of the head, which creates a copy of the item it points to (be it a data member or the tail) and so on until the tail is created, at which point the tail does nothing. The data members will copy both the next member and the data class it's pointing to. (The data class is the template parameter.)

3. I thought that was the case.

I guess I can't do it the way I thought. I'll have to come up with another way. I'll probably have to get at the data cells pointed to by the data nodes and just pass copies of them into the newly created list. I'm not comfortable with that, but it might be the only way. (

By the way, with std::list, are you able to pass an entire list to a function by value? Where can I find information on it? The book I have doesn't mention any of the standard libraries beyond iostream. If std::list can do what I need, as you said...why reinvent the wheel?

Ian

 

[timmay3141]

std is a namespace. Namespaces are not a difficult concept - use Google to look them up.

You can find details of the list class at

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrflistremoveif.asp

 

[PerFnurt]

>I've tried to stay away from them

Oh, but you shouln't, STL (the Standard Template Library - which all resides in the std namespace) is really awesome.

It might look a bit complicated at first but once you've got the hang of it you'll see how clever and nice it really is.

Thanks to it's consistent design, when you've figured out how std::list works, with iterators and all, you've pretty much figured you to work with std::vector, std:set, std::map and the other collections as well.

>By the way, with std::list, are you able to pass an entire list to a function by value?

Not sure what you mean, but the list will have a copy constructor that copies the elements to the other list. Of course this requires the elements to have copy constructors as well.

#include <list>  // Note: no .h

typedef std::list<int> MyIntList;
...
void someFunc(const MyIntList& myIntList)
{
   MyIntList cpy(myIntList);
   // cpy is a list of its own, no sharing of
   // elements with the source list. It will neatly
   // clean up when it goes out of scope.
}

// And a list of lists is trivial:
typedef std::list<std::list<int> > MyListOfIntLists;

There's a whole lot of other goodies in STL, for example std::for_each, which makes it easy to pass every element in a collection to a function. There are functions for sorting, searching, auto pointers and whatnot.

By the way, what is all this "passing by value" about? When it comes to data types beyond the basic ints or doubles I hardly ever pass by value. Pass by const & if its an "in-only" parameter, by & if it's an in/out parameter.


/Per
[sub]
www.perfnurt.se[/sub]

 

[luke13]

In general when you want to copy an object, but only know its base type, add a virtual method that when called, causes an object to copy itself. By convention, this method is called clone().

This is the prototype design pattern. Came up with suprisingly little on this when googling, but this link answers a similar q and should help,

http://www.parashift.com/c++-faq-lite/abcs.html#faq-22.5

 

[chpicker]

Thanks for the input, Per. You're right...I've avoided STL mainly because it looks confusing. Besides, my linked list code mainly came out of the book that I used to learn C++ in the first place. That book is Sams Teach Yourself C++ in 24 Hours by Jesse Liberty. There is a whole chapter devoted to just Linked Lists, and I took that and ran with it. At that point I didn't know anything about STL.

As for passing by value, believe me when I say it's a requirement of this program. In short, I'm writing a recursive function which will take a list, add another item to it, and call itself with the new list. When the function returns, it adds a different item to the list and calls itself again. All of the different possibilities (each possibility is a list) are stored in a list as well, which ends up being a linked list of linked lists. Creating a list template worked better than I expected.

Strangely enough, I ended up partially doing what Luke suggested. I ended up creating a "Copy" method for the data nodes which, when the list's copy constructor is called, passes the new (empty) list to the Copy method. The nodes then individually insert their data into the new list in reverse order. Since the list automatically "sorts" the items as they are inserted, this makes it happen much faster since each new item gets inserted right at the beginning.

I appreciate all of the input, guys. I'll definitely look into using STL for my next project, but since I've got this one doing what I need it to do now I'm going to leave it as is.

Ian