C++ 通用链表和迭代器

Question

我刚开始学习 C++，我需要编写一个通用的链表和迭代器。这是我写的代码(list.h)，但我认为它不正确。它不起作用，我不确定它是否通用。

#include <iostream>        
#include <cassert>


using namespace std;        
using namespace ListExceptions;

class List;    
class Iterator;

template<class T>

class Node{    
private:    
   T data;    
   Node* previous;    
   Node* next;    
   friend class List;    
   friend class Iterator;    
public:    
   Node(T element){    
       data = element;    
       previous = NULL;    
       next = NULL;    
   }    
};    

class List{    
private:    
   Node* first;    
   Node* last;    
public:    
   List(){    
       first = NULL;    
       last = NULL;    
   }    
   void pushBack(T element);    
   void insert(Iterator iter, T element);    
   Iterator remove(Iterator i);    
   Iterator find(const Predicate& predicate);    
   void sort(const Compare& comparer);    
   int getSize() const;    
   Iterator begin();    
   Iterator end();    
};    

class Iterator{    
private:    
   Node* position;    
   Node* last;    
   friend class List;    
public:    
   Iterator();    
   void next();    
   T getElement()const;    
   bool equals(Iterator b) const;    
   bool notEquals(Iterator b) const;    
};    

如果有人可以帮助我？

Answer 1

首先是 List 和 Iterator 是非模板类，您可能想创建给定类型的 List .您可能会考虑重构代码，使 Node 和 Iterator 都是 List 类型的内部类(这会使事情变得更简单):

template <typename T>
class List {
public:
   typedef T value_type;

   class Iterator;
   struct Node {           // Internal to List<T>, so there will be different
                           // List<T>::Node for each instantiationg type T
                           // But you don't need the extra <T> parameter for List
                           // or Iterator
      value_type data;
      Node* next;
      Node* last;

      friend class List;       // Inside List<T>, List by itself refers to List<T>
      friend class Iterator;
   };
   //...
};

替代方案的代码稍微复杂一些:

template <typename T> class List;
template <typename T> class Iterator;
template <typename T> class Node {
   T data;
   Node * next;
   Node * last;
   friend class List<T>;
   friend class Iterator<T>;
};
template <typename T>
class List {
   Node<T>* first;              // note <T> required
//...
};