Having trouble creating a template version of a List/Node Class program

Question

Possible Duplicate:
Why can templates only be implemented in the header file?

I'm trying to take a program that creates and performs operations on a linked list.

This program works and compiles as is, but I have to create a template version of the program that can handle any type of data (int, float, char). There are two classes in the program, the NodeSLList class and the IntNode class.

I have done my best to create template versions of these two classes, while altering the member declarations and definitions as I think they should be, but for the life of me I cannot get rid of some of these errors. I am reading and re-reading my notes on templates and template classes, and scouring the web for better explanations, and will keep working while this is posted, but any help in the mean time I greatly appreciate.

There are two source code files and two header files.

IntNode.h:

///////////////////////////////////////////////////////////////////////
// class IntNode
//
// Description: represents the data that we want to store in our 
//              linked list
///////////////////////////////////////////////////////////////////////
#ifndef __INT_NODE__
#define __INT_NODE__

#include <iostream>

using std::ostream;


// class declaration
template <typename N>
class IntNode {

// make the following friends of this class in order that they be
// able to directly access private data of this container class
    friend void NodeSLList_Test(void);
    friend class NodeSLList;
    friend class TSArray;
    friend ostream& operator<<(ostream &, NodeSLList &);

public:

///////////////////////////////////////////////////////////////////////
// ostream operator
// 
// Description: provide overloaded ostream operator
// Input: reference to ostream object
//        reference to IntNode object to output
// Output: none
// Returns: reference to same ostream operator for cascading
///////////////////////////////////////////////////////////////////////
    friend ostream& operator<<(ostream & out, IntNode<N> & n);

///////////////////////////////////////////////////////////////////////
// default constructor
// 
// Description: provide default construction of an IntNode object
// Input: row of array
//        column of array
//        depth of array
//        initial value of node
//        pointer to next IntNode
// Output: none
// Returns: reference to same ostream operator for cascading
///////////////////////////////////////////////////////////////////////
    IntNode(int inRow=0, int inCol=0, int inDepth=0, N inData, IntNode<N> *in = 0);

///////////////////////////////////////////////////////////////////////
// GetRow
// 
// Description: return row member
// Input: none
// Output: none
// Returns: row member
///////////////////////////////////////////////////////////////////////
    const int GetRow() const;

///////////////////////////////////////////////////////////////////////
// GetColumn
// 
// Description: return column member
// Input: none
// Output: none
// Returns: column member
///////////////////////////////////////////////////////////////////////
    const int GetColumn() const;

///////////////////////////////////////////////////////////////////////
// GetDepth
// 
// Description: return depth member
// Input: none
// Output: none
// Returns: depth member
///////////////////////////////////////////////////////////////////////
    const int GetDepth() const;


///////////////////////////////////////////////////////////////////////
// GetData
// 
// Description: return data member
// Input: none
// Output: none
// Returns: data member
///////////////////////////////////////////////////////////////////////
    const N GetData() const;

private:

///////////////////////////////////////////////////////////////////////
// row
// 
// this variable holds the row of the array element (i.e first demension)
///////////////////////////////////////////////////////////////////////
    int row;

///////////////////////////////////////////////////////////////////////
// column
// 
// this variable holds the column of the array element (i.e 2nd demension)
///////////////////////////////////////////////////////////////////////
    int col;

///////////////////////////////////////////////////////////////////////
// depth
// 
// this variable holds the column of the array element (i.e 3rd demension)
///////////////////////////////////////////////////////////////////////
    int depth;

///////////////////////////////////////////////////////////////////////
// data
// 
// this variable holds the actual data at the array element
///////////////////////////////////////////////////////////////////////
    N data;


///////////////////////////////////////////////////////////////////////
// column
// 
// this variable holds the column of the array element (i.e 2nd demension)
///////////////////////////////////////////////////////////////////////
    IntNode<N> *next;
};


#endif __INT_NODE__

IntNode.cpp:

///////////////////////////////////////////////////////////////////////
// class IntNode
//
// Description: represents the data that we want to store in our 
//              linked list
///////////////////////////////////////////////////////////////////////
#include "IntNode.h"


///////////////////////////////////////////////////////////////////////
// default constructor

template <typename N>
IntNode<N>::IntNode(int inRow, int inCol, int inDepth, N inData, IntNode *in)
{
    data = inData; 
    next = in;
    row = inRow; 
    col = inCol; 
    depth = inDepth;
}

///////////////////////////////////////////////////////////////////////
// GetRow
///////////////////////////////////////////////////////////////////////
template <typename N>
const int IntNode<N>::GetRow() const
{
    return row;
}

///////////////////////////////////////////////////////////////////////
// GetColumn
///////////////////////////////////////////////////////////////////////
template <typename N>
const int IntNode<N>::GetColumn() const
{
    return col;
}

///////////////////////////////////////////////////////////////////////
// GetDepth
///////////////////////////////////////////////////////////////////////
template <typename N>
const int IntNode<N>::GetDepth() const
{
    return depth;
}

///////////////////////////////////////////////////////////////////////
// GetData
///////////////////////////////////////////////////////////////////////
template <typename N>
const N IntNode<N>::GetData() const
{
    return data;
}

///////////////////////////////////////////////////////////////////////
// ostream operator
///////////////////////////////////////////////////////////////////////
template <typename N>
ostream& operator<<(ostream & out, IntNode<N> & n)
{
    out << "[" << n.row << "]"
        << "[" << n.col << "]"
        << "[" << n.depth << "]:"
        << n.data;
    return out;
}

NodeSLList.h:

///////////////////////////////////////////////////////////////////////
// Class NodeSLList Interface
//
// Description - This is the interface for a class which implements 
//               a singly linked list of integers. Each node in the 
//               linked list is IntNode object, defined by the IntNode
//               class. 
///////////////////////////////////////////////////////////////////////
#ifndef INT_LINKED_LIST
#define INT_LINKED_LIST

#include <iostream>

using std::ostream;
using std::cout;
using std::cin;
using std::endl;

#include "IntNode.h"

// Class NodeSLList Declaration

template <typename T>
class NodeSLList {


///////////////////////////////////////////////////////////////////////
// operator<<
// 
// Description: print the list
// Input: reference to ostream object
//        reference to an NodeSLList object to be printed
// Output: linked list printed to screen
// Returns: reference to an ostream object
///////////////////////////////////////////////////////////////////////
    //friend ostream& operator<<( ostream &, NodeSLList<T> & );
    template <typename T> friend ostream & operator<<(ostream &, NodeSLList<T> &);


public:


///////////////////////////////////////////////////////////////////////
// default constructor
// 
// Description: initialize list
// Input: none
// Output: none
// Returns: none
///////////////////////////////////////////////////////////////////////
    NodeSLList();

///////////////////////////////////////////////////////////////////////
// destructor
// 
// Description: deallocates all memory for linked list by calling
//              destroyList() member function
// Input: none
// Output: none
// Returns: none
///////////////////////////////////////////////////////////////////////
    ~NodeSLList();

///////////////////////////////////////////////////////////////////////
// IsEmpty
// 
// Description: returns status of array
// Input: none
// Output: none
// Returns: TRUE if list is empty
//          FALSE otherwise
///////////////////////////////////////////////////////////////////////
    bool IsEmpty() const;

///////////////////////////////////////////////////////////////////////
// GetSize
// 
// Description: get current number of nodes in list
// Input: none
// Output: none
// Returns: number of nodes in list
///////////////////////////////////////////////////////////////////////
    int GetSize() const;

///////////////////////////////////////////////////////////////////////
// AddToHead
// 
// Description: add a node to the head of the list
// Input: data for node to be added
// Output: updated linked list
// Returns: none
///////////////////////////////////////////////////////////////////////
    void AddToHead(IntNode<T> & node);

///////////////////////////////////////////////////////////////////////
// DeleteFromHead
// 
// Description: remove a node from the head of the list
// Input: none
// Output: updated linked list
// Returns: data that was at the node just removed
///////////////////////////////////////////////////////////////////////
    IntNode<T> DeleteFromHead();

///////////////////////////////////////////////////////////////////////
// DeleteFromTail
// 
// Description: remove a node from the tail of the list
// Input: none
// Output: updated linked list
// Returns: data that was at the node just removed
///////////////////////////////////////////////////////////////////////
    IntNode<T> DeleteFromTail();

///////////////////////////////////////////////////////////////////////
// DeleteNode
// 
// Description: remove a node from the list
// Input: node number to be removed
// Output: updated linked list
// Returns: data that was at the node just removed
///////////////////////////////////////////////////////////////////////
    IntNode<T> DeleteNode(int nodeNum);

///////////////////////////////////////////////////////////////////////
// RetrieveNode
// 
// Description: retrieve data from a node without removing it from 
//              the list
// Input: node number (1-N; not 0-N-1)
// Output: none
// Returns: reference to node data
///////////////////////////////////////////////////////////////////////
    IntNode<T> &RetrieveNode(int nodeNum) const;

///////////////////////////////////////////////////////////////////////
// UpdateNode
// 
// Description: update a node's data
// Input: node number (1-N; not 0-(N-1))
// Output: updated node
// Returns: none
///////////////////////////////////////////////////////////////////////
    void UpdateNode(int nodeNum, IntNode<T> &node);

///////////////////////////////////////////////////////////////////////
// DestroyList
// 
// Description: deallocates all memory for linked list
// Input: none
// Output: reset linked list
// Returns: none
///////////////////////////////////////////////////////////////////////
    void DestroyList();

private:

    IntNode<T> *head, *tail;

};

#endif INT_LINKED_LIST

NodeSLList.cpp:

///////////////////////////////////////////////////////////////////////
// Class NodeSLList Implementation
//
// Description - This file implements a singly linked list.
///////////////////////////////////////////////////////////////////////
#include "IntNode.h"
#include "NodeSLList.h"


///////////////////////////////////////////////////////////////////////
// default constructor
///////////////////////////////////////////////////////////////////////
template <typename T>
NodeSLList<T>::NodeSLList()
{ 
    head = tail = 0;
}


///////////////////////////////////////////////////////////////////////
// destructor
////////////////////////////////////////////////////////////////////
template <typename T>
NodeSLList<T>::~NodeSLList()
{
    // call destroyList() to remove all nodes
    // and reset linked list
    DestroyList();
}

///////////////////////////////////////////////////////////////////////
// IsEmpty
////////////////////////////////////////////////////////////////////
template <typename T>
bool NodeSLList<T>::IsEmpty() const
{ 
    return (head == 0); 
}

///////////////////////////////////////////////////////////////////////
// DestroyList
///////////////////////////////////////////////////////////////////////
template <typename T>
void NodeSLList<T>::DestroyList()
{
    // while the list is NOT empy
    // keep removing the head node and make
    // the next node the head node
    for (IntNode<T> *p; !IsEmpty(); )
    {
        p = head->next;
        delete head;
        head = p;
    }
    head = tail = 0;
}

///////////////////////////////////////////////////////////////////////
// AddToHead
///////////////////////////////////////////////////////////////////////
template <typename T>
void NodeSLList<T>::AddToHead(IntNode<T> & node)
{
    // create a new node, and make it the head. the 
    // previous head will become head->next
    head = new IntNode<>(node.row, node.col, node.depth, node.data, head);

    // if this is the first node, make the tail the 
    // same as the head
    if (tail == 0)
        tail = head;
}

///////////////////////////////////////////////////////////////////////
// DeleteFromHead
// 
// Description: remove a node from the head of the list
// Input: none
// Output: updated linked list
// Returns: data that was at the node just removed
///////////////////////////////////////////////////////////////////////
template <typename T>
IntNode<T> NodeSLList<T>::DeleteFromHead()
{
    IntNode<T> temp;
    if (IsEmpty())
    {
        cout << "*****ERROR: Can't delete from head. List is Empty" << endl;
        return temp;
    }

    temp.data = head->data;
    temp.col = head->col;
    temp.row = head->row;
    temp.depth = head->depth;

    IntNode<T> *tmp = head;

    // if there is only one node, set the head and pointer tails
    // to NULL (0)
    if (head == tail)
        head = tail = 0;

    // otherwise, move the head pointer to the next node 
    // in the list
    else
        head = head->next;

    // delete head node
    delete tmp;

    return temp;
}

///////////////////////////////////////////////////////////////////////
// DeleteFromTail
///////////////////////////////////////////////////////////////////////
template <typename T>
IntNode<T> NodeSLList<T>::DeleteFromTail()
{
    IntNode<T> nodeData;
    nodeData.col = tail->col;
    nodeData.row = tail->row;
    nodeData.depth = tail->depth;
    nodeData.data = tail->data;


    // if there is only one node, delete the only node, and set the 
    // head and tail pointers to NULL (0) 
    if (head == tail)
    {
        delete head;
        head = tail =0;
    }

    // otherwise, traverse to the tail node and delete it
    else
    {
        IntNode * temp;
        for (temp = head; temp->next != tail; temp = temp->next);
        delete tail;
        tail = temp;
        tail->next = 0;
    }

    return nodeData;
}

///////////////////////////////////////////////////////////////////////
// DeleteNode
///////////////////////////////////////////////////////////////////////
template <typename T>
IntNode<T> NodeSLList<T>::DeleteNode(int nodeNum)
{
    if (nodeNum <= 0) nodeNum = 1;
    IntNode<T> *prev=head , *temp=head;
    IntNode<T> current;

    // traverse to the node
    for (int loop=1; loop<nodeNum; loop++)
    {
        prev=temp, temp=temp->next;
        // check for case where nodeNum is > the number of 
        // nodes in the list. if we reach the tail before
        // we traverse to the node, delete the tail 
        if ( temp == tail )
            return DeleteFromTail();
    }

    // if deleting the head just call 
    // the appropriate member function 
    // and don't repeat that logic here
    if (temp == head) return DeleteFromHead();

    // otherwise, delete the node we traversed to
    prev->next = temp->next;
    current.row = temp->row;
    current.col = temp->col;
    current.data = temp->data;

    delete temp;

    return current;
}

///////////////////////////////////////////////////////////////////////
// RetrieveNode
///////////////////////////////////////////////////////////////////////
template <typename T>
IntNode<T> & NodeSLList<T>::RetrieveNode(int nodeNum) const
{
    IntNode<T> *tmp = head;

    // traverse to the node, or to the last node, whichever comes
    // first
    for (int i=1; i< nodeNum && tmp != tail; i++)
        tmp = tmp->next;

    return *tmp;
}

///////////////////////////////////////////////////////////////////////
// UpdateNode
///////////////////////////////////////////////////////////////////////
template <typename T>
void NodeSLList<T>::UpdateNode(int nodeNum, IntNode<T> &node)
{
    IntNode<T> *tmp = head;

    // traverse to the node, or to the last node, whichever comes
    // first
    for (int i=1; i< nodeNum && tmp != tail; i++)
        tmp = tmp->next;

    tmp->data = node.data;
    tmp->col = node.col;
    tmp->row = node.row;
}

///////////////////////////////////////////////////////////////////////
// GetSize
///////////////////////////////////////////////////////////////////////
template <typename T>
int NodeSLList<T>::GetSize() const
{
    // check to see if the list is empty. if 
    // so, just return 0
    if ( IsEmpty() ) return 0;

    int size = 1;
    IntNode<T> *p = head;
    // compute the number of nodes and return
    while (p != tail)
    {
        size++;
        p = p->next;
    }
    return size;
}

///////////////////////////////////////////////////////////////////////
// operator<<
///////////////////////////////////////////////////////////////////////
template <typename T>
ostream & operator<<(ostream & output, NodeSLList<T> & sl)
{
    IntNode<T> *p = sl.head;
    if ( sl.IsEmpty())
    {
        output << "List is empty!";
        return output;
    }
    output << "[row][col][depth]:data = ";
    output << *p << ", ";
    while (p != sl.tail)
    {
        p = p->next;
        output << *p << ", ";
    } 

    return output;
}

// TEST DRIVER. Only used to test the class.
// Activated by defining TEST_DRIVER in the 
// Project - Settings - C/C++ - Preprocessor definitions
#ifdef LIST_DRIVER

#include <stdlib.h>
void pause();

void main(void)
{
    NodeSLList_Test<int>();
    NodeSLList_Test<double>();
    NodeSLList_Test<float>();
}


template <typename T>
void NodeSLList_Test()
{

    NodeSLList<T> s;
    IntNode<T> temp;

    cout << "TESTING "<<T<<" OPERATIONS\n";

    IntNode<T> n1(1,1,1,10);
    IntNode<T> n2(1,2,1,20);
    IntNode<T> n3(1,3,1,30);
    IntNode<T> n4(1,4,1,40);
    IntNode<T> n5(1,5,1,50);

    cout << "Testing addToHead() operation" << endl;
    s.AddToHead(n5);
    s.AddToHead(n4);
    s.AddToHead(n3);
    s.AddToHead(n2);
    s.AddToHead(n1);

    cout << s << endl;

    cout << "\nTesting GetSize() operation" << endl;
    cout << "list contains " << s.GetSize() << " node(s)" << endl;

    cout << "\nTesting DeleteFromHead() operation" << endl;
    temp = s.DeleteFromHead();
    cout << "node retrieved " << temp << endl;
    cout << s << endl;

    cout << "\nTesting DeleteFromTail() operation" << endl;
    temp = s.DeleteFromTail();
    cout << "node retrieved " << temp << endl;
    cout << s << endl;

    cout << "\nTesting RetrieveNode() operation" << endl;
    temp = s.RetrieveNode(0);
    cout << "node retrieved (should be first node) " << temp << endl;
    temp = s.RetrieveNode(50);
    cout << "node retrieved (should be last node) " << temp << endl;
    temp = s.RetrieveNode(2);
    cout << "node retrieved (should be 2nd node) " << temp << endl;
    pause();

    cout << "Adding n3 to head" << endl;
    cout << "Adding n2 to head" << endl;
    s.AddToHead(n3);
    s.AddToHead(n2);
    cout << "List is now: " << s << endl;
    cout << "\nTesting DeleteNode() operation" << endl;
    temp = s.DeleteNode(50);
    cout << "node deleted (should be last node) " << temp << endl;
    cout << s << endl;
    temp = s.DeleteNode(3);
    cout << "node deleted (should be 3rd node) " << temp << endl;
    cout << s << endl;

    cout << "Test SsEmpty() operation" << endl;
    cout << (s.IsEmpty() ? "List IS Empty\n" : "List NOT Empty\n");

    cout << "\nTesting UpdateNode() operation (updating 3rd node with [10][20][30]:500)" 
        << endl;
    temp.row = 10;
    temp.col = 20;
    temp.depth = 30;
    temp.data = 500;
    s.UpdateNode(3,temp);
    cout << s << endl;

    pause();

    cout << "\nTesting the ability to delete nodes from head, even" << endl
        << "after list is empty" << endl
        << "Should recieve 2 errors" << endl;
    temp = s.DeleteFromHead();
    temp = s.DeleteFromHead();
    temp = s.DeleteFromHead();
    temp = s.DeleteFromHead();
    temp = s.DeleteFromHead();

    cout << "\nTest IsEmpty() operation" << endl;
    cout << (s.IsEmpty() ? "List IS Empty\n" : "List NOT Empty\n");

    cout << "\nTesting DestroyList() operation" << endl;
    s.AddToHead(n3);
    s.AddToHead(n2);
    s.AddToHead(n1);
    cout << s << endl;
    cout << "calling DestoryList()" << endl;
    s.DestroyList();
    cout << s << endl;


}

void pause()
{
    cout << "Press RETURN to continue" << endl;
    cin.get();
    system("cls");
}

#endif

Errors:

Error   1   error C2989: 'NodeSLList' : class template has already been declared as a non-class template    c:\cis554\nodesllist_template\nodesllist.h  160
Error   2   error C3857: 'NodeSLList': multiple template parameter lists are not allowed    c:\cis554\nodesllist_template\nodesllist.h  23
Error   3   error C2988: unrecognizable template declaration/definition c:\cis554\nodesllist_template\nodesllist.cpp    14
Error   4   error C2059: syntax error : '<' c:\cis554\nodesllist_template\nodesllist.cpp    14
Error   5   error C2588: '::~NodeSLList' : illegal global destructor    c:\cis554\nodesllist_template\nodesllist.cpp    24
Error   6   error C1903: unable to recover from previous error(s); stopping compilation c:\cis554\nodesllist_template\nodesllist.cpp    24
    7   IntelliSense: default argument not at end of parameter list c:\CIS554\NodeSLList_Template\IntNode.h 51

Is this after you made *a very small change from code that worked?* What was that change? If you changed a bunch of things, and you're getting a bunch of errors, you're doing it wrong. — Beta, Nov 21 '12 at 05:59
I made many changes, to try and get the template functionality to work. Still sorting it all out. — traggatmot, Nov 21 '12 at 06:02
@traggatmot look at your code comment, is all that necessary? `// Input: none` you are commenting for obivious things — billz, Nov 21 '12 at 06:59
@bilz - It is not, the files were given to me this way, and my job is to make the changes I talk about. The comments are meant to make the purpose of everything completely obvious. — traggatmot, Nov 21 '12 at 07:39

score 2 · Answer 1 · answered Nov 21 '12 at 06:02

2

It's template, C++ compilers don't support separating class definition into another file. You have to put all .cpp code inside .h

Move all code from IntNode.cpp into IntNode.h, NodeSLList.cpp code into NodeSLList.h

answered Nov 21 '12 at 06:02

billz

44,644
9
83
100

I have done that, and am still running into lots of problems. – traggatmot Nov 21 '12 at 07:31
what's the errors you are getting? – billz Nov 21 '12 at 07:41

score 0 · Answer 2 · answered Nov 21 '12 at 05:54

0

Friend declaration of NodeSLList is wrong, it should be friend class NodeSLList<N>;. And all references to NodeSLList should change accordingly. And other errors are stemming from inconsistent declaration of NodeSLList class.

Also, put the inline definition of the methods of the template class inside the header file, otherwise there would linker errors for users of your template class. Though there are ways to overcome that without putting the definition in the header, but they are not generally good.

answered Nov 21 '12 at 05:54

nanda

804
4
8

Nanda, I was going to combine the everything into the two header files, but only after i got it working...which hasn't happened yet. I replaced the friend declaration as you suggested, and all other instances of NodeSLList have been change to refer to template (in all four files), but that doesn't appear to have helped....after doing that I also combined the separate .cpp and .h files into the .h files....but there are still a tone of errors, with many of the functions in in the NodeSLList class now not being recognized as members of that class... – traggatmot Nov 21 '12 at 06:39
Do not try to do multiple changes in one iteration. Just ensure all declarations and reference of NodeSLList is consistent and unlike here where in one place it is declared as non template class and at other the opposite. After this you can combine the files which itself might cause errors if not done right. – nanda Nov 21 '12 at 06:55

Having trouble creating a template version of a List/Node Class program

2 Answers2