C++

Forum

 
templates+linked list+polymorphism

aasaa (30)
HI, Please help.
the Code is Not easy to understand for beginners so here it is.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
// my main
#include <iostream>
#include "LinkedList.txx"

class A 
{
public:
	virtual void print(std::ostream& os) const =0;
};

std::ostream& operator << (std::ostream& os, const A* a)
{
	a->print(os);
	return os;
}
class B : public A
{
	virtual void print(std::ostream& os) const
	{
		os << "B print";
	}
};

class C : public A 
{
	virtual void print(std::ostream& os) const
	{
		os << "C print";
	}
};

int main() 
{
	B b1,b2;
	C c1,c2;
//	std::cout << ((A*)(&c1));
	LinkedList<A*> list;
	list.insert(&b1);
	list.insert(&c1);
	list.insert(&c2);
	list.insert(&b2);
	std::cout << list << std::endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
//file ListNode.txx

#ifndef _LISTNODE_H
#define _LISTNODE_H
template <class T>
class ListNode
{
public:
	T *_data;
	ListNode *_next; // “ ListNode<T> *_next “ is also correct
	ListNode(T *data, ListNode* next) 
	: _data(data), _next(next) {}
};


#endif 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
//file LinkedList.txx

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <iostream>
#include "ListNode.txx"

using namespace std;




template <class T>
class LinkedList;

template <class T> // *template function*
ostream& operator <<(ostream& os, const LinkedList<T>& list);


template <class T>
class LinkedList
{
private:
	ListNode<T>* _head; // the '<T>' is needed here
public:
	LinkedList() : _head(NULL) {}
	void insert(T& data);
	//void print (ostream&) const;
	friend ostream& operator << <>(ostream& os, const LinkedList<T>& list);
	
	
};


template <class T> // *template function*
ostream& operator <<(ostream& os, const LinkedList<T>& list)
{
	ListNode<T> *tmp = list._head;
	while(tmp != NULL)
	{
		os << " -> ";
		os<<*(tmp->_data);
		tmp = tmp->_next;
	}
	return os;
}

template <class T>
void LinkedList<T>::insert(T& data)
{
	_head = new ListNode<T>(&data,_head);
}
#endif


when I compile using g++ the error shown is:
1
2
3
4
5
6
7
8
9
10
 
g++ app.cpp -o app
app.cpp: In function ‘int main()’:
app.cpp:37: error: no matching function for call to ‘LinkedList<A*>::insert(B*)’
LinkedList.txx:50: note: candidates are: void LinkedList<T>::insert(T&) [with T = A*]
app.cpp:38: error: no matching function for call to ‘LinkedList<A*>::insert(C*)’
LinkedList.txx:50: note: candidates are: void LinkedList<T>::insert(T&) [with T = A*]
app.cpp:39: error: no matching function for call to ‘LinkedList<A*>::insert(C*)’
LinkedList.txx:50: note: candidates are: void LinkedList<T>::insert(T&) [with T = A*]
app.cpp:40: error: no matching function for call to ‘LinkedList<A*>::insert(B*)’
LinkedList.txx:50: note: candidates are: void LinkedList<T>::insert(T&) [with T = A*]


where is the problem?
guestgulkan (2942)
void insert(T& data);

1
2
3
4
5
 
template <class T>
void LinkedList<T>::insert(T& data)
{
	_head = new ListNode<T>(&data,_head);
}


I think it is due to the fact that the insert function is expecting a reference.
So if T is A* then the function is expecting A*& (reference to a pointer to class A).

The compiler will inplicitly convert a derived class pointer) to a base class pointer
but it wont convert a derived class pointer to a reference to a base class pointer.

base class*& = derived class* ; //Error

So try this instead:
void insert(T data); //no longer a reference 

1
2
3
4
5
 
template <class T>
void LinkedList<T>::insert(T data)
{
	_head = new ListNode<T>(&data,_head); //EDIT - see comment below.
}


EDIT:
Although now I think about it - you may have to make a specialization for when T is a pointer.

Last edited on
aasaa (30)
Still not solved.
I sent the address of objects 
1
2
3
4
 
list.insert(&b1);
	list.insert(&c1);
	list.insert(&c2);
	list.insert(&b2);
and received the address of the same objects so the 'default' Copy constructor will not be called. and there is nothing wrong with that. thats because of the receiving function is void LinkedList<T>::insert(T& data) .
in other worlds I send: 
1
2
3
 
an object of type B which inherit from the interface A and the received func is 
void LinkedList<A*>::insert(A*& data) //my data type is A* because A is interface  and I can't allocate it

but the compiler still showing that errors above !!
Gaminic (1621)
Don't confuse "pass by reference" and "pass the address". In fact, "pass the address" would take a pointer (int*), not a reference (int&).

Here's how you pass by reference:
1
2
3
4
5
 
void doubleNumber(int &x) { // "Pass by reference"
  x *= 2;
}
int y = 5;
doubleNumber(y); // Pass variable, not address.


[edit]
And there's no point to "A*&", except that it looks awesome.
Last edited on
aasaa (30)
guestgulkan thanks, now it's compile. but I get segmentation fault.
the Linked list DataStructure is double checked AND NOTHING WRONg WITH IT !!


mmm any Ideas?
ne555 (10692)
Show the updated code.
1
2
3
4
5
6
 
template <class T>
void LinkedList<T>::insert(T data)
{
	_head = new ListNode<T>
		(&data,_head); //Taking the address of a temporary
}
aasaa (30)
can you explain why data is temporary?
and do you suggest that I allocate new memory?

thanks Guys and I'm waiting for your replay.
ne555 (10692)
The parameter is pased by copy. At the end of the function that object dies, and you are trying to use its address.

This compiles.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
template <class T>
class ListNode
{
public:
	//T *_data; //¿why a pointer?
	T data;
	ListNode *next; // starting underscore is reserved
	ListNode(const T &data, ListNode* next) 
	: data(data), next(next) {}
};

void LinkedList<T>::insert( const T &data ){
	head = new ListNode<T>(data, head);
}

Last edited on
aasaa (30)
ne555, the problem is when I make the change like this:
1
2
3
 
void LinkedList<T>::insert( const T &data ){ 
	head = new ListNode<T>(data, head);
}

and from main I do :
1
2
3
 
	B b1,b2;
	LinkedList<A*> list;
	list.insert(b1);

whe compiler will show:
1
2
3
 
app.cpp: In function ‘int main()’:
app.cpp:37: error: no matching function for call to ‘LinkedList<A*>::insert(B&)’
LinkedList.txx:52: note: candidates are: void LinkedList<T>::insert(const T&) [with T = A*]


so what I'm suggesting is to send :
list.insert(&b1); // not list.insert(b1) !!
and the inset woult look like that: 
1
2
3
4
5
 
 	void LinkedList<T>::insert(T data) // <T> is A* and without const
{
	_head = new ListNode<T>(&data,_head);
}
 

1
2
3
4
5
 
	T *_data;
	ListNode *_next; 
	ListNode(T *data, ListNode* next) 
	: _data(data), _next(next) {	}

and still segmentation fault !!
Last edited on
ne555 (10692)
1
2
3
4
 
	B b1,b2;
	LinkedList<A*> list; //a container of pointers
//	list.insert(b1); //this would expect a pointer
	list.insert( &b1 );


1
2
3
4
5
 
 	void LinkedList<T>::insert(T data) // T is A*  then &data will be A**
{
//	_head = new ListNode<T>(&data,_head);
	_head = new ListNode<T>(data,_head);
}


Keep in mind that your list doesn't have the ownership of the object that contains.
aasaa (30)
Solved
 !!! here is the update (see my questions below)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
//file ListNode.txx

#ifndef _LISTNODE_H
#define _LISTNODE_H
template <class T>
class ListNode
{
public:
	T *_data;
	ListNode *_next; // “ ListNode<T> *_next “ is also correct
	ListNode(const T &data, ListNode* next) 
	: _next(next) {
		if(data){
			_data = new T(data);
		}
		else
			_data = NULL;
	}
	
	~ListNode(){
		if(_data)
			delete _data;	
	}
};


#endif  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
//file LinkedList.txx

#ifndef _LINKEDLIST_H
#define _LINKEDLIST_H

#include <iostream>
#include "ListNode.txx"

using namespace std;




template <class T>
class LinkedList;

template <class T> // *template function*
ostream& operator <<(ostream& os, const LinkedList<T>& list);


template <class T>
class LinkedList
{
private:
	ListNode<T>* _head; // the '<T>' is needed here
	bool first;
public:
	LinkedList() : _head(NULL),first(true) {}
	void insert(const T &data);
	//void print (ostream&) const;
	friend ostream& operator << <>(ostream& os, const LinkedList<T>& list);
	
	
};


template <class T> // *template function*
ostream& operator <<(ostream& os, const LinkedList<T>& list)
{
	ListNode<T> *tmp = list._head;

	while(tmp != NULL)
	{
		os << " -> ";
		os<<(*(tmp->_data));
		tmp = tmp->_next;
	}
	return os;
}

template <class T>
void LinkedList<T>::insert(const T &data) // const, make sure I'm not changing data
{
	_head = new ListNode<T>(data,_head); // sending data which is A*
}


#endif

the main() is the same as above

my question is:
1. when I send _head = new ListNode<T>(data,_head); // sending data which is A* , and the received function is: ListNode(const T &data, ListNode* next) {...}. there is no copy was made from object data right? and if the received function was ListNode(T data, ListNode* next) {...}. is there any copy that was made??
once I have answers I'll ask another intrinsic question !!
thanks
Last edited on
Topic archived. No new replies allowed.