C++

Forum

 
Linked list using templates issue

GaiusBaltar (68)
I decided to make a linked list program using classes and templates.
I implemented my linked list and added some basic functions, everything worked just fine. Then I proceeded to add templates...

First, the error list:

1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::addNode(int)" (?addNode@?$List@H@@QAEXH@Z) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::removeAll(void)" (?removeAll@?$List@H@@QAEXXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: int __thiscall List<int>::length(void)" (?length@?$List@H@@QAEHXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::displayList(void)" (?displayList@?$List@H@@QAEXXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: class Node<int> & __thiscall List<int>::getNodeAt(int)" (?getNodeAt@?$List@H@@QAEAAV?$Node@H@@H@Z) referenced in function "public: class Node<int> & __thiscall List<int>::operator[](int const &)" (??A?$List@H@@QAEAAV?$Node@H@@ABH@Z)
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::moveNode(int,int)" (?moveNode@?$List@H@@QAEXHH@Z) referenced in function _main
1>C:\Users\...\Console\Advanced Linked Lists\Debug\Advanced Linked Lists.exe : fatal error LNK1120: 6 unresolved externals
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========


I have no idea what is going on with my program.
All I know is that something is wrong with the templates in "List.cpp", because everything worked before I added them to that file.

Following: Node.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#pragma once

template<class T>
class Node
{
private:
	Node* next;
	T data;
public:
	Node(int val) :data(val), next(0){}
	Node() :data(0), next(0){}
	int getData(){ return data; }
	void setData(T value){ data = value; }
	Node* getNext(){ return next; }
	void setNext(Node* node){ next = node; }

	~Node(){ /* No need */ }
};


Following: List.h

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
 
#pragma once

#include "Node.h"

template<class T>
class List
{
private:
	typedef Node<T>* _NewNode;
	_NewNode head = NULL;
	_NewNode tail = NULL;
public:
	void addNode(T val);
	void addNode();
	void remove(T val);
	void removeAt(int index);
	void removeAll();
	void editNode(int index, T val);
	int length();
	void displayList();
	void displayNode(T val);
	void displayNodeAt(int index);
	Node<T>& getNodeAt(int index);
	void moveNode(int index1, int index2);
	void sortList();

	Node<T>& operator[] (const int &i){
		return getNodeAt(i);
	}
};


Following: List.cpp

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
 
#include "stdafx.h"
#include <iostream>
#include "List.h"
#include <list>


template<class T>
void List<T>::addNode(T val){
	if (head == 0){
		head = new Node<T>(val);
		tail = head;
	}
	else{
		tail->setNext(new Node<T>(val));
		tail = tail->getNext();
	}
}

template<class T>
void List<T>::addNode(){
	if (head == 0){
		head = new Node<T>();
		tail = head;
	}
	else{
		tail->setNext(new Node<T>());
		tail = tail->getNext();
	}
}

template<class T>
void List<T>::remove(T val){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		List::_NewNode tmp = head;
		while (cur->getData() != val){
			tmp = cur;
			cur = cur->getNext();
		}
		if (cur == 0)
			std::cout << "Item doesn't exist.\n";
		else if (cur == head){
			head = head->getNext();
			delete cur;
			std::cout << "Head was deleted.\n";
		}
		else{
			tmp->setNext(cur->getNext());
			delete cur;
			std::cout << "Selected item was deleted.\n";
		}
	}
}

template<class T>
void List<T>::removeAt(int index){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		List::_NewNode tmp = head;
		int i = 0;
		while (i < index && cur != 0){
			tmp = cur;
			cur = cur->getNext();
			i++;
		}
		if (cur == 0 || i < index)
			std::cout << "Item doesn't exist.\n";
		else if (cur == head){
			head = head->getNext();
			delete cur;
			std::cout << "Head was deleted.\n";
		}
		else{
			tmp->setNext(cur->getNext());
			delete cur;
			std::cout << "Selected item was deleted.\n";
		}
	}
}

template<class T>
void List<T>::removeAll(){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		while (head->getNext() != 0){
			cur = head->getNext();
			head->setNext(cur->getNext());
			delete cur;
		}
		delete head;
		head = 0;
		std::cout << "List has been emptied.\n";
	}
}

template<class T>
void List<T>::editNode(int index, T val){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		int i = 0;
		while (i < index && cur != 0){
			cur = cur->getNext();
			i++;
		}
		if (cur == 0 || i < index)
			std::cout << "Item doesn't exist.\n";
		else{
			cur->setData(val);
			std::cout << "Value has been changed.\n" << index + 1 << ". item: getData(): " << cur->getData() << "\n";
		}
	}
}

template<class T>
int List<T>::length(){
	if (head == 0)
		return 0;
	else{
		List::_NewNode cur = head;
		int i = 0;
		while (cur != 0){
			cur = cur->getNext();
			i++;
		}
		return i;
	}
}

template<class T>
void List<T>::displayList(){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		int i = 0;
		while (cur != 0){
			std::cout << i+1 << ". Item: getData(): " << cur->getData() << '\n';
			cur = cur->getNext();
			i++;
		}
		std::cout << i << " items in list.\n";
	}
}

template<class T>
void List<T>::displayNode(T val){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		int i = 1;
		while (cur->getData() != val){
			cur = cur->getNext();
			i++;
		}
		if (cur == 0)
			std::cout << "Item doesn't exist.\n";
		else{
			std::cout << i << ". item: getData(): " << cur->getData() << '\n';
		}
	}
}

template<class T>
void List<T>::displayNodeAt(int index){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode cur = head;
		int i = 0;
		while (i < index && cur->getNext() != 0){
			cur = cur->getNext();
			i++;
		}
		if (cur == 0 || i < index)
			std::cout << "Item doesn't exist.\n";
		else{
			std::cout << index + 1 << ". item: getData(): " << cur->getData() << "\n";
		}
	}
}

template<class T>
Node<T>& List<T>::getNodeAt(int index){
	if (head == 0)
		return *head;
	List::_NewNode cur = head;
	int i = 0;
	while (i < index && cur->getNext() != 0){
		cur = cur->getNext();
		i++;
	}
	if (cur == 0 || i < index){
		return *head;
	}
	else{
		return *cur;
	}
}

template<class T>
void List<T>::moveNode(int index1, int index2){
	if (head == 0)
		std::cout << "List is empty.\n";
	else{
		List::_NewNode tmp = head;
		List::_NewNode cur = head;
		int i = 0;
		while (i < index1 && cur != 0){ // Search for first index and store it's location
			tmp = cur;
			cur = cur->getNext();
			i++;
		}
		if (cur == 0 || i < index1){ // Check if item exists
			std::cout << "First item doesn't exist.\n";
			return;
		}
		List::_NewNode tmp2 = head;
		List::_NewNode cur2 = head;
		i = 0; // Reset i
		while (i < index2 && cur2->getNext() != 0){ // Same for second index just that we have to make sure we aren't assigning to nothing
			tmp2 = cur2;
			cur2 = cur2->getNext();
			i++;
		}
		if (cur == tail) // Check if cur was last item and set last item to tmp if true
			tail = tmp;
		if (cur2 == 0 || i < index2){ // Check if item exists
			std::cout << "Second item doesn't exist.\n";
			return;
		}
		else if (cur == tmp){ // Move item
			head = cur->getNext();
			cur->setNext(cur2);
			tmp2->setNext(cur);
		}
		else if (cur2 == tmp2){
			tmp->setNext(cur->getNext());
			cur->setNext(cur2);
			head = cur;
		}
		else{
			tmp->setNext(cur->getNext());
			cur->setNext(cur2);
			tmp2->setNext(cur);
		}
		std::cout << "Moving complete.\n";
	}
}

template<class T>
void List<T>::sortList(){
	// TODO
}


To sum up: Something's wrong with the templates that I used in "List.cpp" and I have no idea what it could be.
GaiusBaltar (68)
Error list:

1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::addNode(int)" (?addNode@?$List@H@@QAEXH@Z) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::removeAll(void)" (?removeAll@?$List@H@@QAEXXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: int __thiscall List<int>::length(void)" (?length@?$List@H@@QAEHXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::displayList(void)" (?displayList@?$List@H@@QAEXXZ) referenced in function _main
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: class Node<int> & __thiscall List<int>::getNodeAt(int)" (?getNodeAt@?$List@H@@QAEAAV?$Node@H@@H@Z) referenced in function "public: class Node<int> & __thiscall List<int>::operator[](int const &)" (??A?$List@H@@QAEAAV?$Node@H@@ABH@Z)
1>Advanced Linked Lists.obj : error LNK2019: unresolved external symbol "public: void __thiscall List<int>::moveNode(int,int)" (?moveNode@?$List@H@@QAEXHH@Z) referenced in function _main
1>C:\Users\...\Console\Advanced Linked Lists\Debug\Advanced Linked Lists.exe : fatal error LNK1120: 6 unresolved externals
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
MiiNiPaa (8886)
All templated function should go into header file. You cannot place it in cpp file.
GaiusBaltar (68)
Great, it worked, thanks.
Would you mind explaining why they have to go into the header file?
MiiNiPaa (8886)
Ok, first about waht include does: it just copy-pastes everything from header file to the place where include is.

Second: about separate compilation.
Only cpp fileas are compiled, and each compiled file has no slightest idea about other files which are probably compiled too. If compiler finds used function/class definition in current cpp file, it uses it.
If it can not find definition, but finds a declaration (a promise that this finction/class will be defined in other files) it leaves a note to the linker to find that in another files during linkng.

And finally on templates.
Templates are not magic thing accepting all types. It is as name suggests: a template for generating different function/classes. It tells compiler: "if you want an instance with type T = int, copy that template and replace all T's with int". That means if you use templated function with int and then double, compiler will generate two functions: one for int and one for double.
That also means that if function/class is not used, it won't be generated. You never use .erase() method in vector? Code for it will never be actually generated.
When you have bunch of templates in cpp file and no code using them in that file, nothing is generated.
But. In your header file you have a class definition. Which you use. And inside it you have member function declarations. And you use them. You use promises that they would be found elsewhere. But file actually containing templates for definition does not know what needs to be created and if it needs created at all. So linker searches for function definitions, does not finds them and gives you an error.
If you look into standard headers, you will find out that any templated class is fully defined inside that header.
Last edited on
GaiusBaltar (68)
Thanks for that.
Topic archived. No new replies allowed.