C++ list模拟实现

 以下是本次list模拟的三个类与成员函数

using namespace std;
#include<assert.h>
namespace bear
{
    //结点类
    template<class T>
    struct ListNode
    {
        //成员变量
        ListNode<T>* _next;//前指针
        ListNode<T>* _prev;//后指针
        T _data;//数据

        ListNode(const T& x = T())//构造函数
    };


    //迭代器类
    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* n)
 
        //运算符重载
        Ptr operator->()

        Ref operator*()

        self& operator++()

        self operator++(int)


        self& operator--()

        self operator--(int)

        bool operator!=(const self& s)

        bool operator==(const self& s)

    };



    //list类
    template<class T>
    class list
    {

    public:
        typedef ListNode<T> node;
        typedef _list_iterator<T,T&,T*> iterator;
        typedef _list_iterator<T,const T&,const T*> const_iterator;
        /*typedef _list_iterator<T,const T&> const_iterator;*/


        //迭代器指针
        iterator begin()

        const_iterator begin() const
 
        iterator end() 

        const_iterator end() const



        //副构造函数
        void empty_init()

        //主构造函数
        list()


        //迭代器区间函数
        template<class Iterator>
        list(Iterator first, Iterator last)

        //交换函数
        void swap(list<int>& tmp)


        //现代写法 拷贝构造函数  it2(it1)
        list(list<T>& it)

        // it1 = it2;
        list<T>& operator=(list<T> it)

        //析构函数
        ~list()

        //清除函数
        void clear()


        //头删
        void push_back(const T& x)


        //头插
        void push_front(const T& x)

        //尾删
        void pop_back()

        //头删
        void pop_front()

        //插入函数
        void insert(iterator pos,const T& x)


        //删除函数
        iterator erase(iterator pos)

        //获取大小函数
        size_t size() const;

        //扩容+初始化函数
        void resize(size_t n, const T& val = T());

        //判断是否为空函数
        bool empty() const;

    private:
        node* _head;//成员变量，指向头结点的指针
    };



  
}

结点类的模拟实现

list在底层是一个链表，具体来说，是一个带头双向循环链表

该链表包含了3个部分，分别是：数据内容，指向前一个结点的指针，指向后一个结点的指针。所以我们需要通过实现一个结构体来存储该数据：

而且还需要对该值进行初始化，也就是需要编写一个构造函数。

    //节点
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;//指向前一个结点的指针
        ListNode<T>* _prev;//指向后一个结点的指针
        T _data;//数据内容

        ListNode(const T& x = T())//构造函数
            //若没有给值，则采用编译器的默认构造值作为数据
            :_next(nullptr)
            , _prev(nullptr)
            , _data(x)
        {}
    };

迭代器类的模拟实现

为什么会有迭代器类？

在模拟实现string类与vector类时，都没有提到要模拟实现迭代器类，那是因为它们两个数据是存储在一块连续的空间的，我们只需要让指针进行自增或者自减即可对一整个对象进行访问操作，也就是说，string类与vector类的指针都是原生指针

 那么在list类中，每一块数据都在独立的空间，是随机的，并不是连续的，如果我们让指针进行自增或者自减，是不会访问到下一个结点，所以不能通过自增自减的方式进行访问操作

那么就很明显了，迭代器类就是为了让list可以让我们像别的容器一样进行简单的操作，减少不必要的麻烦，对容器的操作进行了统一。

所以可以将list的指针进行封装，对指针的各种运算符进行重载，举个例子：当对list的指针p进行++的时候，许多人都认为会指向下一个结点，但是实际上：p++  =  p=p->next。这就说明了许多东西并不是我们想象中的那样，只是在暗中进行了许多灵性的操作。

综上所述，迭代器类就是为了让list指针能够和别的容器指针进行一样行为，统一了容器的操作。

迭代器类的模板参数

可以看到，这个模板有三个参数：

template<class T,class Ref,class Ptr>

再看list的模拟实现中：

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

这里分别重定义了一个迭代器与const迭代器，所以Ref就是引用类型，Ptr代表了指针类型。

所以当我们使用普通迭代器时，就会实例化一个普通迭代器对象；使用const迭代器时，就会实例化一个const迭代器对象

这也很好的体现了模板的方便性，若没有模板的话，我们就需要写很多重复代码来区分普通迭代器与const迭代器。

构造函数

因为迭代器只是对list指针进行封装，所以变量也只有个一个，用来接收所给的结点指针来构造一个迭代器对象。

        _list_iterator(node* n)
            :_node(n)
         {}

++运算符重载

++运算符有两种

第一种是前置++，我们只需要让指针指向下一个结点就好

第二种是后置++，我们需要先记录当前指针的位置，再让指针指向下一个位置，最后再返回记录下来的指针位置就好

        //前置++
        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;//返回自减前的结点指针
        }

==运算符重载

==实际上只是判断两个迭代器是否为同一个位置的迭代器，所以只需要返回结点指针是否相等即可

        bool operator==(const self& s)
        {
            return _node == s._node;//判断两个结点指针指向是否相同
        }

!=运算符重载

与==运算符相反，判断两个迭代器是否为不同位置的迭代器

        bool operator!=(const self& s)
        {
            return _node != s._node;//判断两个结点指针指向是否不同
        }

*运算符重载

*运算符实际上就是解引用，与平常的*p类似，为了得到该结点的数据，所以只需要返回该节结点的数据即可，这里Ref为引用返回，因为要考虑到解引用后可能会进行修改等操作

        Ref operator*()
        {
            return _node->_data;//返回结点指针所指结点的数据
        }

->运算符重载

在平常使用到结构体时，我们会使用到->的符号，用来直接指向某个成员变量，那么在list中我们也可以直接进行迭代器的->运算符，所以也是直接返回该结点的数据即可

        Ptr operator->()
        {
            return &_node->_data;//返回结点指针所指结点的数据的地址
        }

当list容器当中的每个结点存储的不是内置类型，而是自定义类型，例如日期类，那么当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问Date的成员：

	list<Date> lt;
	Date d1(2021, 8, 10);
	Date d2(1980, 4, 3);
	Date d3(1931, 6, 29);
	lt.push_back(d1);
	lt.push_back(d2);
	lt.push_back(d3);
	list<Date>::iterator pos = lt.begin();
	cout << pos->_year << endl; //输出第一个日期的年份

 讲到这里，可能你会觉得不对，按照这种重载方式的话，这里使用迭代器访问日期类当中的成员变量时不是应该用两个->吗？

这里本来是应该有两个->的，第一个箭头是pos ->去调用重载的operator->返回Date* 的指针，第二个箭头是Date* 的指针去访问对象当中的成员变量_year。

但是一个地方出现两个箭头，程序的可读性太差了，所以编译器做了特殊识别处理，为了增加程序的可读性，省略了一个箭头。

总结：迭代器全函数

    //迭代器类
    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* n)
            :_node(n)
         {}

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

        Ref operator*()
        {
            return _node->_data;
        }
        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;
        }

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

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

list的模拟实现

在通过上面的结点类与迭代器类的模拟实现后，list也趋于完整了，我们只需要对一些普遍的容器函数进行编写即可

默认成员函数

构造函数

首先得申请一个头节点，让头节点的前指针和后指针都指向自己就好了

为了在以后的默认成员函数能够更方便的申请头结点并构造，这里引入一个初始化函数empty_init

        //副构造函数
        void empty_init()
        {
            _head = new node;
            _head->_next = _head;
            _head->_prev = _head;
        }


        //主构造函数
        list()
        {
            empty_init();
        }

拷贝构造函数

首先创建一个头节点，然后在用for循环将需要拷贝的list依靠push_back函数依次拷贝到新的list

        //拷贝构造函数  it2(it1)
        list(list<T>& it)
        {
            empty_init();
            for (auto e : it)
            {
                push_back(e);
            }
        }

赋值重载运算符

这里直接进行传值传参，首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换

例如 it1 = it2

这里直接传值，是为了不改变原有的it2，直接修改it1

        // it1 = it2;
        list<T>& operator=(list<T> it)
        {
            swap(it);
            return *this;
        }

析构函数

首先将用clear函数将list清空，然后释放头节点，最后让头节点置空即可

        //析构函数
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

迭代器相关函数

迭代器的begin是指第一个有效数据，end是指最后一个有效数据的下一个位置

所以begin是头节点的下一个位置，也就是_head->_next

end是最后一个有效数据的下一个位置，也就是头节点，所以就是_head

begin函数

        //迭代器指针
        iterator begin()
        {
            return iterator(_head->_next);
        }
        const_iterator begin() const
        {
            return const_iterator(_head->_next);

end函数

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

访问相关函数

front函数

back函数

修改容器相关函数

insert函数

先找到要插入结点的前一个结点，然后与pos结点建立联系，再与前一个结点建立联系即可

        void insert(iterator pos,const T& x)
        {
            node* cur = pos._node;//找到pos结点
            node* prev = cur->_prev;//找到前一个结点

            node* new_node = new node(x);//开辟新结点
            
            //与前结点建立连接
            prev->_next = new_node;
            new_node->_prev = prev;
            //与后结点建立连接
            new_node->_next =cur;
            cur->_prev = new_node;
        }

erase函数

首先检查pos指针是否合法，也就是是否为头结点，然后找到pos的前一个结点与后一个结点，然后让两个结点建立连接，再删除pos所在的结点即可，然后返回后一个结点的迭代器

        //删除函数
        iterator erase(iterator pos)
        {
            assert(pos != end());//检查
            node* prev = pos._node->_prev;//找到前一个结点
            node* next = pos._node->_next;//找到后一个结点

            //建立连接
            prev->_next = next;
            next->_prev = prev;
            delete[] pos._node;//删除pos结点
            return iterator(next);//返回后一个结点的迭代器
        }

push_back和pop_back函数

因为有了insert函数和erase函数，所以可以复用这两个函数即可

        //尾删
        void push_back(const T& x)
        {
            insert(end(), x);//在头结点前插结点
        }


        //头删
        void pop_back()
        {
            erase(--end());//删除头节点的前一个结点
        }

push_front和pop_front函数

因为有了insert函数和erase函数，所以可以复用这两个函数即可

        //头插
        void push_front(const T& x)
        {
            insert(begin(), x);//在第一个有效数据前插入结点
        }

        //头删
        void pop_front()
        {
            erase(begin());//删除第一个有效数据
        }

其他函数

size函数

通过遍历的形式获取该list的有效数据大小

size_t size() const
{
	size_t sz = 0; //统计有效数据个数
	const_iterator it = begin(); //获取第一个有效数据的迭代器
	while (it != end()) //通过遍历统计有效数据个数
	{
		sz++;
		it++;
	}
	return sz; //返回有效数据个数
}

resize函数

模拟实现了string与vector之后，相信大家都很清楚resize的用法了

void resize(size_t n, const T& val = T())
{
	iterator i = begin(); //获取第一个有效数据的迭代器
	size_t len = 0; //记录当前所遍历的数据个数
	while (len < n&&i != end())
	{
		len++;
		i++;
	}
	if (len == n) //说明容器当中的有效数据个数大于或是等于n
	{
		while (i != end()) //只保留前n个有效数据
		{
			i = erase(i); //每次删除后接收下一个数据的迭代器
		}
	}
	else //说明容器当中的有效数据个数小于n
	{
		while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n
		{
			push_back(val);
			len++;
		}
	}
}

clear函数

clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。

        //清除函数
        void clear()
        {
            iterator it = begin();
            while (it != end())
            { 
                erase(it);
            }
        }

empty函数

empty函数用于判断容器是否为空，我们直接判断该容器的begin函数和end函数所返回的迭代器，是否是同一个位置的迭代器即可。（此时说明容器当中只有一个头结点）

bool empty() const
{
	return begin() == end(); //判断是否只有头结点
}

swap函数

swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

        void swap(list<int>& tmp)
        {
            std::swap(_head, tmp._head);
        }