C++修炼：list模拟实现
Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！
我的博客：<但凡.
我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》
欢迎点赞，关注！
目录
1、list的底层结构
2、list容器的构造
3、迭代器类的完善
4、list类的完善
4.1、迭代器操作
4.2、insert
4.3、erase
4.4、其他复用接口
4.5、初始化列表和拷贝构造
4.6、赋值运算符重载
4.7、析构函数
5、补充
1、list的底层结构
list底层是双向带头循环链表，这意味着我们可以高效的在list中插入，删除节点。但是不支持随机访问。如果我们想要获取特定位置的元素需要遍历链表。
2、list容器的构造
list的模拟实现我们需要三个类，第一个类是节点，我们先把节点类写出来：
namespace danfan
{
template
struct list_node
{
list_node* _next;
list_node* _prev;
T _data;
//构造函数
list_node(const T& val = T())
:_next(nullptr),
_prev(nullptr),
_data(val)
{
}
};
} 其中next指向后一个节点的地址，prev指向前一个节点的地址，data是这个节点存放的数据：
我们再大致写一下迭代器类：
template
struct list_iterator
{
typedef list_iterator iterator;
typedef list_node Node;
Node* _node;//迭代器指向的节点的地址
list_iterator(Node* node)
:_node(node)
{
}
}; 我们这里其实需要三个模板变量，至于为什么需要三个我后面会说。
我们发现其实迭代器类和节点类都是用struct封装的，原因就在于我们实际在访问的时候不回去访问这个底层的节点，那就没必要把他设置成私有变量，那就用不到struct，用class就足够了。
接着我们再来写一下list类：
template
class list
{
typedef list_node Node;
typedef list_iterator iterator;
typedef list_iterator const_iterator;
void empty_list(const T& val=T())
{
_head = new Node;//别忘了开空间
_head->_next = _head;
_head->_prev = _head;
_head->_data = val;//默认为0
_size = 0;
}
list()
{
empty_list();
}
private:
Node* _head;
size_t _size;
}; _size的用途就是可以返回链表的大小。
3、迭代器类的完善
我们回过头来完善一下迭代器类
template
struct list_iterator
{
typedef list_iterator iterator;
typedef list_node Node;
Node* _node;//迭代器指向的节点的地址
list_iterator(Node* node)
:_node(node)
{
}
iterator operator++()
{
_node = _node->_next;
return _node;
}
iterator operator++(int)
{
iterator tmp(this->_node);
_node = _node->_next;
return tmp;
}
iterator operator--()
{
_node = _node->_prev;
return _node;
}
iterator operator--(int)
{
iterator tmp(this->_node);
_node = _node->_prev;
return tmp;
}
ref operator*()
{
return _node->_data;
}
ptr operator->()
{
return &_node->_data;
}
bool operator!=(const iterator& s) const
{
return _node != s._node;
}
bool operator==(const iterator& s) const
{
return _node == s._node;
}
}; 我们需要把对于迭代器的操作，主要是加减，等于，不等于，解引用，->写出来。我们注意到我们的比较操作符没有大于和小于，因为我们在一开始就说过了，list的迭代器在内存上没有地址的大小关系，所以说不能用大于和小于号来比较。另外迭代器加减，不等于，解引用这三个是必须提供的，只有这三个提供了才能使用范围for。
另外写注释的是我们的->运算符重载，这个运算符重载其实是在特定场景使用的。他主要是在list存储自定义类的时候使用。比如我们可以这样访问：
struct A
{
int _a;
int _b;
A(int a, int b)
:_a(a),
_b(b)
{
}
};
list li;
auto it = li.begin();
cout << it->_a << endl;假设我们的begin()接口已经实现完了，那么我们就可以通过->符号访问元素。这里按道理来说应该是->->两个符号才能访问-a，但是由于可读性的问题，省略了一个->符号，所以只剩下一个 -> 也可以正常访问。这个地方属于是特殊处理。
因为咱们的迭代器有const和非const两个版本，所以我们直接在模板迭代器类传入三个模板参数，其中第二个参数和第三个参数是T&,T*或const T&,const T*。这样我们在list类中可以根据我们typedef的迭代器类型来让编译器自己决定返回迭代器的类型。
4、list类的完善
4.1、迭代器操作
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}4.2、insert
我们先实现insert因为后面的push_back可以复用insert，之后有很多接口又复用的push_back。list的insert实际上是在提供的迭代器位置之前插入元素。
push_back我就一起在这里实现了。
void insert(iterator pos,const T& val)
{
Node* cur= pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
++_size;//别忘了
}
void push_back(const T& x)
{
insert(end(), x);
}4.3、erase
iterator erase(iterator pos)
{
assert(pos != end());//pos不能是最后一个元素
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
--_size;
return next;
}注意点很多我们从上往下说：
首先我们一定得断言一下，但需要注意断言不能写成pos
其次，不要忘记delete,不然会内存泄漏。
第三点，我们一定得返回迭代器，因为删除之后会有迭代器失效的问题，原来的那个迭代器位置的节点我们已经删除了。我们返回next会调用赋值拷贝一个迭代器。这个赋值拷贝是必须存在的，因为如果穿引用返回的话我们的next出函数时候生命周期就结束了。
4.4、其他复用接口
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
size_t size()
{
return _size;
}4.5、初始化列表和拷贝构造
实际上我们应该先实现拷贝构造才能进行以上我们实现的这些接口。
list(list& li)
{
empty_list();
for (auto& e : li)
{
push_back(e);
}
}
list(std::initializer_list il)
{
empty_list();
for (auto& e : il)
{
push_back(e);
}
} 4.6、赋值运算符重载
这里还是采用复用swap的写法。
void swap(list li)
{
std::swap(_head,li._head);
std::swap(_size,li._size);
}
list& operator=(list li)
{
swap(li);
return *this;
} 4.7、析构函数
void clear()
{
iterator it1 = begin();
for (it1 != end())
{
it1=erase(it1);//防止迭代器失效
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}5、补充
我们实际上只实现了几个常用的接口，那些不常用的我们并没有实现。
我们现在补充一下关于迭代器的知识点： 
迭代器分为以上几种，我们在调用各种接口的时候实际上是按照要求传入迭代器的。
随机访问迭代器支持读取，写入，递增递减，随机访问，多次遍历。比如我们vector的迭代器就是随机访问迭代器。
双向迭代器不支持随机访问，我们不能直接跳转到指定位置，只能通过遍历找到指定位置。list迭代器就是双向迭代器。
前向迭代器在和双向迭代器相比又不支持递减操作。单链表，还有之后的哈希表就是前向迭代器。
剩下的两个迭代器就是只读和只写迭代器。
这五个迭代器都具有父子集关系，如果一个接口要求传入前向迭代器，那么传入他的父集双向迭代器和随机访问迭代器也可以。但是反过来如果一个接口要求传入随机访问迭代器，就只能传入随机访问迭代器，传入他的子集（也就是剩下那四个迭代器）是不行的。（比如sort）。
如果要求传入只读和只写就是传剩下三个迭代器都可以。只读和只写迭代器没有具体的例子。
好了，今天的内容就分享到这，我们下期再见！
