list的模拟实现（模仿STL）

目录

一、模拟实现前的准备

1.list结构认识

2.迭代器的实现不同

3.如何实现需要的功能

二.结点类实现

三.迭代器实现

1.实现前的问题

2._list_iterator类的成员变量和构造函数

3.*和->运算符重载

4.前置++和后置++的实现

5.前置--和后置--

6.==和!=运算符重载

四.list类的实现

1.list类和构造函数

2.析构

3.拷贝构造函数

4.赋值运算符重载

5.迭代器

6.insert()

7.erase()

8.clear()

9.头插头删，尾插尾删

10.判空

五.完整代码

---

一、模拟实现前的准备

1.list结构认识

1.STLe的list的底层结构其实是带头结点的双向循环链表，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

 

2.迭代器的实现不同

list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响。list的迭代器是自定义类型对原生指针的封装，模拟指针的行为，那为什么不像vector那样直接用原生指针呢？因为list的每个结点在物理结构上面不是连续的，直接对结点++，其得到的不是下一个结点指针。

3.如何实现需要的功能

这里我们可以用三个类来模拟实现，结点类和list迭代器类用struct封装，因为我们不需要对其做访问限制，而list类就用class类封装。

 

二.结点类实现

结点类实现比较简单，不过我们需要注意：

（1）需要用到模板，方便以后使用不同的类型；

（2）结点成员变量包括，结点值、指向前一个结点的指针，指向后一个结点的指针；

（3）不需要析构函数（没有额外申请空间）；

（4）用struct来实现，对访问不做限制

template<class T>                 //list的结点结构，对访问不做限制，所以用structstruct list_node{list_node<T>* _next;       //成员变量list_node<T>* _prev;T _data;list_node(const T& x = T())       //构造函数:_next(nullptr), _prev(nullptr), _data(x){}};

三.迭代器实现

list的迭代器实现是整个实现过程中最精彩的部分，尤其是模板里的多个参数，可谓是把规则用到了极致，涉及到的知识点也非常多，我们不得不感叹STL大佬的实力。

1.实现前的问题

迭代器分为普通迭代器和const迭代器，之前的迭代器由于是直接用的原生指针，所以就算两种迭代器分开实现，其代码量夜很小。但是对于_list_iterator类要实现的普通的_list_iterator和const版本的_list_const_iterator，因为对于两个类中的部分函数有普通函数和const函数之分（如begin( )和end( )），其他并无区别。因为这两个类的大部分代码相似，那么怎么解决呢？

查看STL源码，我们可以发现，用下面的方法非常不错：

迭代器模板用到了三个参数

template<class T, class Ref, class Ptr>

list在实例化时，通过不同的参数实例出两个类，一个是普通的不带const的T，T&， T*，另一个是带const的T，const T&， const T*，其中Ref是引用，Ptr是指针，该类模板实例化了以下这两个类模板：

typedef __list_iterator<T, T&, T*> iterator;   //非const 迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;     //const迭代器

这样我们就解决了代码冗余的问题（大佬不愧是大佬）。

2._list_iterator类的成员变量和构造函数

成员变量只有结点node，构造函数负责初始化结点

template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;                                         //typedef __list_iterator<T, Ref, Ptr> self;node* _node;                //成员变量__list_iterator(node* n)      //构造函数:_node(n){}};

3.*和->运算符重载

Ref operator*()
{
return _node->_data;     //解引用之后，我们需要得到拷贝的值，所以返回引用
}Ptr operator->()
{
return &_node->_data;    //结构体指针解引用，返回结点指针
}

注意：It->_data，（It是一个迭代器）我们平时这样用没问题，但是我们要知道这里其实省略了一个->,It->其实就是It.operator->()，其返回值是_data*类型，我们还需要It.operator->()->_data，但是为了可读性，编译器优化了一个箭头。

4.前置++和后置++的实现

self& operator++()            //都需要用到自身，所以是self
{
_node = _node->_next;
return *this;
}self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}

5.前置--和后置--

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

6.==和!=运算符重载

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

四.list类的实现

1.list类和构造函数

template<class T>class list                           //list类{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;                     //非const 迭代器typedef __list_iterator<T, const T&, const T*> const_iterator;       //const迭代器//typedef __list_const_iterator<T> const_iterator;list(){_head = new node;                    //默认构造函数_head->_next = _head;_head->_prev = _head;}private:node* _head;  };

2.析构

复用了后面的函数

        ~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

3.拷贝构造函数

        void empty_init()          //空初始化{_head = new node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}

4.赋值运算符重载

（1）现代的赋值运算符重载

void swap(list<T>& tmp){std::swap(_head, tmp._head);}list<T>& operator=(list<T> lt){swap(lt);return *this;}

在执行赋值运算符重载时，会调用拷贝构造函数执行深拷贝，然后再交换两个链表头节点的指针，把this要释放的资源交给临时对象，临时对象出了swap的函数作用域就被this要释放的资源也会被同时释放。

5.迭代器

        iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);     //匿名对象}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head->_next);//return it;return const_iterator(_head);}

6.insert()

先构造一个结点，然后插入

        void insert(iterator pos, const T& x){node* cur = pos._node;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;}

7.erase()

删除后，需要返回删除位置的下一个结点

        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;return iterator(next);}

8.clear()

不能把哨兵卫清理了，否则链表就不存在了

        void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

9.头插头删，尾插尾删

这里直接复用insert()和erase()

        void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}

10.判空

bool empty()
{return end()==begin();
}

五.完整代码

        #pragma once
#include<assert.h>
#include<iostream>namespace bit
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};// 1、迭代器要么就是原生指针// 2、迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为template<class T, class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}Ptr 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;}};template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//typedef __list_const_iterator<T> const_iterator;iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{//iterator it(_head->_next);//return it;return const_iterator(_head);}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}// lt2(lt1)/*list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}// lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}void push_back(const T& x){/*node* tail = _head->_prev;node* new_node = new node(x);tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){node* cur = pos._node;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;}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;return iterator(next);}bool empty(){return end()==begin();}private:node* _head;};
}