@[TOC]

前言：

• 本文介绍STL——list功能复写，重点是迭代器，感受泛型编程，函数重载之美
• 博主收集的资料New Young，连载中。
• 博主收录的问题:New Young
• 转载请标明出处：New Young

迭代器

正向迭代器

思路

1. list的关键地方是对迭代器的复写，在复写这一过程，可以不断体会C++语言泛型编程，函数重载的魅力
2. 不同于vector，string，其底层类似数组，它们的迭代器是对元素对象的=="通用指针"==,通过指针的运算，就可以完成很多操作：++，解引用等，但是因为结点是在堆上是随机存储的，因此链表的迭代器必然要进行改变，同时为了支持算术运算（++，--...）解引用等操作，链表的迭代器必然要==封装成一个结构体==。
3. 为什么使用结构体？结构体默认成员是public，方便访问成员。
4. 同时又因为list是有const之分，因此迭代器分为iterarot和const_iterator,（注意这里的const是指节点中的data不可更改，但是迭代器仍是可以改变的，对比==常量指针==）但是这2者的功能非常类似，因此这里就通过==类模板的模板参数==进行区别。----`泛型编程`

   

构造函数

注意拷贝构造函数的形参，是最小权限，可以满足很多情形：匿名对象，类型提升

//迭代器
    template <class T, class Ref ,class Ptr>
    struct list_iterator
    {
typedef list_iterator<T, T&, T*>                     iterator;
        typedef list_iterator<T, const T&, const T*>   const_iterator;
        typedef list_node<T>                                    Node;
        typedef list_iterator<T, Ref, Ptr>                        Self;
        Node* _node;
        list_iterator( Node*x)
            :_node(x)
        {
            ;
        }
        list_iterator() 
        {}
        //场景：权限缩小的拷贝，同时因为计算需要，生成临时对象时会调用
        //其它的通过默认的拷贝构造和默认赋值运算符即可
        list_iterator(const iterator& x) : _node(x._node)
        {

        }

++，--

    typedef list_iterator<T, T&, T*>                     iterator;
        typedef list_iterator<T, const T&, const T*>   const_iterator;
        typedef list_node<T>                                    Node;
        typedef list_iterator<T, Ref, Ptr>                        Self;
Self& operator++()
{
    _node = _node->_next;
    return *this;
}
//后置++
Self  operator++(int)
{
    Self tmp(*this);
    _node = _node->_next;
    return tmp;
}

Self& operator--()
{
    _node = _node->_prev;
    return *this;
}
//后置++
Self  operator--(int)
{
    Self tmp(*this);
    _node = _node->_prev;
    return tmp;
}

*，->

1. 通过返回值的引用，当*时就可以防止const时，进行的写操作
2. 对于节点中存放内置类型的数据时，通过*就可以得到数据但是对于自对于类型如果需要访问数据成员时，需要->运算符但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
   如日期类 cout< < it- > year<<"" << it->month<<""<< it->day<<endl;
   本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下

    Ref operator*()
        {
            return _node->_data;
        }
Ptr  operator->()
        {
            return &_node->_data;
        
        }

！=，==

依据不同类型的迭代器，可能会因为生产一个临时的同类型的迭代器如：iterator和const iterator进行比较，会生成一个iterator的临时const_iterator的拷贝

    
        bool operator !=(const Self& it)const 
        {
            return _node != it._node;
        }
        bool operator ==(const Self& it)const
        {
            return _node == it._node;

        }

反向迭代器

1. 反向迭代器是对正向迭代器的复用，同时几乎所有的反向迭代器都是正向迭代器的复用，因此这里利用类模板来构造反向迭代器
2. 反向迭代器的rbegin是正向迭代器的end(),rend()是正向迭代器的begin().
3. 对于解引用，因为rbegin和rend的特殊性，反向迭代器返回的是迭代器前一个节点的数据

成员

    template<class Iterator,class Ref,class Ptr >
    class reverse_iterator
    {
        
    public:
        typedef reverse_iterator<Iterator, Ref, Ptr> self;    
     private:
        Iterator _it;

构造函数

template<class Iterator,class Ref,class Ptr >
    class reverse_iterator
    {
        
    public:
        typedef reverse_iterator<Iterator, Ref, Ptr> self;
        //这种形式的形参是最小权限，可以满足任何的拷贝构造
        reverse_iterator(const Iterator& it)
            :_it(it)
        {
            ;
        }

++，--

self& operator++()
        {
            --_it;
            return *this;
        }

        self operator++(int)
        {
            self tmp = _it--;
            return tmp;
        }

        self& operator--()
        {
            ++_it;
            return *this;
        }

        self operator--(int)
        {
            self tmp = _it++;
            return tmp;
        }

*与->

Ref operator*()
        {
            Iterator tmp = _it;
            return *(--tmp);
        }
        Ptr operator->()
        {
            Iterator tmp = _it;
            return  &(*(--tmp));
        }

！=与==

    bool operator !=(const self &rit )
        {
        
            return _it != rit._it;
        }

        bool operator ==(const self& rit)
        {

            return _it == rit._it;
        }
    private:
Iterator _it;

list

begin()

iterator begin()
        {
            return  iterator (_head->_next);
        
        }
 const_iterator begin()const
         {
             return  const_iterator(_head->_next);

         }

rbegin()

 reverse_iterator rbegin()
         {
             return  reverse_iterator(end());    
         }
 reverse_const_iterator rbegin()const
         {

             return reverse_iterator(end());

         }

end()

 iterator end()
        {
             return iterator(_head);
        }
const_iterator end()const
         {
             return const_iterator(_head);

         }

rend()

 reverse_iterator rend()
         {
             return  reverse_iterator (begin());
            
         } 
reverse_const_iterator rend()const
         {

             return reverse_iterator(begin());

         }

inert()

 //pos位置前插入数据
        iterator insert(iterator pos, const T& value)
         {
            assert(pos != end());
             Node* prevnode = pos._node->_prev;
             Node* newnode = new Node(value);
             newnode->_next = pos._node;
             newnode->_prev = prevnode;
             prevnode->_next = newnode;

             pos._node->_prev = newnode;

             return iterator(newnode);
         }

erase()

//返回删除后下一个节点的迭代器
        iterator erase(iterator pos)
         {
         
             assert(pos != end());
             Node* prevnode = pos._node->_prev;
             Node* nextnode = pos._node->_next;
        
             prevnode->_next = nextnode;
             nextnode->_prev = prevnode;
             delete pos._node;
             return iterator(nextnode);
         }

全部代码

Reverse_iterator.h

#pragma once


namespace My_Rev_It
{

    template<class Iterator,class Ref,class Ptr >
    class reverse_iterator
    {
        
    public:
        typedef reverse_iterator<Iterator, Ref, Ptr> self;
        //这种形式的形参是最小权限，可以满足任何的拷贝构造
        reverse_iterator(const Iterator& it)
            :_it(it)
        {
            ;
        }
        self& operator++()
        {
            --_it;
            return *this;
        }

        self operator++(int)
        {
            self tmp = _it--;
            return tmp;
        }

        self& operator--()
        {
            ++_it;
            return *this;
        }

        self operator--(int)
        {
            self tmp = _it++;
            return tmp;
        }


        Ref operator*()
        {
            Iterator tmp = _it;
            return *(--tmp);
        }
        Ptr operator->()
        {
            Iterator tmp = _it;
            return  &(*(--tmp));
        }

        bool operator !=(const self &rit )
        {
        
            return _it != rit._it;
        }

        bool operator ==(const self& rit)
        {

            return _it == rit._it;
        }
    private:
        Iterator _it;
    };

}

List.h

#pragma once
#include<iostream>
#include <stdlib.h> 
#include <string>
#include <assert.h>
#include<time.h>
#include<windows.h>
#include<list>
#include"Reverse_iterator.h"
namespace My_List
{
    //节点
    template<class T>
    struct  list_node
    {
        list_node(const T &x=T())
            :_next(nullptr),_prev(nullptr),_data(x)
        {
                ;
        }
        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;
    };

    //迭代器
    template <class T, class Ref ,class Ptr>
    struct list_iterator
    {
        typedef list_iterator<T, T&, T*>                     iterator;
        typedef list_iterator<T, const T&, const T*>   const_iterator;
        typedef list_node<T>                                    Node;
        typedef list_iterator<T, Ref, Ptr>                        Self;
        Node* _node;
        list_iterator( Node*x)
            :_node(x)
        {
            ;
        }
        list_iterator() 
        {}
        //这种形式的形参是最小权限，可以满足
        // 权限缩小的拷贝，同时因为计算需要进行提升，生成临时对象时会调用
        //其它的通过默认的拷贝构造和默认赋值运算符即可
        list_iterator(const iterator& x) : _node(x._node)
        {

        }
        //前置++
        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        //后置++
        Self  operator++(int)
        {
            Self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        //后置++
        Self  operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        //通过返回值的引用，当*时就可以防止const时，进行的写操作
        Ref operator*()
        {
            return _node->_data;
        }

    /*    对于节点中存放内置类型的数据时，通过*就可以得到数据
        但是对于自对于类型如果需要访问数据成员时，需要->运算符
        但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
        如日期类

        cout<<it->year<<"" <<it->month<<""<<it->day<<endl;
        本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下*/
        Ptr  operator->()
        {
            return &_node->_data;
        
        }

        //即使是不同类型的迭代器，这里也会因为生产一个临时的同类型的迭代器
        bool operator !=(const Self& it)const 
        {
            return _node != it._node;
        }
        bool operator ==(const Self& it)const
        {
            return _node == it._node;

        }

    };

    //带头双向循环链表
    template<class T>
    class list
    {
    public:
        typedef list_node<T>                                 Node;
        typedef list_iterator<T,T&,T*>                     iterator;
        typedef list_iterator<T,const T&,const T*> const_iterator;

        typedef My_Rev_It::reverse_iterator<iterator, T&, T*>   reverse_iterator;

        typedef My_Rev_It::reverse_iterator<const_iterator, const T&, const T*>  reverse_const_iterator;




        list(const T&value=T())//头节点
        {
            _head = new Node(value);
            _head->_next = _head;
            _head->_prev = _head;
        }

        list(int  n, const T& value = T())
        {

            _head = new Node(value);
            _head->_next = _head;
            _head->_prev = _head;

            for (int  i = 0; i < n; ++i)
                push_back(value);
        }

        //:list<Date> lt(5, Date(2022, 1, 2));
        //list<int > lt1(5, 1);
        //当形参进行对比时，对于Date会准确调用list(size_t n, const T& value = T())
        //当为int时，编译器更倾向于list(Inputitator first, Inputitator last)
        //因此重载一份list(int  n, const T& value = T())即可
        list(size_t n, const T& value = T())
        {

            _head = new Node(value);
            _head->_next = _head;
            _head->_prev = _head;
            for (size_t i = 0; i < n; ++i)
                push_back(value);
        }

        //利用迭代器区别初始化list
        template<class Inputitator>
        list(Inputitator first, Inputitator last)
        {
            //构建头节点
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造
        list(const list<T> &lt)
            
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;

            list<T> tmp(lt.begin(), lt.end());
            //注意 _head可能是随机指针或者nullptr
            std::swap(_head, tmp._head);
        }

        //赋值运算符
        list<T>& operator=(const list<T> lt)
        {
            clear();
            std::swap(_head, lt._head);
            return *this;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
        }
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }
        void push_back(const T &x)
        {
                
            insert(end(),x);
            /*Node* tail = _head->_prev;
            Node* newnode = new Node(x);
            tail->_next = newnode;
            newnode->_next = _head;
            newnode->_prev = tail;
            
            _head->_prev = newnode;    */
        }
        void push_front(const T& x)
        {
            insert(begin(), x);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            
            erase(begin());
        }

        iterator begin()
        {
            return  iterator (_head->_next);
        
        }

         iterator end()
        {
             return iterator(_head);
        }

         reverse_iterator rbegin()
         {
             return  reverse_iterator(end());
                
         }
         reverse_iterator rend()
         {
             return  reverse_iterator (begin());
            
         }


         reverse_const_iterator rbegin()const
         {

             return reverse_iterator(end());

         }
         reverse_const_iterator rend()const
         {

             return reverse_iterator(begin());

         }


         const_iterator begin()const
         {
             return  const_iterator(_head->_next);

         }
         const_iterator end()const
         {
             return const_iterator(_head);

         }
         //pos位置前插入数据
         //不会出现迭代器失效问题，但是需要返回一个插入位置的迭代器
         //很显然，constlist是不需要insert的
        iterator insert(iterator pos, const T& value)
         {
             Node* prevnode = pos._node->_prev;
             Node* newnode = new Node(value);
             newnode->_next = pos._node;
             newnode->_prev = prevnode;
             prevnode->_next = newnode;
             pos._node->_prev = newnode;
             return iterator(newnode);
         }

        //返回删除后下一个节点的迭代器
        iterator erase(iterator pos)
         {
         
             assert(pos != end());
             Node* prevnode = pos._node->_prev;
             Node* nextnode = pos._node->_next;
        
             prevnode->_next = nextnode;
             nextnode->_prev = prevnode;
             delete pos._node;
             return iterator(nextnode);
         }
    private:
        Node* _head;

    };
    
}

总结

复写过程经常遇到类型无法转化问题，大概率是因为权限问题或者