[C++] Template Linked List Problem - Possible Runtime Polymorphism

Phyre

Phyre

Phyre

Associate
Joined
3 Dec 2006
Posts
594
Right now, I'm learning data structures and specifically linked lists right now along with templates. I'm in a bit of a "pickle" right now though... I have a few structs that I want to store in the linked list. There's the base struct and a few derived structs.

Is there anyway to create a linked list template that can hold all of these? I've tried by declaring the list with the name of the base struct but when I try and use values from the derived classes it gives me an error saying those values aren't members of <base class>. Where am I going wrong? Is this not possible?

I've looked at run-time polymorphism and I'm guessing that's what's going on here. I have a few values in base struct, with some additional values in the derived struct. When I try and load the derived struct into the list, it claims "derivedVariable not member of BaseClass"...

This is how I'm setting everything out currently:

I was declaring the linked list in a totally different class as:

Code: 
LinkedList<Base> list;

And in one of the member functions of this new class I create an object of one of the derived classes by:

Code: 
Derived* derived= new Derived();

In my linked list class I add a new Node by using one of its member functions, add(dataType data*). Does that look good?

Then back to the member function where I create a pointer of the derived object, to add it to the list, I use:

Code: 
list.add(derived);

I've tried making that initial LinkedList object creation with a pointer, but that stops the add() function from working (gives me an error, saying the data needs to be part of a class, struct etc)...

Any thoughts? Thanks.
 
The list's template type (value_type in STL parlance) needs to be Base* not Base for the polymorphism to work:

PHP: 
struct Base { virtual int foo() { return 1; } };
struct Derived : public Base { int foo() { return 4; } };
LinkedList<Base*> AList;
Derived *D = new Derived ( );
AList.add (D); //Derived* -> Base* is OK.
 
Sorry, should've mentioned that I tried that... But when it comes to adding it to the list, I get an error:

error C2664: 'LinkedList<dataType>::add' : cannot convert parameter 1 from 'Base*' to 'Base**'
Click to expand...

Because my add() function takes the parameter as a pointer already. I've tried using something like

Code: 
list.add(&Derived)

but that then gives me an error saying...

error C2664: 'LinkedList<dataType>::add' : cannot convert parameter 1 from 'Derived**__w64 ' to 'Base** '
Click to expand...
 
add ( ) should take its argument as a reference to const dataType:

add (const dataType &ToAdd) { ... }

The problem you've encountered is that a pointer to a pointer to a Derived is not a pointer to a pointer to a Base. It's a good thing, because if that were allowed, it'd be easier to do silly things like have a pointer to a Derived class (D1 say) point to an object of a different Derived class (D2), by abusing the address of operator.
 
Ok, I think I understand that... I now, however, have the problem of re-arranging everything in my LinkedList and Node classes because most of the functions were using pointers...
 
Ok... Still having problems... I've debugged my program and I'm still getting the same basic problem as before, where the derived variables aren't being added to the list. I've debugged it and when the add(const dataType &data) function is called the only values that show up in the debugger are the Base values... I'm declaring the list as LinkedList<Base*> list; now so there's nothing wrong there. I'm declaring a pointer with Derived *derived= new Derived(); so nothing wrong there... Then I'm asking the user to input values, which goes through fine. It's just the transition from the add() function call... Unless I'm missing something?
 
Hmm.. Which code do you want?

My add() function:

Code: 
template<class dataType> 
void LinkedList<dataType>::add(const dataType &data)
{
	Node<dataType> *newNodePtr = new Node<dataType>;

	newNodePtr->setData(data);

	if(begin == NULL)
	{
		begin = newNodePtr;
	}
	else
	{
		newNodePtr->setPrevNode(end);
		end->setNextNode(newNodePtr);
	}

	end = newNodePtr;
	current = newNodePtr;
}

Anything else? I appreciate the help, azteched, thanks.
 
Looks ok..

If you want a derived pointer back from the list (assuming you have a back ( ) function that returns the last item, type dataType), you need to cast, because the list itself only knows about Base:

PHP: 
Base *Retrieved = list.back ( ); //get a base ptr
Derived *RetrievedD = dynamic_cast<Derived*> (list.back ( ));
//dynamic_cast returns 0 if the pointer doesn't actually point to a Derived
 
I'm starting to think that Templates are more trouble than they're worth... I just can't understand why the derived object's variables aren't being added to the list. I've looked at loads of text on run-time polymorphism and they all suggest that if you declare the list as "List<Base*> list;" then make a pointer of a derived class as "Derived *derived = new Derived();", then add the list with the parameter as "const dataType &data" (as you said) it should work... But it doesn't. SO frustrating.
 
Well as far as the list is concerned, it stores values of type Base*, and knows nothing else. If you want to regain Derived pointers from the list, you need to dynamic_cast, as above.

I don't often find the need to cast down to derived from base, because if you have a list of Base*, then you generally want to access them through the Base interface (i.e. you don't care what the concrete type is).

Templates are great things, but you have to know what their limitations are.

If you need a true heterogenous container, you could have something like std::list<boost::any> (see boost libraries at boost.org), then you can stuff in anything you like, but it's not widely useful, because you need to know what type you want to get back to pass to any_cast.
 
I'm confused... When I add my derived object to the list in debug mode, and highlight "data" in the add() function, I see no values that are in the derived class. Are they still being added, despite saying they aren't?

I don't have a "list.back()" function... I tried to set one up by retrieving the "prev" pointer that's part of the Node class, like so:

Code: 
template<class dataType>
Node<dataType>* LinkedList<dataType>::getPrevNode()
{
	return prev;
}

..but it doesn't like that. I get an error saying:

error C2683: 'dynamic_cast' : 'Node<dataType>' is not a polymorphic type

edit: ok apparently I can't use dynamic_cast with classes that don't have any virtual functions. Mine don't btw... If I use static_cast instead I get another error saying that my return type isn't correct.
 
Last edited:
Phyre said:
I'm confused... When I add my derived object to the list in debug mode, and highlight "data" in the add() function, I see no values that are in the derived class. Are they still being added, despite saying they aren't?
Click to expand...

data is a Base*, so it's treated as such. The list doesn't know the object you created is a Derived.

I don't have a "list.back()" function... I tried to set one up by retrieving the "prev" pointer that's part of the Node class, like so:

Code: 
template<class dataType>
Node<dataType>* LinkedList<dataType>::getPrevNode()
{
	return prev;
}

..but it doesn't like that. I get an error saying:

error C2683: 'dynamic_cast' : 'Node<dataType>' is not a polymorphic type

edit: ok apparently I can't use dynamic_cast with classes that don't have any virtual functions. Mine don't btw... If I use static_cast instead I get another error saying that my return type isn't correct.
Click to expand...

I was modelling back() after stl containers, i.e. it returns a reference to dataType:
PHP: 
template<typename dT> struct List
{
...other members

dT& back ( ) {
//I guess in your case you'd do something like
return theLastNode->getData ( );
}
};
 
You must log in or register to reply here.
Back
Top Bottom