What did I miss? (Templates, Classes, Linking)

[d3v4l1]

Hey guys. I'm stuck with a linked list class I was aiming to make generic after writing it successfully without templates.


So here's my main.cpp file:

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

int main()
{
	// construct 1
	LinkedList<char> *llist1 = new LinkedList<char>();
	llist1->push_front('b');
	llist1->push_back('c');
	llist1->push_front('a');
	llist1->push_back('d');
	llist1->display();
	
	std::cout << "\n\n";
	
	// construct 2
	ListNode<int> *lnode = new ListNode<int>;
	lnode->data = 1;
	lnode->next = NULL;
	
	LinkedList<int> *llist2 = new LinkedList<int>(lnode);
	llist2->push_front(0);
	llist2->push_back(2);
	llist2->display();

}

and using this LinkedList.h file works:

#include <iostream>

template<class T>
struct ListNode
{
	T data;
	ListNode<T> *next;
};
		
template<class T> class LinkedList
{
	public:
		LinkedList()
		{
			this->head = NULL;
		}
		
		LinkedList(ListNode<T> *node)
		{
			this->head = node;
		}
		
		void push_front(T newData)
		{
			ListNode<T> *newNode = new ListNode<T>;
			newNode->data = newData;
			newNode->next = head;
			head = newNode;
		}
			
		void push_back(T newData)
		{
		    ListNode<T> *newNode = new ListNode<T>;
		    newNode->data = newData;
		    ListNode<T> *nodePtr = new ListNode<T>;  // To move through the list
		
		    // If there are no nodes in the list
		    // make newNode the first node.
		    if (!head)
		    {
		        head = newNode;
		        head->next = NULL;
		    }
		    else  // Otherwise, insert newNode at end.
		    {
		        // Initialize nodePtr to head of list.
		        nodePtr = head;
		
		        // Find the last node in the list.
		        while (nodePtr->next)
		        {
		            nodePtr = nodePtr->next;
				}
		
		        // Insert newNode as the last node.
		        nodePtr->next = newNode;
		        newNode->next = NULL;
		    }
		}
		
		void display()
		{
			std::cout << "START\n";
			for(ListNode<T>* p = this->head; p != NULL; p = p->next)
				std::cout << p->data << " ";
			std::cout << "\nEND";
		}

		
	private:
		ListNode<T> *head;
	
};

but not when I separate it like this...

LinkedList.h :

#include <iostream>

template<class T>
struct ListNode
{
	T data;
	ListNode<T> *next;
};
		
template<class T> class LinkedList
{
	public:
		LinkedList<T>();
		LinkedList<T>(ListNode<T>* node);
		
		void push_front(T newData);
		void push_back(T newData);
		void display();
		
	private:
		ListNode<T> *head;
	
};

LinkedList.cpp :

#include "LinkedList.h"

template<class T>
LinkedList<T>::LinkedList()
{
	this->head = NULL;
}

template<class T>
LinkedList<T>::LinkedList(ListNode<T> *node)
{
	this->head = node;
}

template<class T>
void LinkedList<T>::push_front(T newData)
{
	ListNode<T> *newNode = new ListNode<T>;
	newNode->data = newData;
	newNode->next = head;
	head = newNode;
}
	
template<class T>
void LinkedList<T>::push_back(T newData)
{
    ListNode<T> *newNode = new ListNode<T>;
    newNode->data = newData;
    ListNode<T> *nodePtr = new ListNode<T>;  // To move through the list

    // If there are no nodes in the list
    // make newNode the first node.
    if (!head)
    {
        head = newNode;
        head->next = NULL;
    }
    else  // Otherwise, insert newNode at end.
    {
        // Initialize nodePtr to head of list.
        nodePtr = head;

        // Find the last node in the list.
        while (nodePtr->next)
        {
            nodePtr = nodePtr->next;
		}

        // Insert newNode as the last node.
        nodePtr->next = newNode;
        newNode->next = NULL;
    }
}

template<class T>
void LinkedList<T>::display()
{
	std::cout << "START\n";
	for(ListNode<T>* p = this->head; p != NULL; p = p->next)
		std::cout << p->data << " ";
	std::cout << "\nEND";
}

Here's the error I get:

C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x20): undefined reference to `LinkedList<int>::LinkedList()'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x35): undefined reference to `LinkedList<int>::push_front(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x46): undefined reference to `LinkedList<int>::push_back(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x57): undefined reference to `LinkedList<int>::push_front(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x68): undefined reference to `LinkedList<int>::push_back(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0x74): undefined reference to `LinkedList<int>::display()'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0xc7): undefined reference to `LinkedList<int>::LinkedList(ListNode<int>*)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0xdc): undefined reference to `LinkedList<int>::push_front(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0xed): undefined reference to `LinkedList<int>::push_back(int)'
C:\Env\Code\C++\LinkedList\main.o main.cpp:(.text+0xf9): undefined reference to `LinkedList<int>::display()'
c:\dev\$kit\mingw64\x86_64-w64-mingw32\bin\ld.exe main.o: bad reloc address 0x10 in section `.xdata'
C:\Env\Code\C++\LinkedList\collect2.exe [Error] ld returned 1 exit status
25 C:\Env\Code\C++\LinkedList\Makefile.win recipe for target 'LinkedList.exe' failed




So what did I miss?

[ne555]

http://www.cplusplus.com/forum/general/113904/#msg622073


> ListNode<int> *lnode = new ListNode<int>;
¿where did you "learn" that?
http://www.cplusplus.com/forum/general/138037/#msg731921

[d3v4l1]

It wouldn't work with ListNode<int> *lnode;
So I did it that way and it works.

So... according to your first link, in C++, whenever we intend to use templates, they must go in the header file (which of course nullifies the very point of having a clean. standalone header file)?

[mbozzi]

It wouldn't work with ListNode<int> *lnode;
So I did it that way and it works.

There's nothing wrong with what you did there (except that you're leaking memory). Your list controls the lifetime of its nodes. Perhaps std::unique_ptr<ListNode<int>> would be a better choice.

So... according to your first link, in C++, whenever we intend to use templates, they must go in the header file (which of course nullifies the very point of having a clean. standalone header file)

Yes. The definition of templates must be visible from where they are instantiated. This is because template code is "expanded" in a conceptually similar way to a macro --- the type parameter (in this case, T) is replaced with the corresponding argument from the location of its instantiation. If a template is instantiated but the definition of that template isn't visible from that TU, the compiler will defer instantiating it, assuming that the definition is somewhere else.

When that instantiation never shows up, you get linker errors.

This is IMO one of the biggest drawbacks of templates.

There are alternatives, though they still have some drawbacks. If you so choose, you can write your templates (sans definitions) in your header file, put the instantiations in the source file (sometimes the file extension is "tpp" or something), but instead of including the header file from the source file, include the source file from the bottom of the header file. This lets you keep a clean header file, but this technique can be confusing if you've not seen it before.

Another trick is to explicitly instantiate the templates you need. This can be done in the TU containing the templates after the definitions.

The problem with that is that using a new template parameter requires that you edit the code somewhere else to explicitly instantiate it. I'm not a big fan of that solution.

[ne555]

sorry, I quoted the wrong snip.

//LinkedList<int> *llist2 = new LinkedList<int>(lnode); //avoid this
LinkedList<int> llist2; //prefer this 

The nodes are not destroyed in the same scope, you create them in push_{back,front}() and delete them in the destructor... Wait, you don't have a destructor, you don't even have a single delete (and for some reason are creating 2 nodes in `.push_back()')
you've got some serious memory leak issues.


> they must go in the header file (which of course nullifies the very point of
> having a clean. standalone header file)?

dict wrote:

stand-alone
<jargon> Capable of operating without other programs, libraries, computers, hardware, networks, etc.

you can't have function definitions in headers unless they are template (or inline). So the only way to have a stand-alone header is for those functions to be template (or inline).

As for clean, you may have all the declarations at the top, no need to define them at the same point.

[d3v4l1]

LinkedList<int> *llist2 = new LinkedList<int>(lnode); is meant for cases where I have to instantiate the list with a pre-created node (as illustrated in my main.cpp's construct 2).

So unless there's a way I can pass a "reference to the node" to the class's constructor without the new keyword, I'll keep that line, regardless of if I'm using pointers to objects or just objects.

I figured LinkedList<int> llist2 = LinkedList<int>(lnode); would be stored on the stack as opposed to the former which goes in the heap but I prefer '->' to '.'

This is what I ended up doing, just to keep it the pointer way:

LinkedList<int> llist2_obj = LinkedList<int>(lnode);    // to the stack (automatic object)
LinkedList<int> *llist2 = &llist2_obj;    // use pointers still, like before 

Oh, about deleting stuff, like you noticed, I have no 'remove' function for the nodes. I didn't bother writing a destructor because the class was incomplete at the time and my major problem was the template issue.
Also, you mentioned the creation of two nodes I did in push_back() without deleting. So if I delete both nodes before control leaves the function, will it suffice (good practise wise)?

[mbozzi]

Well, good practice would be to not create redundant values.

That being said, it's more than "good practice" to release resources you allocate, though, mainly because if you don't your program is horribly broken --- leaking memory is not a "minor" issue.

On some platforms (on anything freestanding, for example) large-enough memory leaks will cause the system to catastrophically fail. On others, Linux, for instance, it's likely (but not guaranteed) that the kernel will send SIGKILL to your program, crashing it, after causing the system to slow to a crawl while your software consumes any swap space the system has available. If the kernel doesn't kill your program, it kills another.

I prefer '->' to '.'

That's not a valid preference. If you're using pointers because you like the notation, you're introducing complexity for no reason and making your code significantly more error prone by using pointers. This is especially the case if you're using new unnecessarily, which isn't a good idea because it forces the programmer to take into account resource management for no reason.

LinkedList<int> *llist2 = new LinkedList<int>(lnode); is meant for cases where I have to instantiate the list with a pre-created node (as illustrated in my main.cpp's construct 2).

What's wrong with LinkedList<int> llist2(lnode);?

Note that in push_back, you're reassigning nodePtr after allocating dynamic memory for it.
Once you lose the reference to that dynamically-allocated ListNode, it's leaked. You don't need it.

If you had to do that, you must delete the resource stored at that pointer before you lose your last reference to it, and once it's deleted, you must never access that resource again.

Let's slightly modify push_back:

template<class T>
void LinkedList<T>::push_back(T newData)
{
    // dynamically allocate this one --- if it had automatic storage
    // duration, it would be destroyed upon returning from the function.
    ListNode<T> * const newNode = new ListNode<T>;
    newNode->data = newData;  // Maybe do this in the node ctor?

    // If there are no nodes in the list
    // make newNode the first node.
    if (!head)
    {
        head = newNode;
        head->next = nullptr;
    }
    else  // Otherwise, insert newNode at end.
    {
        // Initialize nodePtr to head of list.
        ListNode<T> const *iter = head;

        // Find the last node in the list.
        while (iter->next)
        {
            iter = iter->next;
        }

        // Insert newNode as the last node.
        iter->next = newNode;
        newNode->next = nullptr;
    }
}

There's no delete, because you need the node you dynamically created to exist in the list until it is removed or the list node is otherwise destroyed (probably along with the list it's contained in.)

[d3v4l1]

You made iter const then you tried to overwrite it in read-only mode.

while(iter->next) {
    iter = iter->next;    // compiler coughs here
}

iter cannot be const here.

[mbozzi]

You made iter const

No, I didn't.
There is a difference between a pointer-to-constant and a pointer-constant.

[d3v4l1]

You and my compiler need to have a chat then.

[mbozzi]

No.

ListNode<T> const *iter = head; is semantically equivalent to
const ListNode<T> * iter = head;
Which is not semantically equivalent to
ListNode<T> *const iter = head; nor
ListNode<T> const * const iter = head;.

To put it another way, the iterator is mutable, but the referent is not.