How to correctly initialize instance of a class that has a template?

[vaderboi]

I am creating my own implementation of a List ADT and I am really confused as to a linker error that I am getting. When I compile with

g++ -std=c++11 problem1.cpp main.cpp -o Problem1

I get this error:

/tmp/cceo20TV.o: In function `main':
main.cpp:(.text+0xdd): undefined reference 
to `List<int>::List(std::vector<int, std::allocator<int> >&)'
main.cpp:(.text+0xf3): undefined reference 
to `List<int>::List(std::vector<int, std::allocator<int> >&)'
collect2: error: ld returned 1 exit status 

I know this probably has something to do with how I called instances of my class due to my confusion regarding how to implement templates. What am I doing wrong here?

Here are my files:

main.cpp

#include "problem1.h"

int main()
{
	std::vector<int> ListP = {1, 3, 4, 6};
	std::vector<int> ListL  = {0, 7, 4, 3, 2, 1, 9};
	std::vector<int> &toPlaceInP = ListP;
	std::vector<int> &toPlaceInL = ListL;

	List<int> P( toPlaceInP );
	List<int> L( toPlaceInL );

	return 0;
} 

problem1.h

#ifndef PROBLEM1_H
#define PROBLEM1_H

#include<iostream>
#include<vector>

template<typename Object>
class List
{
	public:
		
		List();

		//~List();

		List( std::vector<Object> &toPlaceInList );

		void insertAtEnd( Object dataToInsert );

		void printAll();

		void initialize();

	private:
		
		struct Node
		{
			Object data;
			Node *next;
			Node *prev;
		};

		Node *head;
		Node *tail;
};

#endif 

problem1.cpp

#include "problem1.h"

template<typename Object>
List<Object>::List()
{
	initialize();
}

/*List::~List()
{
	//to fill
}*/

template<typename Object>
List<Object>::List( std::vector<Object> &toPlaceInList )
{
	initialize();

	for( int i = 0; i < toPlaceInList.size(); ++i )
	{
		insertAtEnd( toPlaceInList[i] );
	}
}


template<typename Object>
void List<Object>::insertAtEnd( Object dataToInsert )
{
	Node *toInsert = new Node;
	toInsert->data = dataToInsert;

	//Node before tail now points to toInsert
	tail->prev->next = toInsert;
	
	//toInsert now points backwards to Node before it
	toInsert->prev = tail->prev;
	toInsert->next = tail;
	
	//tail now points to toInsert
	tail->prev = toInsert;
}

template<typename Object>
void List<Object>::initialize()
{
	head = new Node;
	tail = new Node;
	
	head->next = tail;
	head->prev = tail;

	tail->next = head;
	tail->prev = head;
}

template<typename Object>
void List<Object>::printAll()
{
	if( head->next == tail )
	{
		std::cout << "Nothing to print" << std::endl;
	}
	else
	{
		Node *printNode = new Node;
		printNode = head->next;

		while( printNode != tail )
		{
			std::cout << "Data: " << printNode->data << std::endl;
			printNode = printNode->next;
		}
	}
}

[Mitsuru]

Your template class, List, is needed to be explicit instantiation in problem1.cpp. If not, List<int> is not instantiated for problem1.o, which means the type is missing in linker stage.

<https://en.cppreference.com/w/cpp/language/class_template#Explicit_instantiation>

Perhaps, you may need a statement such as the below around the bottom line in problem1.cpp.

template class List<int>;

[vaderboi]

But I want it to be instantiated in main.cpp, right? Otherwise, doesn't it destroy the point of having a template?

[Mitsuru]

> But I want it to be instantiated in main.cpp, right?

Member functions (constructor, initialize() etc) are all template function, and compiled in problem1.cpp. Therefore, List<int>::XXX is missing in linker stage.

>Otherwise, doesn't it destroy the point of having a template?

Do you mean such a treatment degrades the usefulness of template as generic programming?
Some library based on template techniques (c.f. boost) implements all (not only declaration, but definition) in the header, which enables generic programming for arbitrary template arguments.

[vaderboi]

So did I make the template a class rather than a typename? Is that part of the issue? Why am I supposed to put template class List<int> at the bottom of my .cpp file? I don't want it to be int. I want it to be able to take whatever data type it is initialized as in main.

[Mitsuru]

template class List<int>;

The above code defines template class "List" is instantiated as List<int>.
If you need other types, you can add instantiated classes like the below

template class List<int>;
template class List<double>;
template class List<std::string>;
// just add the definitions 

If you do not like it, (1) all codes in problem1.cpp and problem1.h should be moved into main.cpp, or (2) write the implementations of problem.cpp in the problem1.h.

[vaderboi]

Oh okay. Do I put those in the problem1.cpp or problem1.h?

[Mitsuru]

Like this as to (2). (Sorry, just copy&pate)

#ifndef PROBLEM1_H
#define PROBLEM1_H

#include<iostream>
#include<vector>

template<typename Object>
class List
{
	public:
		
		List(){
	initialize();

	for( int i = 0; i < toPlaceInList.size(); ++i )
	{
		insertAtEnd( toPlaceInList[i] );
	}
}

		//~List();

		List( std::vector<Object> &toPlaceInList ){
	initialize();

	for( int i = 0; i < toPlaceInList.size(); ++i )
	{
		insertAtEnd( toPlaceInList[i] );
	}
}

		void insertAtEnd( Object dataToInsert ){
	Node *toInsert = new Node;
	toInsert->data = dataToInsert;

	//Node before tail now points to toInsert
	tail->prev->next = toInsert;
	
	//toInsert now points backwards to Node before it
	toInsert->prev = tail->prev;
	toInsert->next = tail;
	
	//tail now points to toInsert
	tail->prev = toInsert;
}

		void printAll(){
	if( head->next == tail )
	{
		std::cout << "Nothing to print" << std::endl;
	}
	else
	{
		Node *printNode = new Node;
		printNode = head->next;

		while( printNode != tail )
		{
			std::cout << "Data: " << printNode->data << std::endl;
			printNode = printNode->next;
		}
	}
}

		void initialize(){
	head = new Node;
	tail = new Node;
	
	head->next = tail;
	head->prev = tail;

	tail->next = head;
	tail->prev = head;
}

	private:
		
		struct Node
		{
			Object data;
			Node *next;
			Node *prev;
		};

		Node *head;
		Node *tail;
};

#endif 

[vaderboi]

I understand I can put definitions in the header file. Where do I place those template declarations if I want a separate .cpp file?

[Mitsuru]

If you want a separated .cpp files, you need explicit instantiation as you confronted in this case.

When declaration & definition is written in the header,
template class is implicitly instantiated without explicit instantiation.

This is some key points in generic programming in C++.

[Mitsuru]

Similar question, and the same answer.
<https://stackoverflow.com/questions/8752837/undefined-reference-to-template-class-constructor>

[vaderboi]

Oh I get it now. So since I am compiling the .cpp file and and .h file separately, the compiler won't know what data type I input when I created an instance of the class?

[Mitsuru]

Precisely speaking, the minimum unit of the compile is each .cpp file. (statements in .h file is just inserted into the .cpp by #include). Thus, main.cpp and problem1.cpp are compiled independently.
You intended to instantiate List<int> in main.cpp, but it is not instantiated in problem1.cpp.
main.cpp does not know definition of List<int>, but it is forwardly declared in problem1.h, so that such a forward declaration tells compiler that "Though now the definition is unknown, it is added in linker stage".
But, it is not defined in other place (problem1.cpp) , which leads to the error "undefined reference of List<int>::XXX" because there is no definition of List<int>::XXX.

It is something confusing, but, it is internally related to compiler procedure in C++.

[vaderboi]

Ah. That makes sense. The linker knows that the member constructors, variables, and functions have been declared but because the .cpp file is compiled separately, it has no idea what the definitions are. Thank you for the help!

[Mitsuru]

You are welcome.
Template techniques are sometimes confusing, please be careful about how to work.