Expert: vijayan - 11/14/2008

Question
QUESTION: Dear Vijayan,

Below I pasted my list.h file for you to see.
I am  a newbie in C++.  My template classes work fine (at least it seems like so). Now I'd like to make class Iterator an internal class of List.  Could you help me on that please?
I have been searching on line  for examples but I couldn't find anything to help me understand how it's done.
thanks for your time.


#ifndef LIST_H
#define LIST_H

#include <string>

template <typename T> class Element;
template <typename T> class Iterator;

template <typename T>
class List {
public:
  List();
  List(const List<T> & other);//copy constructor
  ~List();
  void add(const T& s);
  void insert(const Iterator<T>& pos, const T& s);
  void remove(Iterator<T>& pos);
  void free();
  void copy(const List<T>& other);
  const List<T> & operator=(const List<T>& other);

  Iterator<T> getFirst() const;
  Iterator<T> getLast() const;
private:
  Element<T>* firstElement;
  Element<T>* lastElement;
};
template <typename T>
class Iterator {
public:
  Iterator();
  T& get() const;
  void next();
  void prev();

  bool equal(const Iterator& b) const;
  void operator++(int junk);
  void operator++();
  T& operator*();
  bool operator==(const Iterator& other) const;
  bool operator!=(const Iterator& other) const;

private:
  Element<T>* position;
  Element<T>* last;
  friend class List<T>;
};
#endif


ANSWER: all you have to do is declare/define the class Iterator within the List<> class.

the template parameter T is available to the Iterator because it is within List<T>. ie List<int>::iterator and List<double>::iterator are different classes.

for example, to make both Iterator and Element nested classes within List<T>

template <typename T>
class List
{
   public:
       class Element;
       class Iterator;

        List();
        List(const List<T> & other);//copy constructor
        ~List();
        void add(const T& s);
        void insert(const Iterator& pos, const T& s);
        void remove(Iterator& pos);
        void free();
        void copy(const List<T>& other);
        const List<T> & operator=(const List<T>& other);

        Iterator getFirst() const;
        Iterator getLast() const;
   private:
        Element* firstElement;
        Element* lastElement;

   public:
         class Iterator {
         public:
         Iterator();
         T& get() const;
         void next();
         void prev();

         bool equal(const Iterator& b) const;
         void operator++(int junk);
         void operator++();
         T& operator*();
         bool operator==(const Iterator& other) const;
         bool operator!=(const Iterator& other) const;

         private:
         Element* position;
         Element* last;
         friend class List<T>;
         };

         class Element
         {
         T value ;
         Element* next ;
         Element* previous ;
         // etc
         };

};


and if you want to define a member of Iterator out of line, this is how you would do it:

template< typename  T > T& List<T>::Iterator::get() const
{ return position->value ; }




---------- FOLLOW-UP ----------

QUESTION: thank you so much for your reply :))
I would like to keep the class element outside the class list (pasted below). Could you kindly tell me what changes I need to make to my list.cpp file?



#include "list.h"
#include <string>
#include <iostream>

using namespace std;

template <typename T>
class Element {
public:
  Element(const T& s);

private:
  T value;
  Element<T>* prev;
  Element<T>* next;
  friend class List<T>;
  friend class Iterator<T>;
};

template <typename T>
Element<T>::Element(const T &s) {
  value = s;
  prev = next = NULL;
}

template <typename T>
Iterator<T>::Iterator() {
  position = last = NULL;
}

template <typename T>
T& Iterator<T>::get() const {
  return position->value;
}

template <typename T>
void Iterator<T>::next() {
  position = position->next;
}

template <typename T>
void Iterator<T>::prev() {
  if(position == NULL) {
     position = last;
  } else {
     position = position->prev;
  }
}

template <typename T>
bool Iterator<T>::operator ==(const Iterator& other) const {
  return (this->position == other.position);
}

template <typename T>
bool Iterator<T>::operator !=(const Iterator& other) const {
  return (this->position != other.position);
}

template <typename T>
void Iterator<T>::operator ++(int junk) {
  this->position = this->position->next;
}

template <typename T>
void Iterator<T>::operator ++() {
  this->position = this->position->next;
}

template <typename T>
T& Iterator<T>::operator *() {
  return this->position->value;
}

template <typename T>
bool Iterator<T>::equal(const Iterator& b) const {
  return position==b.position;
}

template <typename T>
List<T>::List() {
  firstElement = lastElement = NULL;
}

//copy constructor
template <typename T>
List<T>::List(const List<T> & other) {
  firstElement = lastElement = NULL;
  copy(other);
}

template <typename T>
void List<T>::copy(const List<T>& other) {
  if(&other == this) {
     return;
  }
  free();
  for(Iterator<T> pos=other.getFirst(); pos!=other.getLast(); pos++ ){
     this->add(pos.get());
  }
}

template <typename T>
List<T>::~List() {
  free();
}

template <typename T>
void List<T>::free() {
  for(Iterator<T> pos=this->getFirst(); pos!=this->getLast();){
     Iterator<T> temp = pos;
     pos++;
     this->remove(temp);
  }
  //important!!
}

template <typename T>
const List<T> & List<T>::operator=(const List<T>& other) {
  copy(other);
  return *this;
}

template <typename T>
Iterator<T> List<T>::getFirst() const {
  Iterator<T> it;
  it.position = firstElement;
  it.last = lastElement;
  return it;
}

template <typename T>
Iterator<T> List<T>::getLast() const {
  Iterator<T> it;
  it.position = NULL;
  it.last = lastElement;
  return it;
}

template <typename T>
void List<T>::add(const T& s) {
  Iterator<T> last = getLast();
  insert(last, s);
}

template <typename T>
void List<T>::insert(const Iterator<T>& pos, const T& s) {
  
  Element<T>* newElement = new Element<T>(s);
  
  if(lastElement==NULL && firstElement==NULL) {
     //list is empty
     firstElement = newElement;
     lastElement = newElement;
  } else {
     //list is not empety
     if(pos.position == NULL) {
        lastElement->next = newElement;
        newElement->prev = lastElement;
        lastElement = newElement;
     } else if(pos.position == firstElement){
        firstElement->prev = newElement;
        newElement->next = firstElement;
        firstElement = newElement;
     } else {
        newElement->next = pos.position;
        newElement->prev = pos.position->prev;
        pos.position->prev->next = newElement;
        pos.position->prev = newElement;
     }

  }
}

template <typename T>
void List<T>::remove(Iterator<T>& pos) {
  
  if(lastElement==NULL && firstElement==NULL) {
     //list is empty, nothing to remove
     return;
  } else {
     //list is not empety
     if(pos.position == NULL) {
        return;
     } else if(pos.position == firstElement){
        firstElement = firstElement->next;
     } else {
        pos.position->prev->next = pos.position->next;
        pos.position->next->prev = pos.position->prev;
     }
     delete pos.position;
  }
}



ANSWER: since the List<T> and List<T>::Iterator needs to use the name Element<T> and Element<T> needs to declare List<T> and List<T>::Iterator as friends, place the various parts in your file in this order:

a. forward declare Element<T>
b. define List<T> with List<T>::Iterator as a nested class
c. define Element<T>
d. define member functions of Element<T>, List<T> and List<T>::Iterator


template <typename T> class Element ; // declaration

template <typename T>
class List
{
   public:
       class Iterator;

        List();
        List(const List<T> & other);//copy constructor
        ~List();
        void add(const T& s);
        void insert(const Iterator& pos, const T& s);
        void remove(Iterator& pos);
        void free();
        void copy(const List<T>& other);
        const List<T> & operator=(const List<T>& other);

        Iterator getFirst() const;
        Iterator getLast() const;
   private:
        Element<T>* firstElement;
        Element<T>* lastElement;

   public:
         class Iterator {
         public:
         Iterator();
         T& get() const;
         void next();
         void prev();

         bool equal(const Iterator& b) const;
         void operator++(int junk);
         void operator++();
         T& operator*();
         bool operator==(const Iterator& other) const;
         bool operator!=(const Iterator& other) const;

         private:
         Element<T>* position;
         Element<T>* last;
         friend class List<T>;
         };

};

template <typename T>
class Element { // definition
public:
      Element(const T& s);

private:
      T value;
      Element<T>* prev;
      Element<T>* next;
      friend class List<T>;
      friend class List<T>::Iterator;
};


template< typename  T > T& List<T>::Iterator::get() const
{ return position->value ; }

// etc


as these are templates, the list file should be a header (not cpp).



---------- FOLLOW-UP ----------

QUESTION: but I would still need a cpp file right?
Are you suggesting that I rename list.cpp to element.cpp?

I'm sorry I may lack some basic knowledge.

Answer
templates are a pure compile-time mechanism. the compiler needs to see the template code for any template that you would be using.

put Element<>, List<> etc in list.h

where you want to use the list, for example main.cpp or some_other_file.cpp, add a

#include "list.h"

so that the preprocessor would bring it into the translation unit where you need it.