12

I have been trying to implement my own linked list class for didactic purposes.

I specified the "List" class as friend inside the Iterator declaration, but it doesn't seem to compile.

These are the interfaces of the 3 classes I've used:

Node.h:

#define null (Node<T> *) 0

template <class T>
class Node {
 public:
    T content;
    Node<T>* next;
    Node<T>* prev;

    Node (const T& _content) :
        content(_content),
        next(null),
        prev(null)
    {}
};

Iterator.h:

#include "Node.h"

template <class T>
class Iterator {
 private:
    Node<T>* current;

    Iterator (Node<T> *);

 public:
    bool isDone () const;

    bool hasNext () const;
    bool hasPrevious () const;
    void stepForward ();
    void stepBackwards ();

    T& currentElement () const;

    friend class List<T>;
};

List.h

#include <stdexcept>
#include "Iterator.h"

template <class T>
class List {
 private:
    Node<T>* head;
    Node<T>* tail;
    unsigned int items;

 public:
    List ();

    List (const List<T>&);
    List& operator = (const List<T>&);

    ~List ();

    bool isEmpty () const {
        return items == 0;
    }
    unsigned int length () const {
        return items;
    } 
    void clear ();

    void add (const T&);
    T remove (const T&) throw (std::length_error&, std::invalid_argument&);

    Iterator<T> createStartIterator () const throw (std::length_error&);
    Iterator<T> createEndIterator () const throw (std::length_error&);
};

And this is the test program I've been trying to run:

trial.cpp

using namespace std;
#include <iostream>
#include "List/List.cc"

int main ()
{
 List<int> myList;

 for (int i = 1; i <= 10; i++) {
  myList.add(i);
 }

 for (Iterator<int> it = myList.createStartIterator(); !it.isDone(); it.stepForward()) {
  cout << it.currentElement() << endl;
 }

 return 0;
}

When I try to compile it, the compiler gives me the following errors:

Iterator.h:26: error: ‘List’ is not a template

Iterator.h: In instantiation of ‘Iterator’:

trial.cpp:18: instantiated from here

Iterator.h:12: error: template argument required for ‘struct List’

List.cc: In member function ‘Iterator List::createStartIterator() const [with T = int]’:

trial.cpp:18: instantiated from here

Iterator.h:14: error: ‘Iterator::Iterator(Node*) [with T = int]’ is private

List.cc:120: error: within this context

Seems like it is not recognizing the friend declaration. Where did I go wrong?

Davide Valdo
  • 779
  • 8
  • 21
  • Don't define your own null (or NULL, or anything related) macro. In the case of initializing data members, `0` works just fine. –  Jan 03 '10 at 00:46
  • I know it's ugly, it was only temporary. But I was quite sure C++ didn't allow implicit casting. – Davide Valdo Jan 03 '10 at 00:48
  • Casts are never implicit, but conversions are. (Two sides of the same coin, you might say, and "conversion" is also used to name methods which convert a value among other uses, but that's a different type of conversion.) What you need to initialize a pointer is another pointer of suitable type, or a null pointer constant; `0` is a perfectly fine null pointer constant (`NULL` is too, if you prefer). –  Jan 03 '10 at 00:52
  • You will also need to define your class template's (List's) methods in the header (instead of List.cc, which shouldn't be #included in good code), in the general case, because class templates and function templates aren't really classes and functions, they *generate* classes and functions, and the full code must be available to the compiler. –  Jan 03 '10 at 01:00

2 Answers2

14

try adding a forward declaration

template <class T> class List;

at the start of Iterator.h -- that might be what you need to allow the friend declaration inside the Iterator class to work.

Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
5

The problem is List has not been properly declared in Iterator.h. Instead, nest the Iterator class inside List (automagically making it a template), which you'll likely want to do anyway (to use List::Iterator instead of renaming it to ListIterator or IteratorForList, as you would to have more than one Iterator in a namespace).

template<class T>
struct List {
  //...
  struct Node {/*...*/};
  struct Iterator {
    // ...
  private:
    Iterator(Node*);
    friend class List; // still required
  };
  //...
};