Templates

[ohsnap1319]

Hello Everyone!

I am currently trying to use function templates in order to rewrite two linked list functions "appendNode" and "insertNode". However, I don't think that I am quite getting the hang of it and I have alot of errors that I don't know how to fix. Any help with this problem would be much appreciated. Thanks!

// This program uses function templates to rewrite the append
// and insert node functions from our linked list notes
// so that they will accept any data type.

#include <iostream>

using namespace std;
template <class T>

struct ListNode {
	T value;
	struct ListNode *next;
};
ListNode *head = NULL;

void appendNode(T num);
void insertNode (T num);

int main()
{

}

template <class T>
void appendNode(T num)
{
	struct ListNode *newNode, *nodePtr = head;
	newNode = new ListNode;
	if(newNode == NULL) {
		cout << "Error allocating memory for new list member!\n";
		return 1;
	}
	newNode->value = num;
	newNode->next = NULL;
	if(head == NULL) {
		cout << "List was empty - " << newNode->value;
		cout << " is part of list's first node.\n";
		head = newNode;
	}
	else {
		while(nodePtr->next != NULL)
			nodePtr = nodePtr->next;
		nodePtr->next = newNode;
	}
	return 0;
}

template <class T>
void insertNode (T num)
{
	struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL;

	newNode = new ListNode;
	if(newNode == NULL) {
		cout << "Error allocating memory for new list member!\n";
		return 1;
	}
	newNode->value = num;
	newNode->next = NULL;
	if(head == NULL) {
		cout << "List was empty - " << newNode->value;
		cout << " is part of list's first node.\n";
		head = newNode;
	}
	else {
		while((nodePtr != NULL) && (nodePtr->value < num)) {
			prevNodePtr = nodePtr;
			nodePtr = nodePtr->next;
		}
		if(prevNodePtr == NULL)
			newNode->next = head; head = newNode;
		else
			newNode->next = nodePtr; prevNodePtr->next = newNode;
	}
	return 0;
}

[Disch]

Line 14: 'ListNode' is a template, so you can't define it like that. You need to give it a type to use for 'T'

For example: ListNode<int> *head = NULL;. This will compile okay because you give 'int' for T.

Lines 16 and 17: You're using T as a type, but those functions aren't templated so the compiler doesn't know what T is:

template <class T>
void appendNode(T num);

template <class T>
void insertNode (T num);

This will fix that problem.

[jsmith]

As a side note, a typical error is:

newNode = new ListNode;
if(newNode == NULL) {
    cout << "Error allocating memory for new list member!\n";
    return 1;
}

By default, newNode will never be NULL, so the if check() is completely useless.
new never returns NULL; rather it throws std::bad_alloc if allocation fails. If you
_really_ want to handle out of memory errors yourself, then you have to use
the nothrow version of new:

#include <new>

newNode = new (std::nothrow) ListNode;

[ohsnap1319]

@Disch thanks for the help with my errors.

@jsmith thanks for the information.

[ohsnap1319]

// This program uses function templates to rewrite the append
// and insert node functions from our linked list notes
// so that they will accept any data type.

#include <iostream>

using namespace std;
template <class T>

struct ListNode {
	T value;
	struct ListNode *next;
};
ListNode<int> *head = NULL;

template <class T>
void appendNode(T num);

template <class T>
void insertNode (T num);

int main()
{

}

template <class T>
void appendNode(T num)
{
	struct ListNode *newNode, *nodePtr = head;
	newNode = new ListNode;
	if(newNode == NULL) {
		cout << "Error allocating memory for new list member!\n";
		return 1;
	}
	newNode->value = num;
	newNode->next = NULL;
	if(head == NULL) {
		cout << "List was empty - " << newNode->value;
		cout << " is part of list's first node.\n";
		head = newNode;
	}
	else {
		while(nodePtr->next != NULL)
			nodePtr = nodePtr->next;
		nodePtr->next = newNode;
	}
	return 0;
}

template <class T>
void insertNode (T num)
{
	struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL;

	newNode = new ListNode;
	if(newNode == NULL) {
		cout << "Error allocating memory for new list member!\n";
		return 1;
	}
	newNode->value = num;
	newNode->next = NULL;
	if(head == NULL) {
		cout << "List was empty - " << newNode->value;
		cout << " is part of list's first node.\n";
		head = newNode;
	}
	else {
		while((nodePtr != NULL) && (nodePtr->value < num)) {
			prevNodePtr = nodePtr;
			nodePtr = nodePtr->next;
		}
		if(prevNodePtr == NULL)
			newNode->next = head; head = newNode;
		else
			newNode->next = nodePtr; prevNodePtr->next = newNode;
	}
	return 0;
}

[guestgulkan]

To ohsnap1319 You have marked this thread as solved.
However, I just cannot see the code above (posted at Apr 19, 2010 at 3:33pm) compiling at all.

[mcleano]

You also did not take jsmith's advice.

[imi]

Disch is right with the line-14 comment about templates, however I recommend you move the head-variable into the struct (as static) so you can make use of T as template argument. After all, you want your template to work with all kinds of types (that's the whole idea of making it a template, right?)

template<class T>
struct ListNode {
...
    static ListNode<T> *head = NULL;
};

Next for appendNode and insertNode: You have to specify the template parameter to ListNode as well. Everywhere you use "ListNode", that would be "ListNode<T>". ListNode without any <> afterwards is just the name of a template, and not a type.


And jsmith is right! you should think about your null-checking on new. If you don't happen to work with a very ancient compiler, (Like Visual Studio 5.0) it's just useless.

Ciao, Imi.