C/C++编程：使用模板实现一个链式容器的迭代器

亦凉 2023-01-17 02:23 78阅读 0赞

#include <stdexcept>
    
    template<typename T> class list; // 前置声明，用于声明友元类
    
    
    template<typename N>
    class list_iterator{
        
        N * pos;
        
        template<typename T> friend class list;  //list模板可访问私有成员以进行插入等操作
        
    public:
    	// 重命名各种类型以方便其他模板提取
        typedef typename N::value_type value_type;  // 标记迭代器所指数据的类型
        typedef typename N::reference_type reference_type;  // 标记迭代器所指数据的引用
        typedef typename N::const_reference_type const_reference_type;   // 标记迭代器所指数据的只读引用类型
        typedef list_iterator<N> self_type;
        
        list_iterator() : pos(0) {
        }  // 构造一个空迭代器
        list_iterator(N *pos) : pos(pos) {
        }
        
        bool operator!= (self_type const &right) const {
        
            return pos != right.pos;
        }
    
        bool operator== (self_type const &right) const {
        
            return pos == right.pos;
        }
        
        self_type & operator++ (){
        
            if(pos){
        
                pos = pos->next;
            }
            return *this;
        }
        
        reference_type operator* () noexcept (false){
        
            if (pos){
        
                return pos->value;
            }else{
        
                throw std::runtime_error("dereferencing null iterator!");
            }
        }
        
    };

通过typedef按约定好的规则预定义一些类型以描述本模板的相关特性时常见且非常重要的一种手段。这一段代码是基于在节点类N中有同样的类型名定义的假定。有此定义后，就可以通过比如下面代码提取出迭代器所指元素类型并加以应用等：

list_iterator<linked_list_node>::value_type a;

另外，这三行typedef语句中还在嵌套标识符N::value\_type、N::reference\_type以及N::const\_reference\_type之前必须用typename修饰。因为N是一个模板参数，编译器仅知道其为一个类型，对于嵌套其内的标识符，编译器无从判断其意义。N::value\_type 也可能是类型N的一个静态成员变量名、成员函数名、嵌套定义的枚举值名。在无从推断嵌套标识符的意义时，编译器首先假定该标识符不是类型名，在根据上下文判断。所以，当嵌套标识符确为类型名时，须在其前加typename修饰以免编译器报错。

// 链表节点类模板
    template<typename T>
    struct list_node{
        
        typedef T value_type;
        typedef T& reference_type;
        typedef const T& const_reference_type;
        
        T value;
        list_node *prev;
        list_node *next;
        
        list_node(T const &value, list_node *prev, list_node *next) :
            value(value), prev(prev), next(next){
        }
    };
    
    // 链表类模板
    template<typename T>
    class list{
        
        typedef list_node<T> node_type;
        node_type *head;  // 头节点指针
    
    public:
    	// 类型定义
        typedef T value_type;
        typedef list_iterator<node_type> iterator;
        
        list() :head() {
        }
        ~list(){
        
        	// 析构时删除链表节点空间
            while (head){
        
                node_type *n = head;
                head = head->next;
                delete n;
            }
        }
        
        // 从表头插入数据
        void push_front(T const &v){
        
            head = new node_type (v, 0, head);
            if(head->next){
        
                head->next->prev = head;
            }
        }
        
         // 从表头删除数据
        void pop_front(T const &v){
        
            if(head){
        
                node_type *n = head;
                head = head->next;
                head->prev = 0;
                delete n;
            }
        }
        
        // 指定位置后面插入元素
        void insert(iterator it, T const &v){
        
            node_type *n = it.pos;
            if(n){
        
                node_type *new_node = new node_type (v, n, n->next);
                new_node->next->prev = new_node;
                n->next = new_node;
            }
        }
        
        // 删除指定元素
        void erase(iterator *it){
        
            node_type  *n = it->pos;
            ++it;  // 将迭代器指向下一个元素
            if(n){
        
                if(n->next){
        
                    n->next->prev = n->prev;
                }
                if(n->prev){
        
                    n->prev->next = n->next;
                }
                if(head == n){
        
                    head = n->next;
                }
                delete n;
            }
        }
        
        bool is_empty() const {
        
            return head == 0;
        }
        
        iterator begin(){
        
            return iterator (head);
        }
        
        iterator  end(){
        
            return iterator ();
        }
    };