【C++】STL——list模拟实现

实现思路

** List是一个类模板，实际上是一个双向循环链表。在上一篇list基本使用的博客中，可以发现list支持了像vector一样的****"下标访问"**，也就是通过迭代器区间去访问链表的每个节点数据。本人在初学阶段也是比较好奇——list的迭代器（正向与反向）是如何实现的；本篇博客将以自己所掌握的知识，详细的介绍list是如何实现的。

list实现结构：

** 1.节**点设计

** 2.正向迭代器设计**

** 3.反向迭代器设计**

** 4.list各个接口完善（增删查改）**

一、list的节点设计

*list本身和list的结点是两个不同的结构，需要分开设计。以下是list的节***点结构： **

/*ListNode.h*/
namespace mlg
{
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev; //节点的前指针
        ListNode<T>* _next; //节点的后指针
        T _data;            //节点的数据
 
        ListNode(const T& data= T())//初始化列表进行初始化
            :_prev(nullptr)
            ,_next(nullptr)
            ,_data(data)
        {}
        
    };
}

** 首先，我们在自己的命名空间内模拟实现list（为了防止与库冲突），上面的代码就是list节点的结构。在这里是用并没有使用class，因为struct默认访问权限是public，又因为节点是需要经常访问的，所以使用struct更好。**

** 我们将这个类加上 template<**class****T> 后，就能够实现节点存储不同类型的数据，这也是C++模板的好处。

二、list的初步框架

** 当我们设计好了list的结点以后，我们就需要对list的基本框架进行设计，list要能够去控制这些节点，它的成员变量就必须是这个节点类；以下是list的结构设计：**

/*List.h*/
namespace mlg //命名空间保持一致
{
    template<class T> //list是一个类模板，设计时需要这个
    class list
    {
        typedef ListNode<T> Node; //将其类型重命名方便书写，在后续的类型中会有比较多的typedef
    public：

        /*
        成员函数包含了默认成员函数、迭代器和增删查改
        */

    private:
        Node* _head; //带头结点的双向循环链表
    };
}

在以上两个基本的框架搭建完毕以后，接下来重点主要是正向与反向迭代器

三、list的正向迭代器设计

1.实现原理

   ** list的确是支持了迭代器，但是list不在能够像vector一样以普通的指针作为迭代器，因为其节点不保证在存储空间中连续。list的迭代器必须有能力指向list的节点，并有能力进行递增、递减、取值、成员存储等操作。如何具备这样的能力呢？那就是递增时指向下一个结点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员；**

2. 正向迭代器的结构

/*iterator.h*/

namespace mlg
{
    template<class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef ListNode<T> Node;
        typedef __list_iterator<T, Ref, Ptr> self;
        Node* _node;
        
        //迭代器构造函数
        __list_iterator(Node* x)
            :_node(x)
        {}

        //重载*号 —— 实现解引用操作
        Ref operator*()
        {
            return _node->_data;
        }

        //重载->操作符 —— 实现指针访问元素
        Ptr operator->()
        {
            return &_node->_data;
        }

        //++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素
        self& operator++()
        {
            _node = _node->_next;//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点
            return *this;
        }

        //it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分）
        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;//后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点
            return tmp;
        }

        //--it 重载前置-- —— 让链表能够像数组一样去--操作，访问元素
        self& operator--()
        {
            _node = _node->_prev;//前置--返回的是--之后的值，直接让当前位置的结点指向前一个节点
            return *this;
        }

        //it-- 重载后置-- ——（这里需要加上int作为一个站位符，与前置--区分）
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;//后置--返回的是--之前的值，需要保存当前节点，再指向下一个节点
            return tmp;
        }

        //重载==
        bool operator==(const self& it)const
        {
            return _node == it._node;
        }

        //重载!=
        bool operator!=(const self& it)const
        {
            return _node != it._node;
        }
    
    };
}

在上述代码中，有三个地方没有做解释：

1. template<****class****T****,****class****Ref****,****class****Ptr****>

2. typedef__list_iterator<****T****, ****Ref****, ****Ref****> self;

** 它是迭代器类模板，里面包含了三个参数：T、Ref、Ptr；这三个参数表明传给iterator类的类型是不确定的，需要根据实际的情况，将这三个参数匹配到相应的地方。**

如：

** 1. ++/--操作：返回的是一个对象，只要用到了对象，一般都是写成****__list_iterator****<T, Ref, Ref>，因为类名太长，就有了第2点的typedef****__list_iterator****<**T****, Ref, Ref> self;

** 2. operator* 操作：返回的是对象的数据的值，并且*****号是具有读写操作的，我们应该返回的是这个数据类型的引用（T&**）；

** 3. operator->操作：返回的是对象的数据的地址，我们应该返回的是这个数据类型的地址（*T）；

--------------------------------------------------------------------------------------------------------------------------

**3. *typedef ListNode<T> Node;
Node _node;

** iterator类中的成员变量也是节点，我们刚刚已经解释了list迭代器的原理，它是通过重载++ / --,其内部实现上是节点中的_prev指针（找当前节点的前一个位置，相当于--操作）和_next指针（找当前节点的下一个位置，相当于++操作）的操作来实现的；**

** 所以，list正向迭代器的实现，本质上是用节点的两个指针的操作来代替了传统的++/--操作。再简单点说，其实就是函数调用（***包括/->**）

四、list反向迭代器的设计

1.实现原理

** 我们刚刚对list正向迭代器做了介绍以后，你是否会想，反向迭代器也是同样的原理呢？**确实可以这样理解，但是中间还有一个过程，我们先通下面的图解了解一下双链表（list）中和数组（vector）中正向迭代器与反向迭代器的区别。

vector迭代器的位置不需要多说，对于list的迭代器：****begin( )是数据的起始位置，end( )是数据的结束位置，也就是头结点；反向迭代器不就是与之相反嘛。

那如何才能通过反向迭代器控制链表的++/--等一系列操作呢？

** 方法一：我们可以重新写一个，也通过节点的指针去控制（比较麻烦：如果我想用正向迭代器区获取某个节点的位置传个反向迭代器，就需要给反向迭代器增设正向迭代器的接口）**

** 方法二：反向迭代器通过正向迭代器去间接控制list节点，达到想要的效果（在SLT原码中是这样子实现的，其目的是能适应其他容器，其称之为迭代器适配器**）

**2.反向迭代器的结构 **

/*reverse_iterator.h*/
namespace mlg
{
    template<class Iterator,class Ref,class Ptr>
    class __list_reverse_iterator
    {
        typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;
    public:
        //反向迭代器构造函数（通过正向迭代器去构出造反向迭代器）
        __list_reverse_iterator(Iterator it)
            :_it(it)
        {}

        //重载* 
        Ref operator*()
        {
            Iterator prev = _it; //获取正向迭代器end()的位置
            return *--prev;      //返回的是当前位置执行前置--操作后的解引用
        }

        //重载->
        Ptr operator->()
        {
            return &operator*(); //调用上面一个重载函数
        }

        //++it
        self& operator++()
        {
            --_it;        //反向迭代器的前置++就是调用正向迭代器的前置--
            return *this; //
        }

        //it++
        self operator++(int)
        {
            self tmp(*this); //后置++返回的是++之前的，所有先记录当前正向迭代器的位置
            _it--;           //反向迭代器的后置++就是调用正向迭代器的后置--
            return tmp;
        }

        //--it
        self& operator--()
        {
            ++_it;        //反向迭代器的前置--就是调用正向迭代器的前置++
            return *this;
        }

        //it--
        self operator--(int)
        {
            self tmp(*this); //后置--返回的是--之前的，所有先记录当前正向迭代器的位置
            _it++;           //反向迭代器的后置--就是调用正向迭代器的后置++
            return tmp;
        }

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

        //重载==
        bool operator==(const self& rit)const
        {
            return _it == rit._it;
        }

    private:
        Iterator _it;//成员变量是一个正向迭代器
    };
}

1.反向迭代器的 ++ / -- 操作解析

//++it
self& operator++()
{
    --_it;           //调用正向迭代器的前置--
    return *this;
}

//it++
self operator++(int)
{
    self tmp(*this);
    _it--;           //调用正向迭代器的后置--
    return tmp;
}

通过上图可以发现：

1.反向迭代器++（前置/后置）：调用正向迭代器的--

2.反向迭代器--（前置/后置）：调用正向迭代器的++

2.反向迭代器的 * / -> 操作解析

//重载* 
Ref operator*()
{
    Iterator prev = _it; //获取正向迭代器end()的位置
    return *--prev;      //返回的是当前位置执行前置--操作后的解引用
}

//重载->
Ptr operator->()
{
    return &operator*(); //调用上面一个重载函数
}

**对于->的重载，只要去复用就可以了。 **

五、list结构的完善

** 上面我们对节点结构、正向与反向迭代器结构实现原理及注意点一一做了介绍，最后一步也是最重要的一步，那就是将list结构完善起来，实现list的功能。**

1.构造函数

** list的成员变量是一个节点类，在构造头节点时，需要将这单个头节点构造成一个双向循环链表；**

//构造函数
list()
{
    _head = new Node;     //new一个节点出来
    _head->_prev = _head; 
    _head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
}

2.拷贝构造

** 拷贝构造是用一个已有对象去构造出另一个对象，首先将待构造对象进行初始化，然后利用迭代器区间去构造一个和lt1一样的临时的tmp对象，再进行数据的交换，达到深拷贝的目的。**

//拷贝构造 --- 现代写法 lt2(lt1)
list(const list<T>& lt)
{
    _head = new Node;
    _head->_prev = _head;
    _head->_next = _head;
    list<T> tmp(lt.begin(), lt.end());
    std::swap(_head, tmp._head);
}

3.迭代器区间构造

**通过传过来的迭代器区间进行初始化 **

//迭代器区间构造
template<class IputIterator>
list(IputIterator first, IputIterator last)
{
    _head = new Node;
    _head->_prev = _head;
    _head->_next = _head;

    while (first != last)
    {
        push_back(*first);//尾插数据，会根据不同类型的迭代器进行调用
        ++first;
    }
}

4.用n个val构造

** 通过用n个val来对对象进行初始化，需要注意这里的****T( )**是一个匿名对象，作为val的缺省参数，因为我们并不知道传给val的是一个对象还是一个整形（或其他），给缺省参数的好处在于，对于自定义类型编译器会去调用自定义类型的构造函数来对val进行初始化，如果是内置类型，它也是有自己的构造函数

//我们常常对内置类型的定义是这样的
int i = 10;

//但其实也可以这样定义
int i = int(10);

//用n个val个构造                     
list(int n, const T& val = T())                       
{                                                   
    _head = new Node;
    _head->_prev = _head;
    _head->_next = _head;
    for (int i = 0; i < n; i++)
    {
        push_back(val);
    }
}

对于用n个val进行初始化和迭代器区间初始化，起初我是这样写的（为了和库一致） ，测试时却出现问题：****非法的间接寻址

//迭代器区间初始化
template<class IputIterator>
list(IputIterator first, IputIterator last){...}

//用n个val初始化
list(size_t n, const T& val = T()) {...}   

//测试日期类
struct Date
{
    int _year;
    int _month;
    int _day;
    Date(int year = 1, int month = 1, int day = 1)
        :_year(year)
        , _month(month)
        , _day(day)
    {}
};

void test_list4()
{
    list<Date> lt1(5, Date(2022, 6, 21));//1
    for (auto e : lt1)
    {
        cout << e._year << "/" << e._month << "/" << e._day << endl;
    }
    cout << endl;

    list<int> lt2(5, 1);//2
    for (auto e : lt2)
    {
        cout << e << " ";
    }
    cout << endl;
}

5.赋值重载

//赋值重载 --- 现代写法 lt2 = lt1
list<T>& operator=(list<T> lt)
{
    std::swap(_head, lt._head);
    return *this;
}

6.析构函数

**析构函数可以结合着erase函数看 **

~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        //写法1
        erase(it++); //it是一个正向迭代器，采用后置++传给erase
        //写法2
        iterator del = it++;
        delete del._node;
        //写法3
        iterator del = it++;
        erase(del);
    }
    _head->_prev = _head;
    _head->_next = _head;
}

7.迭代器的实现

在list类中，我们typedef了正向与反向迭代器，解释一下其目的及作用

**//正向迭代器 **

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

//反向迭代器

typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;

** list是一个类模板，参数列表是T类型（未知类型）正向与反向迭代器分别都有三个参数，在list内重命名相当于内嵌定义，显示传参，我们对迭代器中需要返回值的地方不能进行类型的准确判断，通过这种显示传参，确定了迭代器三个参数的基本对于类型。**

** 对于正向迭代器，我们显示传参<**T、T&、T*****>如果是const迭代器，再重新typedef一个const迭代器；

** 对于反向迭代器，我们是需要正向迭代器去构造，所有显示传参就可以给到<**iterator, T&, T*****>

namespace mlg
{
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        //正向迭代器
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        iterator begin()
        {
            return iterator(_head->_next);//返回头节点的下一个结点
        }

        iterator end()
        {
            return iterator(_head);//返回头节点
        }

        const_iterator begin()const
        {
            return const_iterator(_head->_next);//返回头节点的下一个结点
        }

        const_iterator end()const
        {
            return const_iterator(_head);//返回头节点
        }

        //反向迭代器
        typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef __list_reverse_iterator<iterator, const T&, const T*>const_reverse_iterator;

        reverse_iterator rbegin()
        {
            return reverse_iterator(end());   //返回正向迭代器的结束位置
            //return reverse_iterator(_head); //等价与正向迭代器的头节点

        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());        //返回正向迭代器的起始位置
            //return reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
        }

        const_reverse_iterator rbegin()const
        {
            return const_reverse_iterator(end());   //返回正向迭代器的结束位置
            //return const_reverse_iterator(_head); //等价与正向迭代器的头节点
        }

        const_reverse_iterator rend()const
        {
            return const_reverse_iterator(begin());        //返回正向迭代器的起始位置
            //return const_reverse_iterator(_head->_next); //等价于正向迭代器头节点的下一个结点
        }
    };
}

8.增删查改

//头插
void push_front(const T& x)
{
    insert(begin(), x);
}

//尾插
void push_back(const T& x)
{
    /*
    Node* tail = _head->_prev;
    Node* newnode = new Node(x);
    tail->_next = newnode;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
    */
    insert(end(), x);
}

//头删
void pop_front()
{
    erase(begin());
}

//尾删
void pop_back()
{
    erase(--end());
}

//在pos位置插入元素x
iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;    
    Node* prev = cur->_prev;     
    Node* newnode = new Node(x); 
    prev->_next = newnode;      
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);//在pos位置插入返回的是新插入的节点位置
}

//在pos位置删除元素
iterator erase(iterator pos)
{
    assert(pos != end());
    Node* prev = pos._node->_prev;
    Node* next = pos._node->_next;
    delete pos._node;
    prev->_next = next;
    next->_prev = prev;
    return iterator(next);//返回的是删除pos位置节点的下一个节点
}

六、完整代码

1.ListNode.h

#pragma once

namespace mlg
{
    template<class T>
    struct ListNode
    {
        ListNode<T>* _prev;
        ListNode<T>* _next;
        T _data;

        ListNode(const T& data= T())
            :_prev(nullptr)
            ,_next(nullptr)
            ,_data(data)
        {}
        
    };
}

2.iterator.h

#pragma once

namespace mlg
{
    template<class T,class Ref,class Ptr>
    struct __list_iterator
    {
        typedef ListNode<T> Node;

        typedef __list_iterator<T, Ref, Ptr> self;

        typedef Ref reference;
        typedef Ptr pointer;

        Node* _node;

        __list_iterator(Node* x)
            :_node(x)
        {}

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

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

        //++it
        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        //it++
        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        //--it
        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        //it--
        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

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

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

**3.reverse_iterator.h **

#pragma once

namespace mlg
{
    template<class Iterator,class Ref,class Ptr>
    class __list_reverse_iterator
    {
        typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;
    public:
        __list_reverse_iterator(Iterator it)
            :_it(it)
        {}

        Ref operator*()
        {
            Iterator prev = _it;
            return *--prev;
        }

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

        //++it
        self& operator++()
        {
            --_it;
            return *this;
        }
        //it++
        self operator++(int)
        {
            self tmp(*this);
            _it--;
            return tmp;
        }
        //--it
        self& operator--()
        {
            ++_it;
            return *this;
        }
        //it--
        self operator--(int)
        {
            self tmp(*this);
            _it++;
            return tmp;
        }

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

    private:
        Iterator _it;
    };
}

4.list.h

#pragma once
#include "ListNode.h"
#include "iterator.h"
#include "reverse_iterator.h"

namespace mlg
{
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        //正向迭代器
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;

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

        //反向迭代器
        typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef __list_reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;

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

        //构造函数
        list()
        {
            _head = new Node;     //new一个节点出来
            _head->_prev = _head; 
            _head->_next = _head; //_prev 和 _next 同时指向了头结点，形成了双向循链表
        }

        //用n个val个构造                     
        list(int n, const T& val = T())                       
        {                                                  
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            for (int i = 0; i < n; i++)
            {
                push_back(val);
            }
        }

        //迭代器区间构造
        template<class IputIterator>
        list(IputIterator first, IputIterator last)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造 --- 现代写法 lt2(lt1)
        list(const list<T>& lt)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            list<T> tmp(lt.begin(), lt.end());
            std::swap(_head, tmp._head);
        }

        //赋值重载 --- 现代写法 lt2 = lt1
        list<T>& operator=(list<T> lt)
        {
            std::swap(_head, lt._head);
            return *this;
        }
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            iterator it = begin();
            while (it != end())
            {
                erase(it++);
            }
            _head->_prev = _head;
            _head->_next = _head;
        }

        void push_front(const T& x){ insert(begin(), x); }

        void push_back(const T& x) { insert(end(), x);}

        void pop_front() {erase(begin());}

        void pop_back(){erase(--end());}

        //在pos位置插入元素x
        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(x);
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;
            return iterator(newnode);
        }

        //在pos位置删除元素
        iterator erase(iterator pos)
        {
            assert(pos != end());
            Node* prev = pos._node->_prev;
            Node* next = pos._node->_next;
            delete pos._node;
            prev->_next = next;
            next->_prev = prev;
            return iterator(next);
        }

    private:
        Node* _head;
    };

    void print_list(const list<int>& lt)
    {
        list<int>::const_iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }

    void test_list5()
    {
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        list<int>::reverse_iterator rit = lt.rbegin();
        while (rit != lt.rend())
        {
            cout << *rit << " ";
            ++rit;
        }
        cout << endl;
    }
}

** 以上是对list模拟实现的全部结束，大家可以在.c文件下进行测试。如果存在任何问题，或者有不同的见解，大家可以直接在评论区提出来**