Archived

This topic is now archived and is closed to further replies.

Setting up a LinkedList using templates

This topic is 5178 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m not to familiar with using templates, but when I wrote this, it compiled properly, but gave me an error when I tried to intialize an instance of the class.
// LinkedList.h: interface for the CLinkedList class.

//

//////////////////////////////////////////////////////////////////////


#if !defined(AFX_LINKEDLIST_H__68DF6B9F_6CE7_4198_8258_1E1F46138676__INCLUDED_)
#define AFX_LINKEDLIST_H__68DF6B9F_6CE7_4198_8258_1E1F46138676__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000



template<class T>
struct Node
{
	Node* prev;
	int ID;
	T* m_Object;
	Node* next;
};

template<class T>
class CLinkedList  
{
public:
	T& operator +=(const CLinkedList<T>* rhs);		//Add Link

	T& operator -=(const CLinkedList<T>* rhs);		//Remove Link

	bool operator ==(const CLinkedList<T>* rhs);				//Check if link exists

	void Add(const CLinkedList<T>* rhs);
	void Del(const CLinkedList<T>* rhs);
	void ClearLinks();											//Clears pointer links to item *warning, may cause memory leaks*

	void DeleteLinks();											//Deletes the allocated memory, and removes the pointers


	T& Find(int m_pfind);
	T& FindID(int m_pfindID);

	CLinkedList();
	virtual ~CLinkedList();

private:
	Node<T>* m_Head;
	Node<T>* m_Tail;
	int* m_LinkNum;

};

#endif // !defined(AFX_LINKEDLIST_H__68DF6B9F_6CE7_4198_8258_1E1F46138676__INCLUDED_)

// LinkedList.cpp: implementation of the CLinkedList class.

//

//////////////////////////////////////////////////////////////////////


#include "LinkedList.h"

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////


template<class T>
CLinkedList<T>::CLinkedList()
{
	m_Head = NULL;
	m_Tail = NULL;
	m_LinkNum =  new int;
	*m_LinkNum = 0;
}

template<class T>
CLinkedList<T>::~CLinkedList()
{

}

template<class T>
T& CLinkedList<T>::operator +=(const CLinkedList<T>* rhs)
{
/*	m_LinkNum++;
	if(!m_Head)
	{
		m_Head = new Node<T>;
		*m_Head->m_Object = rhs;
	}
	else
	{

	}
	*/
	return *this;
}

template<class T>
T& CLinkedList<T>::operator -=(const CLinkedList<T>* rhs)
{
//	m_LinkNum--;

	return *this;
}

template<class T>
bool CLinkedList<T>::operator ==(const CLinkedList<T>* rhs)
{

}

template<class T>
void CLinkedList<T>::Add(const CLinkedList<T>* rhs)
{
//	CLinkedList<T>::operator += rhs

}

template<class T>
void CLinkedList<T>::Del(const CLinkedList<T>* rhs)
{
//	CLinkedList<T>::operator -= rhs

}

template<class T>
T& CLinkedList<T>::Find(int m_pfind)
{

}

template<class T>
T& CLinkedList<T>::FindID(int m_pfindID)
{

}
CLinkedList<int> newlink;
Thats the error it gave: Main.obj : error LNK2001: unresolved external symbol "public: virtual __thiscall CLinkedList::~CLinkedList(void)" (??1?$CLinkedList@H@@UAE@XZ) Main.obj : error LNK2001: unresolved external symbol "public: __thiscall CLinkedList::CLinkedList(void)" (??0?$CLinkedList@H@@QAE@XZ) Anyone know what I''m doing wrong?

Share this post


Link to post
Share on other sites
The most obvious error I see is that you have a cpp file. The thing with templates is that it needs the entire implementation in the h file.
I''m not sure if all compliers need templates this way, but my .NET does. So I would first try moving everything in the cpp over to the h.
I''ve written two templated LL classes and it looks like you can either copy all the cpp undernearth the class definition or within the class itself similar to how you would write an inline function. HTH a little atleast.

Share this post


Link to post
Share on other sites
AFAIK, the standard allows for implementation of templated functions to be in a seperate source file, but unfortunately there are almost no compilers that support it, especially not VC++.

Share this post


Link to post
Share on other sites
Is there something that std::list doesn''t provide that you need? Or is this for educational purposes?

--
Dave Mikesell
d.mikesell@computer.org
http://davemikesell.com

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
actually VC++ does support this functionality but you need to do this:

//top of .h file

#define my_file_h
//bottom of .h file

#ifndef my_file_cpp
#include "my_file_cpp"
#endif

//top of .cpp file

#define my_file_cpp
#ifndef my_file_h
#include "my_file_h"
#endif

Share this post


Link to post
Share on other sites
quote:
Original post by sbennett
AFAIK, the standard allows for implementation of templated functions to be in a seperate source file, but unfortunately there are almost no compilers that support it, especially not VC++.



Sorry, but you are mistaken, I have written my own templated linked list function, and the implementation is in the .cpp file and the declaration in a .h file. I don''t know why you''re making the destructor virtual, since you most likely won''t be inheriting this. Also, the reason I chose to write my own, was because I needed the list to do a few things that the stl doesn''t do.



//Header file


template <class T> struct GenericList_S
{
T Cur;
GenericList_S *Next;
GenericList_S *Prev;
};

template <class T> class GenericList_C
{
public:
GenericList_S<T> *First;
GenericList_S<T> *Cur;
public:
GenericList_C(void);
T Add(T ToAdd);
T AddBefore(T ToAdd, T AddBefore);

MyInline T GetFirst(void);
MyInline T GetNext(void);
MyInline T GetPrev(void);

void Remove(T ptr);

~GenericList_C(void);
};



//Source file

/***** Our Generic List Class *****/
template <class T>
GenericList_C<T>::GenericList_C(void)
{
First = 0; //Set us to null

Cur = 0;
}

template <class T>
MyInline T GenericList_C<T>::GetFirst(void)
{
if (First)
{
Cur = First;
return First->Cur;
}
return 0;
}

template <class T>
MyInline T GenericList_C<T>::GetNext(void)
{
if (First && Cur->Next!=First)
{
Cur = Cur->Next;
return Cur->Cur;
}
Cur=0;
return 0;
}

template <class T>
MyInline T GenericList_C<T>::GetPrev(void)
{
if (First && Cur->Prev!=First)
{
Cur = Cur->Prev;
return Cur->Cur;
}
Cur = 0;
return 0;
}

template <class T>
T GenericList_C<T>::Add(T ToAdd)
{
GenericList_S<T> *tmp = new GenericList_S<T>;
tmp->Cur = ToAdd;
if (!First) //Nothing in list yet?

{
First = tmp;
First->Next = First;
First->Prev = First;
}
else //We have a list already, lets add it to the end!

{
tmp->Next = First;
tmp->Prev = First->Prev;
First->Prev = tmp;
tmp->Prev->Next = tmp;
}
return tmp->Cur;
}

template <class T>
T GenericList_C<T>::AddBefore(T ToAdd, T AddBefore)
{
GenericList_S<T> *adder = new GenericList_S<T>;
adder->Cur = ToAdd;

if (First)
{
GenericList_S<T> *tmp = First;
do
{
if (tmp->Cur==AddBefore)
{
//This is our guy!

adder->Next = tmp;
adder->Prev = tmp->Prev;
adder->Prev->Next = adder;
adder->Next->Prev = adder;
if (First==tmp) //Ahh crap, it was our first in list, lets set us to first now!

First = adder;
return adder->Cur;
}
tmp = tmp->Next;
} while (tmp!=First);
}

return Add(ToAdd);;
}

template <class T>
void GenericList_C<T>::Remove(T ptr)
{
if (First->Cur==ptr) //Our first?

{
if (First==First->Next) //Only one in the list!

{
delete First; //Only responsible to delete the list, not the stuff in the list!

First = 0;
Cur = 0;
}
else
{
GenericList_S<T> *tmp = First;
First->Next->Prev = First->Prev;
First->Prev->Next = First->Next;
First = First->Next;
Cur = First;
delete tmp;
}
}
else //Not our first one!

{
GenericList_S<T> *tmp = First->Next;
while (tmp!=First)
{
if (tmp->Cur == ptr) //This our guy?

{
tmp->Next->Prev = tmp->Prev;
tmp->Prev->Next = tmp->Next;
Cur = tmp->Next;
delete tmp; //Delete our guy

return; //Ok, lets bail, we removed him

}
}
}
}

template <class T>
GenericList_C<T>::~GenericList_C(void)
{
while (First)
Remove(First->Cur);
}
/***** End of Our Generic List Class *****/

Share this post


Link to post
Share on other sites
Here''s another question.

template<class T>
T& CLinkedList<T>::FindID(int m_pfindID)
{
m_Current = m_Head;
while(m_Current)
{
if(m_Current->ID == m_pfindID)
return *m_Current->m_Object;

m_Current = m_Current->next;
}
return *m_Current->m_Object;

}


How do I get this to return a null value if the search doesn''t find the specified int?

Share this post


Link to post
Share on other sites
quote:
Original post by Ready4Dis


Sorry, but you are mistaken, I have written my own templated linked list function, and the implementation is in the .cpp file and the declaration in a .h file.


Well, the following doesn't compile on VC++:

foo.h:

template <class T>
class foo
{
public:
void print(const T& x);
};


foo.cpp:

#include <iostream>
#include "foo.h"

template <class T>
void foo<T>::print(const T& x)
{
std::cout << x;
}


main.cpp:

#include "foo.h"

int main()
{
foo<int> bar;

bar.print(5);

return 0;
}


I get the following output:

--------------------Configuration: Foo - Win32 Release--------------------
Linking...
main.obj : error LNK2001: unresolved external symbol "public: void __thiscall foo<int>::print(int const &)" (?print@?$foo@H@@QAEXABH@Z)
Release/Foo.exe : fatal error LNK1120: 1 unresolved externals
Error executing link.exe.

Foo.exe - 2 error(s), 0 warning(s)


It seems that having a templated class implemented in a seperate cpp file doesn't work?

[edited by - sbennett on October 14, 2003 5:44:02 PM]

Hmm...it seems that editing posts screws up source tags...

[edited by - sbennett on October 14, 2003 5:46:05 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by PumpkinPieman
Here''s another question.

template<class T>
T& CLinkedList<T>::FindID(int m_pfindID)
{
m_Current = m_Head;
while(m_Current)
{
if(m_Current->ID == m_pfindID)
return *m_Current->m_Object;

m_Current = m_Current->next;
}
return *m_Current->m_Object;

}


How do I get this to return a null value if the search doesn''t find the specified int?


I think either just change the return type to a T* or I think there is an something in STL (Cref?) that lets you return a null reference. Otherwise you can''t normally return a null reference, only a null pointer.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

template<class T>
*T CLinkedList<T>::FindID(int m_pfindID)
{ m_Current = m_Head;
while(m_Current->next != NULL)
{
if(m_Current->ID == m_pfindID)
return *m_Current->m_Object;
m_Current = m_Current->next;
}
return(NULL);
}

Share this post


Link to post
Share on other sites