1.list易错点
（1）慎用list的sort，list的排序比vector慢得多，尽管两者时间复杂度一样，甚至不如先把list转为vector，用vector排完序后再转为list
（2）splice是剪切链表，将x的部分剪切到pos后，也可以自己剪自己的
（3）list迭代器不支持[]运算符，但相比较vector多支持了push_front和pop_front，原因在于[]效率不高，push_front和pop_front效率高
2.list模拟实现
list实现中我们会用到多个模板，注意每个template定义的模板参数都只能供当前类或函数使用，不存在一个文件中所有T都是一个意思
（1）结点
为了适应不同数据的存储，我们采用模板的方式来定义结点。为了能够体现封装特性，我们将创建结点并赋值作为一个构造函数写入类ListNode中。因为在接下来的class list中会频繁调用lt->next，即在外部访问LIstNode的成员变量，所以我们的ListNode使用struct，默认访问限定符是public
（2）无参构造和析构
我们的list是带头双向循环链表，所以所有的构造都需要定义一个哨兵位
还有很多带参的构造，虽然这里我们可以去实现，但是它们需要使用到的功能和后面的函数相符合，所以我会先实现后续的函数。
析构只需要遍历所有节点，将它们释放即可
（3）迭代器
list的迭代器和指针就拉开了差距，list的数据是不连续存储的，因此无法使用指针的加减来遍历list。我们需要定义一个iterator的类，在这个类里重载运算符++、*等操作，使它们在使用过程中和指针一致但能够正常访问数据。
我们使用ListNode*作为结点的标识，当++时就调用它的_next，--就调用它的_prev，*就返回对应_data的值。有了这个思路，迭代器的大部分功能我们都可以顺利实现了。
template<class T, class T1 = T>
struct List_iterator
{
typedef ListNode<T> Node;
typedef List_iterator<T, T1> iterator;
List_iterator(Node* node)
:_curnode(node)
{}
iterator operator++()
{
_curnode = _curnode->_next;
return _curnode;
}
iterator operator--()
{
_curnode = _curnode->_prev;
return _curnode;
}
iterator operator++(int)
{
_curnode = _curnode->_next;
return _curnode->_prev;
}
iterator operator--(int)
{
_curnode = _curnode->_prev;
return _curnode->_next;
}
T1& operator*()//对于const T无法进行修改
{
return _curnode->_data;
}
T1* operator->()//对于const T无法进行修改
{
return &(_curnode->_data);
}
bool operator!=(const List_iterator lt) const
{
return _curnode != lt._curnode;
}
bool operator==(const List_iterator lt) const
{
return _curnode == lt._curnode;
}
Node* _curnode;
};
但是这里面还有一些代码需要解释
a.operator->()
要理解这里，我们要思考迭代器本身想要模仿的是指向数据的指针，如果存储类型是int，对应iterator和int*的使用方式一模一样，类似地，像char、double、int*等内置类型是这样，那么自定义类型呢？operator->()就是为了模仿自定义类型的指针而专门设计的。
我们先将T1就看成T，T是一个结构体，里面有自己的成员变量，当我们使用结构体指针想要访问它们时，我们首先要拿到这个结构体的地址，再用->访问，这里的iterator也是如此，_data是结构体类型，我们直接先指向这个结构体内容本身，即_curnode->_data，这个表达式的返回值是一个结构体，也就是我们想要访问的结构体，但是我们是要模拟指针的操作，要使用->而不是.，所以我们要再对它取地址，即&(_curnode->_data)，这样返回的就是一个指向_data的指针了，当我们调用it.operator->()->(成员变量)时就能访问结构体内部的成员变量了，简化为it->(成员变量)，省略了一个->为了易读性。
b.T1和T的区分
在我们想要创建一个const_iterator时，T1的出现就很重要了。
当不传第二个模板参数时，默认和第一个一样，如果传了const T，那就使用传的参数
对于这两个要返回指针或引用的函数，加上const修饰T可以防止T被修改。那为什么不直接用const T一个参数呢？要注意const int和int是两个类型，对于一些自定义类型来说有很大区别，所以要分成两块来写。
有了上面的基础，反向迭代器也可以很快的完成，思路就是复用，用刚刚实现的正向迭代器稍加修改得到。
template<class T, class T1 = T>
struct List_reverse_iterator
{
typedef ListNode<T> Node;
typedef List_iterator<T, T1> iterator;
typedef List_reverse_iterator<T, T1> reverse_iterator;
List_reverse_iterator(Node* node)
:_it(node)
{}
List_reverse_iterator(iterator it)
:_it(it)
{}
reverse_iterator operator++()
{
return --_it;
}
reverse_iterator operator--()
{
return ++_it;
}
reverse_iterator operator++(int)
{
return _it--;
}
reverse_iterator operator--(int)
{
return _it++;
}
T1& operator*()//对于const T无法进行修改
{
return *_it;
}
T1* operator->()//对于const T无法进行修改
{
return &(*_it);
}
bool operator!=(const List_reverse_iterator lt) const
{
return _it != lt._it;
}
bool operator==(const List_reverse_iterator lt) const
{
return _it == lt._it;
}
iterator _it;
};（4）push_back
push_back是非常关键的一个函数，在构造函数中，我们经常用到它
先用val创建一个newnode，找到尾节点并修改尾节点和哨兵位的_prev和_next使得newnode插入链表中
（5）insert
我们实现insert的方式是先实现一个可复用性最强的函数（迭代器版本的insert），再用它实现其它函数
后续的函数只需要调整参数复用即可
iterator insert(iterator pos, int n, int val)//特殊处理，防止定位错误
{
return insert(pos, (size_t)n, (T)val);
}
iterator insert(iterator pos, size_t n, const T& val)
{
list<T> tmp;
for (size_t count = 0; count < n; count++)
{
tmp.push_back(val);
}
return insert(pos, tmp.begin(), tmp.end());
}
iterator insert(iterator pos, const T& val)
{
return insert(pos, 1, val);
}其中有一个函数需要解释
当我们调用insert(lt.begin(), 1, 3)时，是想在首位置插入1个3，但是编译器会将1，3识别成迭代器（注意看我们之前已经实现了模板函数，1和3同类型是会匹配的），size_t和const int&虽然都能作为1和3的类型，但它们都不叫完美匹配，不完美匹配就会去找模板函数。
注意各大整型家族的区别，10u是unsigned int类型。
因此我们只有针对这一种情况进行单独处理，将它们强转后就可以匹配正确的函数了。
（6）erase
我们的思路也是先实现一个可复用性最强的，再对其它函数复用。这些函数逻辑都很简单，不做过多讲解。
（7）带参构造
这里我们就可以发现，只要有了push_back，insert，我们实现这些带参构造就很快了，我们要学会复用，即实现最关键的几个函数，其它的函数用这几个核心的函数套用就可以了，这不仅节省了我们的时间，还使得代码易于维护，失误率降低。
list(size_t n, const T& val)
{
_head = new Node;
_head->_next = _head->_prev = _head;
for (size_t count = 0; count < n; count++)
{
push_back(val);
}
}
list(const list<T>& lt)
{
_head = new Node;
_head->_next = _head->_prev = _head;
for (const auto& e : lt)
{
push_back(e);
}
}
template<class Init>
list(Init first, Init last)
{
_head = new Node;
_head->_next = _head->_prev = _head;
insert(begin(), first, last);
}
（8）全部代码（包含一些边缘性的函数）
注意模板函数是按需实例化，只检查调用的实例化的函数，不调用就不实例化
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
namespace my_list
{
template<class T>
struct ListNode
{
ListNode(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{}
T _data;
ListNode<T>* _next;
ListNode<T>* _prev;
};
template<class T, class T1 = T>
struct List_iterator
{
typedef ListNode<T> Node;
typedef List_iterator<T, T1> iterator;
List_iterator(Node* node)
:_curnode(node)
{}
iterator operator++()
{
_curnode = _curnode->_next;
return _curnode;
}
iterator operator--()
{
_curnode = _curnode->_prev;
return _curnode;
}
iterator operator++(int)
{
_curnode = _curnode->_next;
return _curnode->_prev;
}
iterator operator--(int)
{
_curnode = _curnode->_prev;
return _curnode->_next;
}
T1& operator*()//对于const T无法进行修改
{
return _curnode->_data;
}
T1* operator->()//对于const T无法进行修改
{
return &(_curnode->_data);
}
bool operator!=(const List_iterator lt) const
{
return _curnode != lt._curnode;
}
bool operator==(const List_iterator lt) const
{
return _curnode == lt._curnode;
}
Node* _curnode;
};
template<class T, class T1 = T>
struct List_reverse_iterator
{
typedef ListNode<T> Node;
typedef List_iterator<T, T1> iterator;
typedef List_reverse_iterator<T, T1> reverse_iterator;
List_reverse_iterator(Node* node)
:_it(node)
{}
List_reverse_iterator(iterator it)
:_it(it)
{}
reverse_iterator operator++()
{
return --_it;
}
reverse_iterator operator--()
{
return ++_it;
}
reverse_iterator operator++(int)
{
return _it--;
}
reverse_iterator operator--(int)
{
return _it++;
}
T1& operator*()//对于const T无法进行修改
{
return *_it;
}
T1* operator->()//对于const T无法进行修改
{
return &(*_it);
}
bool operator!=(const List_reverse_iterator lt) const
{
return _it != lt._it;
}
bool operator==(const List_reverse_iterator lt) const
{
return _it == lt._it;
}
iterator _it;
};
template<class T>
class list
{
public:
typedef ListNode<T> Node;
typedef List_iterator<T> iterator;
typedef List_iterator<T, const T> const_iterator;
typedef List_reverse_iterator<T> reverse_iterator;
typedef List_reverse_iterator<T, const T> const_reverse_iterator;
list()
{
_head = new Node;
_head->_next = _head->_prev = _head;
}
list(size_t n, const T& val)
{
_head = new Node;
_head->_next = _head->_prev = _head;
for (size_t count = 0; count < n; count++)
{
push_back(val);
}
}
list(const list<T>& lt)
{
_head = new Node;
_head->_next = _head->_prev = _head;
for (const auto& e : lt)
{
push_back(e);
}
}
template<class Init>
list(Init first, Init last)
{
_head = new Node;
_head->_next = _head->_prev = _head;
insert(begin(), first, last);
}
~list()
{
Node* cur = _head->_next, * next = _head->_next->_next;
while (cur != _head)
{
delete cur;
cur = next, next = next->_next;
}
delete _head;
_head = nullptr;
}
size_t size()
{
size_t count = 0;
for (const auto& e : *this)
{
count++;
}
return count;
}
bool empty()
{
return _head->_next == _head;
}
list<T>& operator=(const list<T>& lt)
{
if (lt._head != _head)
{
clear();
for (const auto& e : lt)
{
push_back(e);
}
}
return *this;
}
T& front()
{
return *begin();
}
T& back()
{
return *(--end());
}
const T& front() const
{
return *begin();
}
const T& back() const
{
return *(--end());
}
void swap(const list<T>& lt)
{
std::swap(_head, lt._head);
}
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);
}
reverse_iterator rbegin()
{
return reverse_iterator(_head->_prev);
}
reverse_iterator rend()
{
return reverse_iterator(_head);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(_head->_prev);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(_head);
}
void push_back(const T& val)
{
Node* newnode = new Node(val);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& val)
{
insert(begin(), 1, val);
}
void pop_front()
{
erase(begin());
}
void pop_back()
{
erase(--end());
}
template<typename Input>
iterator insert(iterator pos, Input first, Input last)
{
Node* cur = pos._curnode->_prev, * next = cur->_next;
Node* ret = cur;
while (first != last)
{
Node* newnode = new Node((T)(*first));
cur->_next = newnode, newnode->_prev = cur;
newnode->_next = next, next->_prev = newnode;
cur = cur->_next;
first++;
}
return ret->_next;//新插入的第一个结点对应的迭代器，有隐式类型转换
}
iterator insert(iterator pos, int n, int val)//特殊处理，防止定位错误
{
return insert(pos, (size_t)n, (T)val);
}
iterator insert(iterator pos, size_t n, const T& val)
{
list<T> tmp;
for (size_t count = 0; count < n; count++)
{
tmp.push_back(val);
}
return insert(pos, tmp.begin(), tmp.end());
}
iterator insert(iterator pos, const T& val)
{
return insert(pos, 1, val);
}
iterator erase(iterator first, iterator last)
{
Node* cur = first._curnode->_prev, * next = last._curnode;
iterator nextit = first;
while (first != last)
{
nextit++;
delete first._curnode, first = nextit;
}
cur->_next = next, next->_prev = cur;
return cur->_next;
}
iterator erase(iterator pos)
{
iterator cur = pos;
return erase(pos, ++cur);
}
void clear()
{
erase(begin(), end());
}
private:
Node* _head;
};
}