listvectorvectorlistmy_list_0">前言：各位老铁好久不见了，今天分享的知识是自己实现一个简单的list容器，为什么我先跳过vector容器的自我实现呢？我个人觉得vector相对于list的自我实现简单一点，所以今天先分享实现my_list的知识
listlistlist_2">我们要实现my_list，首先我们要知道list有那些常用的接口，我们先看一看实现list的文档
list/list/?kw=list" rel="nofollow">实现list容器文档入口
list容器有这么多接口，我会从里面挑出常用的接口进行模拟实现。
list_7">list实现(这里讲的是带头的双向循环链表)
listlistlistmy_list_8">我们在数据结果中已经学习过list了，知道list内部结果主要包含三部分，一是存放的值，二是链接前面一个结点的指针，三是链接后面一个结点的指针。由于库里面也有已经实现好了的list，为了防止my_list和库里面的冲突，我们需要搞个命名空间封装起来，命名空间的名字随便用。
namespace ljy
{}
listlistlist_16">由于我们不知道list容器的类型是什么类型，所以我们需要搞个模板函数，对任意类型的list都适用。然后我们需要搞个类(私有的比较好，防止其他人修改成员变量)把list里面的成员给封装起来
namespace ljy
{template<class T>struct _list_node{_list_node<T>* _prev;_list_node<T>* _next;T _data;//任意类型的数据};
}
接下来我们需要把链表给初始化
namespace ljy
{template<class T>struct _list_node{_list_node<T>* _prev;_list_node<T>* _next;T _data;//任意类型的数据_list_node(const T& x = T())//这里是构造一个空的对象来充当缺省参数，防止没有提供参数从而导致编译器报错:_data(x), _prev(nullptr), _next(nullptr){}};
}
listlistlist_50">由于list不支持随机访问，我们只能通过迭代器进行访问list中的结点。所以我们先来实现list的迭代器的接口。
由于list迭代器底层是一个指针，所以我们如果需要访问list和修改list,就需要对指针进行解引用和取地址,因此我给list迭代器模板参数定义三个参数，一个是有关数据类型(T)，一个是解引用(Ref),一个是取地址(Ptr)
//迭代器
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迭代器进行初始化
_list_iterator(Node* node):_node(node)
{}
我们需要分清对指针的*和->，一个是对指针解引用(表示取向指针指向的值)，另一个是对指针取地址(表示指向结点的本身)
//*Ref operator*(){return _node->_data;}
//->
Ptr operator->()
{return &_node->_data;
}
再接下来我们实现++和- -运算符的重载，++和- - 分为前置++，前置- -，后置++和后置- -。前置和后置的区别是是否先返回值再进行++和- -
前置++
//前置++
Self& operator++()//返回的是this指针,出了作用域还存在，所以用引用返回
{_node = _node->_next;return *this;
}
后置++
//后置++ 返回的是中间变量，出了作用域就不存在了，不需要使用引用返回
Self operator++(int)//在形参里面+int是为了和前置++区别开来。
{Self tmp(this);++(*this);return tmp;
}
前置- -
//前置--
Self& operator--()
{_node = _node->_prev;return *this;
}
后置- -
//后置--
Self operator--(int)
{Self tmp(this);_node = _node->_prev;return tmp;
}
然后再实现==和!=运算符重载
==运算符重载
bool operator==(const Self& lt)
{return _node == lt._node;
}
!=运算符重载
bool operator!=(const Self& lt)
{return _node != lt._node;
}
到这里list的迭代器就完成了。
list_154">接下来就到list的一些常用接口的实现
list的框架
template <class T>class list{typedef _list_node<T> Node;public:typedef _list_iterator<T,T*,T&> iterator;//普通迭代器typedef _list_iterator<T, T*, T&> const_iterator;//const迭代器private:Node* _head;};
返回头节点
//双向带头的循环链表(可修改头节点的位置和头节点指向的值)
iterator begin()
{//开始的结点在头节点的下一个结点//通过迭代器迭代寻找结点return iterator(_head->_next);
}
//通过const迭代器迭代寻找结点(不可修改头节点的位置和头节点指向的值)
const_iterator begin() const
{return const_iterator(_head->_next);
}
//双向带头的循环链表(可修改尾节点的位置和尾节点指向的值)
iterator end(){//头结点指向的位置就是end位置return iterator(_head);}
//通过const迭代器迭代寻找结点(不可修改尾节点的位置和尾节点指向的值)
const_iterator end() const
{return const_iterator(_head);
}
然后实现在任意位置插入数据的接口
//在pos位置前插入数据void insert(iterator pos,const T& x){//先找出当前的结点Node* cur = pos._node;Node* prev = cur->_prev;//再开辟出一个新的结点Node* newnode = new Node(x);//再把prev newnode cur三个结点按前后顺序链接起来prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}
再在任意插入位置插入数据的接口基础上实现头插和尾插
头插：就是在begin前一个位置插入
//头插
void push_front(const T& x)
{//直接在begin()前面的位置进行插入insert(begin(), x);
}
尾插：就是在头结点前一个位置进行插入，头节点前一个位置就是末尾
//从尾部插入数据void push_back(const T& x){//end()就是头节点的前一个位置，也就是尾部return (end(), x);}
到这里插入数据的接口我们就实现完了，有插入数据必然就会有删除数据，所以接下来我们就开始实现删除数据。
首先我们先实现在任意位置删除数据，在文档中erase删除数据是将数据删除后返回当前数据的下一个位置。
//在任意位置删除数据void erase(iterator pos, const T& x){//不能把头节点删除assert(pos != end());//先保存当前结点Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;delete cur;//再把结点链接起来prev->_next = next;next->_prev = prev;}
然后在在任意位置删除数据的接口的基础上，再实现头删和尾删。
头删：begin()函数返回的位置就是头
void pop_front(const T& x)
{erase(begin(), x);
}
尾删：end()函数获取的位置是尾结点的下一个位置，只要先给end()函数- -就能找到尾结点从而删掉尾结点。
//尾删
void pop_back(const T& x)
{erase(--end());
}
listlist_293">list的删除数据接口到这里就完成了，然后我们再给list写初始化函数(个人习惯，先写完接口再写初始化)，构造函数，拷贝构造函数，赋值运算符重载，析构函数。
构造函数：由于我们我们这里的list是双向带头循环的链表，所以我们需要先开辟一个头节点出来，把头结点和自身链接起来。
list()
{//new出一个头结点_head = new Node;//让头节点指向自己_head->_next = _head;_head->_prev = _head;
}
拷贝构造函数：
//拷贝构造
//lt2(lt1)
list(const list<T>& lt)//传一个类对象过来
{//先构造出一个和lt一模一样的头节点，然后再直接把lt的数据插入到lt2中_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto e : lt){push_back(e);//这里其实是this->push_back()}
}
赋值运算符重载(现代写法：借助第三方实现相对应的功能，再把原来的和第三方进行交换)
//operator=
//lt3=lt2
list<T>& operator=(list<T> lt)//这里创建对象借助了拷贝构造，lt2通过lt1进行拷贝构造
{//直接把lt3和lt2的头结点进行交换就可以了swap(_head = lt._head);//再返回this指针return *this;
}
