list的优缺点
list的底层是双向链表，相比于之前底层是数组的string，vector，list的缺点是无法通过位置来直接访问元素，因为内存分配不连续；以及底层的迭代器需要封装指针才能实现++，*等逻辑的正确性。优点是 当已知插入/删除位置的迭代器，进行插入，删除元素时仅需改变前后指针的指向；以及list迭代器稳定，插入新节点时不必移动已有节点，迭代器不会失效。
对list双向链表进行拆分成三类，
第一类list_node
，链表中的节点list_node，包括本身存储的数据，以及指向下一个，上一个 节点的指针
本身存储的数据类型是T，创建一个模板，
template<class T>
struct list_node//链表中的每个节点
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
};第二类list
，链表本身，包含多个节点list_node，以及链表中节点的个数_size
此时节点仅仅维护一个哨兵位_head，剩下的节点利用push_back等方法进行插入
template<class T>
class list
{
private:
list_node<T>* _head;
size_t _size;
};第三类一会再说，先进行节点插入到链表的操作，实现push_back,
namespace sxm
{
template<class T>
struct list_node//链表中的每个节点
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& data)//节点的构造函数
:_data(data)
,_prev(nullptr)
,_next(nullptr)
{ }
};
template<class T>
class list
{
public:
void push_back(const T& x)
{
list_node<T>* newnode = new list_node<T>(x);//先创建一个节点,并将存储的元素x传入，这时候
//就要对节点弄构造函数(第一个类)，用struct方便访问
//接下来对节点进行链接,tail newnode _head
list_node<T>* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
++_size;
}
list()//链表的构造函数
{
_head = new list_node<T>(T()); //创建一个_head的哨兵节点,注意！
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
private:
list_node<T>* _head;
size_t _size;
};
void test()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
list<int>::iterator it = a.begin();
while (it != a.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}注意，list链表的构造函数是先创建一个对象list_node，不能写成_head = new list_node()，而是要写成_head = new list_node(T()); 需要调用list_node的构造函数，而list_node中如果没有无参的构造函数，因为list_node一般要初始化_data，有参，会编译失败。这里不推荐list_node的无参构造，会导致_data的未定义行为
而T () 会创建一个T类型的临时对象，并调用T的默认构造函数，然后这个临时对象会作为list_node构造函数的参数，传递给 list_node(const T& val)，用于初始化节点的_data
_head = new list_node<int>(int());
// 等价于：new list_node<int>(0)，因为 int() 会初始化为 0
_head = new list_node<string>(string());
// 调用 string 的默认构造函数，初始化 data 为空字符串那这时如何用迭代器来遍历链表呢？
第三类，迭代器类(非const类)
，模拟指针行为，封装节点指针
为什么要有这一类？
拿刚刚的迭代器遍历来说，对节点指针进行解引用得到的是节点本身，拿不到节点里面存储的数据；对节点指针进行++，得不到下一个节点，节点在内存中存储是不连续的。
迭代器的本质是对遍历行为的抽象，让用户可以忽略底层的差异，用相同的方法遍历数组，链表等结构。
因此进行封装指针，重载++，*等运算符，提供begin(),end()等方法，供外部使用
先实现一个迭代器模板
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
Node* _node;
}；迭代器中的成员变量是一个当前节点指针，存储当前迭代器指向的节点，可以进行向前移动(_node>_prev)，向后移动(_node->_next)，访问当前元素(_node->_data)，通过这一个链表节点对运算符重载，来达到我们想要的目的
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
Node* _node;
Node* operator++()
{
_node = _node->_next;
return _node;
}
};可以这样写吗？返回一个list_node *_node？
不可以，因为这样会返回的是 节点指针，如果再次对这个指针进行++操作，不会是下一个指针，即无法再对迭代器进行后续操作。
将返回类型改成迭代器类型，返回值应返回迭代器本身，而不是结点指针
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
Node* _node;
list_iterator<T>& operator++()
{
_node = _node->_next;//迭代器的内部状态被修改，指向下一个节点
return *this;//为外部提供接口
}
list_iterator(Node *node)// // 接受节点指针的构造函数，允许从节点指针构造迭代器
:_node(node)
{}
};同理operator--
list_iterator<T>& operator--()
{
_node = _node->_prev;//更新内部迭代器
return *this;//返回给外部更新后的迭代器
}对*进行运算符重载
，直接对节点指针进行解引用得到的是节点本身，而非节点内存储的数据
T& operator*()
{
return _node->_data;
}以及operator!=/operator==
bool operator!=(const list_iterator<T>& s)
{
return _node != s._node;
}
bool operator==(const list_iterator<T>& s)
{
return _node == s._node;
}
接着进行插入在list类中实现迭代器begin(),end()
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
iterator begin()
{
iterator it = _head->_next;//调用 iterator 的构造函数创建一个临时对象，再将这个临时对象拷贝到 it 中
return it;
//return iterator(_head->_next);//直接调用迭代器的构造函数，创建一个临时的匿名迭代器对象
//return _head->next;
}
iterator end()
{
iterator it=_head;
return it;//最后一个元素的下一个位置
}
list()
{
_head = new list_node; //创建一个_head的哨兵节点
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
private:
list_node<T>* _head;
size_t _size;
};此时第三种写法return _head->_next;原本的类型是list_node<T>*，但函数的返回值类型是iterator，编译器会在list_iterator<T> 类中查找可以接收 list_node<T>* 作为参数的构造函数，会自动调用这个构造函数构造一个临时的 list_iterator<T> 对象（head->_prev 作为参数），返回一个转换后的iterator
对list进行完善
insert
在list类中实现指定位置之前的插入insert
void insert(iterator pos, const T& x)//prev newnode cur
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev= pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
}push_back
那这时，push_back可以变为
void push_back(const T& x)
{
insert(end(), x);
}push_front
push_front，在开头增加一个新节点
void push_front(const T& x)
{
insert(begin(), x);//_head->_next之前插入，即_head的下一个节点
}erase
erase的实现，从list中删除某个节点信息
void erase(iterator pos)// pos._node->_prev pos->_node pos._node->next
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
}pop_back
接着实现pop_back，删除链表中最后一个节点
void pop_back()
{
erase(--end());//_head->_prev
}pop_front
pop_front，删除第一个有效节点
void pop_front()
{
erase(begin());//_head->_next
}size
以及size
size_t size()
{
return _size;
}operator++(int),operator--(int)
后置--/++，返回值而不是迭代器的引用，因为核心是操作“先使用自增前的迭代器，再进行自增”，应该先返回自增前的值
list_iterator<T> operator--(int)
{
list_iterator<T> temp = *this;//this 是一个指向当前对象的指针list_iterator<T>* ; *this 代表的是当前的 list_iterator<T> 对象、
//浅拷贝就行，让新的迭代器 _node 指向同一个节点
_node = _node->_prev;
return temp;
}
list_iterator<T> operator++(int)
{
list_iterator<T> temp = *this;
_node = _node->_next;
return temp;
}我们看下面一段代码，我们定义了一个AA类类型，如果不重载流运算符<<的话，需要写成（*ita)._aa1才能插入到流中
struct AA
{
int _aa1 = 1;
int _aa2 = 1;
AA(int aa1,int aa2)
:_aa1(aa1)
,_aa2(aa2)
{ }
};
void test()
{
list<AA> lta;
lta.push_back(AA(1, 1));
lta.push_back(AA(2, 2));
lta.push_back(AA(3, 3));
lta.push_back(AA(4, 4));
list<AA>::iterator ita = lta.begin();
while (ita != lta.end())
{
cout << (*ita)._aa1 << ":" << (*ita)._aa2;
//ita是一个迭代器，lta->_data=AA，即*ita 返回的是 AA&，这个元素是一个 AA 类型的对象，
//而对象需要通过 . 运算符访问其内部成员,如_a1,_a2
++ita;
}
cout << endl;
}还有一种方法，用箭头运算符（ita->_aa1）访问。不过ita是迭代器类型，为了让迭代器像指针一样用 -> 访问元素成员，必须通过重载 operator-> 来实现
operator->
步骤1：迭代器的 operator-> 必须返回一个指针（如 AA*）
步骤2：编译器会用这个指针再次调用 -> 访问 _aa1 成员。
当写 ita->_aa1 时，编译器会自动展开为 (ita.operator->())->_aa1。但为了可读性，省略了后一个->
所以返回值应该是T*，&表示取地址
T* operator->()
{
return &(_node->_data);//返回 _node->_data 这个对象的内存地址，结果是 T* 类型的指针
}这样就可以进行->访问了
cout << ita->_aa1 << ":" << ita->_aa2<<" ";接下来我们看这样一段代码
//打印
template<class T>
void Print(const list<T>& v)
{
for (auto it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
}v是const容器时，表示容器里面的数据不能修改，调用v.begin()，应该返回一个const迭代器，但我们之前只实现了普通迭代器，v.begin()返回普通迭代器iterator，auto it自动推导成普通迭代器类型，编译会报错，v.begin()应该返回一个const_iterator类型的迭代器，保证不能修改。接下来我们进行const迭代器的操作。
刚刚介绍了非const迭代器，成员函数operator*/operator-> 的返回值都可以被修改；而非const迭代器要求不能通过迭代器修改元素
那我们是新建一个const_iterator类型，还是在iterator的基础上＋const 呢？const iterator
const iterator：指迭代器本身不能修改
const_iterator：指向内容不能修改
我们想要的非const迭代器是 指向的内容不能修改，而不是迭代器本身不能修改，因为迭代器需要进行++/--等操作进行移动，移动到下一个节点，因此定义一个const_iterator 迭代器
const迭代器只需要将operator*/operator-> 的返回值前面+const，表示返回值的指向内容不能修改
const迭代器
template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator<T> Self;
Node* _node;
list_const_iterator(Node* node)
:_node(node)
{}
Self& operator++()
{
_node = _node->_next;//更新迭代器内部存储的节点指针
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self temp = *this;
_node = _node->_prev;
return temp;
}
Self operator++(int)
{
Self temp = *this;
_node = _node->_next;
return temp;
}
const T& operator*()//返回你的别名，但返回的是const别名，将权限缩小了之后再返回，修改不了
{
return _node->_data;
}
const T* operator->()
{
return &_node->_data;//返回const指针
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};begin,end
以及const迭代器的begin，end
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef list_iterator<T> iterator;
typedef list_const_iterator<T> const_iterator;
iterator begin()
{
iterator it = _head->_next;
return it;
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin()const
{
const_iterator it = _head->_next;
return it;
}
const_iterator end()const
{
const_iterator it = _head;
return it;
}
};返回 const_iterator 解决的是 “迭代器能否修改元素” 的问题，而成员函数加 const 解决的是 “const 容器能否调用这个函数” 的问题。
但是这两类迭代器const与非const大部分代码都相似，单独写两个类太麻烦了，因此在这两个类的基础上再实现一个类，同一个类模板，增加两个模板参数来控制。
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
//T表示迭代器的元素类型，Ref表示operator*的返回值，T& or const T&，Ptr表示的是operator->的返回值，T* or const T*
typedef list_iterator<T, Ref, Ptr> Self;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
Self& operator++()
{
_node = _node->_next;//更新迭代器内部存储的节点指针
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self temp = *this;
_node = _node->_prev;
return temp;
}
Self operator++(int)
{
Self temp = *this;
_node = _node->_next;
return temp;
}
Ref operator*()//返回你的别名返回的是const别名，or 非const别名
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;//返回const指针
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
//通多指定不同的Ref 和 Ptr，让同一个list_iterator模板实例化出两种迭代器类型
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
iterator it = _head->_next;
return it;
}
iterator end()
{
return _head;
}
//const迭代器
const_iterator begin()const
{
const_iterator it = _head->_next;
return it;
}
const_iterator end()const
{
const_iterator it = _head;
return it;
}接下来看迭代器失效的问题
1.insert
不会引起迭代器失效的问题，每个节点是单独储存的，在pos节点之前插入新节点，但本身迭代器pos指向的节点_node仍然不变。
规范写的话，insert加上返回值，返回新插入节点的迭代器
iterator insert(iterator pos, const T& x)//prev newnode cur
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;//隐式类型转换
}2.erase
void erase(iterator pos)
被删除节点的迭代器pos会失效，pos->_node在函数结束后会被释放，但形参仍保留着pos迭代器的地址，如果进行++等操作，操作对象就是野指针。
比如删除一个偶数
void test()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
Print(lt);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
lt.erase(it);
}
it++;//it是野指针
}
}这样我们可以将erase函数设置一个返回值，返回下一个节点的迭代器。
iterator erase(iterator pos)// pos._node->_prev pos->_node pos._node->next
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}void test()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
Print(lt);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
it=lt.erase(it);
}
else
{
it++;
}
}
Print(lt);
}但其他迭代器不受影响，因为其他迭代器指向的节点地址都不会被改变。
继续完善list类
~list与clear
~list()//将节点一个一个的释放
{
clear();
delete _head;
_head = nullptr;
}
void clear()//不清除哨兵位
{
auto it = begin();
while (it != end())
{
it=erase(it);//it接收删除后的下一个迭代器
}
}实现深拷贝
//lt2(lt1),this是list2,lt1是list1
list(const list<T>& lt)
{
for (auto& e : lt)
{
push_back(e);//遍历原链表的每个元素，为每个节点创建新空间，
}
}不可以这样写，push_back的前提是得有一个哨兵位，使得_head不为nullptr，否则_head是一个野指针，无法进行插入
因为调用的是拷贝构造list<int>lt1(lt2)，构造函数不会再调用其他构造函数，拷贝构造也是构造函数，
因此我们委托构造，让拷贝构造先调用默认构造的逻辑，实现空链表的初始化
void empty_init()
{
_head = new list_node<T>(T()); //创建一个_head的哨兵节点
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
//lt2(lt1),this是list2,lt1是list1
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}以及赋值的深拷贝
//lt1=lt3
list<T>& operator=(list<T> lt)//lt是lt3的拷贝（拷贝构造函数创建的深拷贝）,lt与lt3是两个完全独立的链表
{
swap(lt);//交换这个深拷贝lt 和 lt1
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);//交换两个变量的值
std::swap(_size, lt._size);
}函数结束后，lt3 的副本 lt 也会被销毁。
initializer_list初始化链表
C++11支持initializer_list初始化链表，允许使用花括号 {} 传递一组同类型的值。
initializer_list<int> lt = {1,2,3};用initializer_list<T>类型，是为了支持花括号 {} 初始化
list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
} initializer_list<int> lt1({ 1,2,3 });当写 list<int> lt = {1,2,3}; 时，编译器会自动将 {1,2,3} 隐式类型转换为initializer_list<int> 类型的临时对象，然后调用参数类型为initializer_list<T>的构造函数，用这个临时的对象初始化lt1。
list的迭代器与vectoe的迭代器的对比
list进行插入，迭代器不会失效。
std::list<int> l = {1, 3, 4};
auto it = ++l.begin(); // it 指向 3（第二个节点）
l.insert(it, 2); // 在 3 前面插入 2，链表变为 {1,2,3,4}
// it 仍然指向 3（节点地址未变），*it 结果仍为 3（有效）而vector进行插入，有时会触发扩容，将原有元素全部复制到新内存中，导致指向旧内存的原迭代器失效
std::vector<int> v = {1, 3, 4};
v.reserve(3); // 固定容量为 3（避免自动扩容，仅演示移动导致的失效）
auto it = ++v.begin(); // it 指向 3（第二个元素）
v.insert(it, 2); // 插入后变为 {1,2,3,4}，原 3、4 向后移动
// it 原本指向旧位置的 3，但插入后该位置变为 2，it 现在指向 2（失效，因为指向的元素变了）扩容
std::vector<int> v = {1, 2, 3};
auto it = v.begin(); // 指向 1（旧内存地址）
v.push_back(4); // 若容量不足，触发扩容（分配新内存）
// it 指向旧内存（已释放），彻底失效进行删除操作时，list中被删除的节点会失效，其他迭代器仍然有效
std::list<int> l = {1, 2, 3, 4};
auto it1 = l.begin(); // 指向 1
auto it2 = ++l.begin(); // 指向 2（准备删除的节点）
auto it3 = ++++l.begin(); // 指向 3
l.erase(it2); // 删除节点 2，链表变为 {1,3,4}
// it2 失效（指向已释放的节点）
// it1 仍指向 1，it3 仍指向 3（均有效）而vector进行删除时，删除位置后的元素向前挪动，进行覆盖，被删除元素的迭代器失效，以及被删除之后的元素的迭代器也会失效
std::vector<int> v = {1, 2, 3, 4};
auto it1 = v.begin(); // 指向 1
auto it2 = ++v.begin(); // 指向 2（准备删除的元素）
auto it3 = ++++v.begin(); // 指向 3
v.erase(it2); // 删除 2 后，3、4 向前移动，变为 {1,3,4}
// it2 失效（指向被删除的位置）
// it3 原本指向 3，但移动后 3 的位置变了，it3 现在指向的是原 4 的位置（值为 4），失效