c++ 模版编程，构造迭代器和双向链表

迈不过友情╰ 2022-04-18 02:36 182阅读 0赞

#pragma once
    #include <iostream>
    #include <stdexcept>
    #include "func.h"
    // 链表
        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*()throw (std::runtime_error){
                if(pos) return pos->value;
                else throw (std::runtime_error("dereferencing null iterator"));
            }
    
        };
    
    //双向链表容器模版
        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();
        }
    
    };