templates - how to?

[tones1986]

Hey guys and girls. I am working on a project that needs to use templates. My professor didnt go over teh use of them in class, nor is our book very descriptive of them. Im assuming they are way easier than i make them seem, but some help , tips, etc would be very helpful.

My assignment is to make a doubly linked list, using templates etc. I have a basic skeleton for the code which is all placed within a single .h file. (We have a driver program given to use for use with our code as the main.cpp file).

//BASIC HEADER FILES HERE

template <class T>
struct DNode
{
    Deque(const T &);
    T * item, * prev, * next;
};

template <class T>
class Deque
{
  private:
      T * qFront, * qRear, * data;    
  public:
      Deque();
      bool empty();
};

/****************************************************************
   FUNCTION:   Deque()
   ARGUMENTS:  int
   RETURNS:    None
   NOTES:      this is the Deque constructor
****************************************************************/ 
template <class T>
Deque::Deque()
{
  qFront = qRear = NULL;
}

/****************************************************************
   FUNCTION:   Deque()
   ARGUMENTS:  int
   RETURNS:    None
   NOTES:      this is the Deque constructor
****************************************************************/ 
template <class T>
DNode::Deque(const T& item)
{
  prev = next = NULL;
  data = item;
}

/****************************************************************
   FUNCTION:   empty()
   ARGUMENTS:  None
   RETURNS:    bool
   NOTES:      finds out if the deque is empty or not
****************************************************************/
template <class T>
bool Deque<T>::empty()
{
  return (qFront == NULL && qRear == NULL);
}

#endif //END OF DEQUE.H

I have a problem trying to compile this using the driver program in a dev project.

Here is the start code:

int main()
   {
   Deque<int> deque1;

   cout << "deque 1 is ";

   if (deque1.empty())
      cout << "empty" << endl;
   else
      cout << "not empty" << endl;

And i get the following error message when attempting to compile.
[Linker error] undefined reference to `Deque<int>::Deque()'

Which means that the Deque<int> deque1 defined in main.cpp cannot find the constructor correct? This being the case, if im correct in thinkin that way, the problem lies with the way the templates work/need to be set. Could you guys give me a hand in sorting out the basics of the templates/and if its not a template problem, point that out too!!!

Thank you so much in advance

[Narue]

Template tip #1: Write your class first using concrete types (such as int) and get it working. Then add the template parameters and replace instances of the concrete types with the parameters. This skips the whole "a template isn't instantiated until you use it" crap, which tends to hide simple errors until you actually touch the code in your test driver.

Template tip #2: During initial development, define all of your member functions in the class definition. That way you don't have to deal with the mess of properly linking a member function definition to a template class. Compare:

template <typename T>
class Foo {
public:
  void test ( T arg )
  {
    // Stuff
  }
};

template <typename T>
class Foo {
public:
  void test ( T arg );
};

template <typename T>
void Foo<T>::test ( T arg )
{
  // Stuff
}

I don't know about you, but duplicating the template parameters and qualifying the class name in an outside member function definition is tedious and tends to verbose when all you really care about at this point is getting the code working. After it's working you can easily convert example #1 into example #2.

Note: You're using the format of example #2, but it's incomplete, which is why you're getting errors.

[tones1986]

Thank you for the help so far. That was really easy to understand and helped me figure alot of this stuff out... i have come across another problem. I am supposed to make a dynamically allocated list using pointers -

So like this:
Prev Data Next Prev Data Next
qRear ----- |NULL| 6 | |<====>| Ptr | 7 | NULL|----qFront

So each node has a data member - with 2 pointers, one to the previous node, the other to the next node in the list.

I am having problems with my struct and class definitions....here is my code for this:

template <class T>
class Deque
{
  private:
      int qSize;
      DNode <T> *qFront, *qRear;
  public:
      Deque();
      ~Deque();
      Deque(const Deque&);
      bool empty();
      int size();
      void clear();
};

template <class T>
struct DNode
  {
  T data;
  DNode <T> *next, *previous;

  DNode(T newData)
    {
     data = newData;
     next = NULL;
     previous = NULL;
    }
   };

I get errors such as:
25 C:\Users\Tony\Documents\NIU - School\Spring 2008\csci 241\assign7\Deque.h ISO C++ forbids declaration of `DNode' with no type
On this line:

DNode <T> *qFront, *qRear;

And then i get lots of
C:\Users\Tony\Documents\Deque.h `qFront' undeclared (first use this function)
C:\Users\Tony\Documents\Deque.h `qRear' undeclared (first use this function)

For lines like this in functions:

template <class T>
Deque<T>::Deque()
{
  qFront = qRear = NULL;
}

Can someone explain to me how im supposed to be declaring the variables/pointers so so that i dont get these errors!

Thanks you so much

[tones1986]

After continuing working with my code/program. I still cannot figure out some of the errors i am getting. I just dont understand why i cant declare my variables as i have them, so if someone could point out what im doing wrong, it just doesnt make sense to me as is:

Code:

#ifndef DEQUE_H
#define DEQUE_H

#include <iomanip>
#include <ostream>
#include <fstream>

using namespace std;


template <class T>
class Deque
{
  private:
      int qSize;
      DNode *qFront, *qRear;
  public:
      Deque();
      ~Deque();
      Deque(const Deque&);
      bool empty();
      int size();
      void clear();
};

template <class T>
struct DNode
  {
  T data;
  DNode *next, *previous;

  DNode(T newData)
    {
     data = newData;
     next = NULL;
     previous = NULL;
    }
   };


/****************************************************************
   FUNCTION:   Deque()
   NOTES:      this is the Deque constructor
****************************************************************/ 
template <class T>
Deque<T>::Deque()
{
  qFront = NULL;
  qRear = NULL;
}

/****************************************************************
   FUNCTION:   Deque()
   NOTES:      this is the Deque destructor
****************************************************************/ 
template <class T>
Deque<T>::~Deque()
{
  clear();
}

/****************************************************************
   FUNCTION:   Deque()
   NOTES:      this is copy constructor
****************************************************************/ 
template <class T>
Deque<T>::Deque(const Deque& otherObject)
{
DNode<T> * current;
current = qRear;

while (current != NULL)
  DNode<T> mynewnode(current);
  //pushBack(mynewnode);
  current = current->previous;    
}

/****************************************************************
   FUNCTION:   empty()
   NOTES:      finds out if the deque is empty or not
***************************************************************/
template <class T>
bool Deque<T>::empty()
{
  return (qFront == NULL && qRear == NULL);
}

/****************************************************************
   FUNCTION:   size()
   NOTES:      returns the size of the deque
***************************************************************/
template <class T>
int Deque<T>::size()
{
  return qSize;
}

/****************************************************************
   FUNCTION:   clear()
   NOTES:      clears the dynamic array
***************************************************************/
template <class T>
void Deque<T>::clear()
  {
  DNode<T> *current, *forward;
  current = qFront;

  while(current != NULL)
    {
     forward = current->next;
     delete current;
     current = forward;
    }

  qFront = NULL;
  qRear = NULL;
} 

#endif //END OF DEQUE.H

My errors are: (this is compiling on a linux machine using g++)

g++ -ansi -Wall -c assign7.cpp
Deque.h:25: error: ISO C++ forbids declaration of DNode with no type
Deque.h:25: error: expected ";" before "*" token
Deque.h: In constructor "Deque<T>::Deque()":
Deque.h:59: error: "qFront" was not declared in this scope
Deque.h:60: error: “qRear” was not declared in this scope
Deque.h: In copy constructor “Deque<T>::Deque(const Deque<T>&)”:
Deque.h:85: error: “qRear” was not declared in this scope
Deque.h: In member function “bool Deque<T>::empty()”:
Deque.h:102: error: “qFront” was not declared in this scope
Deque.h:102: error: “qRear” was not declared in this scope
Deque.h: In member function “void Deque<T>::clear()”:
Deque.h:127: error: “qFront” was not declared in this scope
Deque.h:137: error: “qRear” was not declared in this scope
make: *** [assign7.o] Error 1

So obviously im declaring my variables incorrectly - but by the looks of them they 'should' work. Unless im missing something completely. Hope someone can lend a hand.

Thank you in advance !!!

[tones1986]

I figured that this was due to my having my struct declaration below my class declaration. Very stupid, idiotic mistake. I moved it above my class and it worked fine.

New question...

How would be copy constructor look like?

I have this:

template <class T>
Deque<T>::Deque(const Deque& otherObject)
{
DNode<T> * current;
current = qRear;

while (current != NULL)
  DNode<T> *otherObject(current);
  pushBack(otherObject);
  current = current->previous;    
}

But am unsure if this is right, im pretty sure its not, as i crash when i try to pushBack();

Talking of pushBAck(), how would this work? Im supposed to insert an item into the rear of the queue. But this queue is empty, so basically its just adding one node, and setting the pointers to be correct. I tried the following, but didnt work seeing as im asking for help!

template <class T>
void Deque<T>::pushBack(const T& item)
{
     //DNode<T> * newNode;
     //newNode->data = item;
     cout << "Item data is: " << item << endl;
     /*
     if (qRear == NULL && qFront == NULL)
        {
          newNode->prev = qRear;
          newNode->prev = qFront;
        }
     else
        {
         qFront->next = newNode->prev;
         qFront = newNode->prev;
         newNode->next = NULL;
        }
        */
}

Hope someone can help again. THank you so much.

[Lerner]

1) You have to decide what you mean by making a copy. Since you have pointers within the node objects making up the list/deque if you do a shallow copy then each copy is using the same memory and if one copy is destroyed then the memory for all copies is destroyed. This may or may not be what you want. Doing a deep copy means copying the information in the node into a new node and then arranging new addresses creates an independent, freestanding list with the same values in the same order but uses different nodes so deleting/destroying/changing one list doesn't affect another.

2) Add a new node to an empty list:

DNode<T> * newNode;
newNode->data = item;
newNode->prev = NULL;
newNode->next = NULL;

if (qRear == NULL && qFront == NULL)
{
    qRear = newNode;
    qFront = newNode;
}

3) Why do you use a deque at all in this program, let alone have a deque within DNode? Shouldn't it be more like this:

struct DNode
{
    int item;
    DNode * prev;
    DNode * next;
};

class DLLIST
{
   DNode * front;
   DNode * rear;
}

[tones1986]

I was able to work oout the push() function and am now able to insert items into the linked list without any problems...

My next concern, as mentioned above, is that of the copy constructor.

I have to use a push(either front or back) to traverse through the original linked list, then create an exact copy as another list/Deque.

So here is the function call:

Deque<int> deque2(deque1);

And here is the (very incorrect function)

template <class T>
Deque<T>::Deque(const Deque& otherObject)
{                 
DNode<T> * current;
current = qRear;

while (current != NULL)
  DNode<T> *otherObject(current);
  pushBack(current->data);
  current = current->prev;  
}

This above, crashes the program... i think i know why i might be going wrong, but im not sure how to fix it. I don't ever really use the otherObject (the original) when working with the function, plus the function needs to return the new Deque, (deque2 in this case) after it is all working correctly.

DOes anyone have any ideas... ?

Here is part of the assignment itself:
Copy constructor

The class should also have a proper copy constructor. If you choose to make a copy of the linked list by using one of the push methods, make sure you set both the front and rear pointers for the new deque to NULL before you attempt to insert any nodes into it.

If the above makes any sense, please inform me as to what it may mean.. Im assuming i can just traverse through the original, using pushBack(current->data) or something along those lines??? If that works, how do i set up all the pointers etc to work correctly ---

Sorry for the multiple posts - but help would be appreciated once again.

Thank you very much in advance

[Lerner]

Write two different copy constructors for this:

class A
{
   public:
     int * data;
};

Then expand it to cover your situation using whichever version you think is best for how you plan to use the objects created with the class. For many purposes however, the deep copy method is the most appropriate.