一、list的介绍
list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要因素
1、list的使用
1.1、list的构造
构造函数接口说明list()构造空的listlist (size_type n, const value_type& val = value_type构造的list中包含n个值为val的元素list (const list& x)拷贝构造函数list (InputIterator first, InputIterator last)使用迭代器构造list1、list()
list
2、list (size_type n, const value_type& val = value_type())
list
3、list (const list& x)
list
4、list (InputIterator first, InputIterator last)
//1、用lt2的[begin(), end()）左闭右开的区间构造lt
list
//2、以数组为迭代器区间构造lt5
int array[] = { 1,2,3,4 };
list
1.2、迭代器的使用
函数声明接口说明begin返回第一个元素的迭代器end返回最后一个元素下一个位置的迭代器rbegin返回第一个元素的reverse_iterator,即end位置rend返回最后一个元素下一个位置的reverse_iterator,即begin位置
begin和end
begin是返回第一个元素的迭代器，end是返回最后一个元素下一个位置的迭代器。可以通过迭代器进行元素访问：
void test()
{
list
list
while (it != lt.end()) //不能用it < lt.end()
{
cout << *it << " "; //3 3 3 3 3
it++;
}
}
注意：begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin和rend
和先前学到的string类似，rbegin的第一个元素为尾部end位置，rend返回的是begin的位置。
void test()
{
list
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
//list
//用auto自动识别类型：
auto rit = lt.rbegin();
while (rit != lt.rend())
{
cout << *rit << " "; //4 3 2 1
rit++;
}
}
注意：rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
范围for
范围for的底层就是迭代器实现的，利用其也可进行元素访问：
void test()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
for (auto e : lt)
{
cout << e << " ";//1 2 3 4
}
}
1.3、list的元素获取
函数声明接口声明front返回list第一个节点的引用back返回list最后一个节点的引用front和back
front返回第一个元素，back返回最后一个元素
void test()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
cout << lt.front() << endl;//1
cout << lt.back() << endl; //4
}
1.4、list的大小
函数声明接口说明empty检测list是否为空，是返回true，不是返回falsesize返回list中有效节点的个数empty
empty判断list是否为空
void test()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
cout << lt.empty() << endl;//0
}
size
size用来获取list中有些元素个数
void test5()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
cout << lt.size() << endl;//4
}
1.5、list修改的相关函数
函数声明接口声明push_front头插pop_front头删push_back尾插pop_back尾删insert在list position 位置中插入一个元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效数据push_front和pop_front
push_front即头插，pop_front即头删。
void test()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
lt.push_front(0);//头插0
cout << lt.front() << endl;//0
lt.pop_front();//头删
cout << lt.front() << endl;//1
}
push_back和pop_back
push_back即尾插，pop_back即尾删。
void test6()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
lt.push_back(6);//尾插6
cout << lt.back() << endl;//6
lt.pop_back();//尾删
cout << lt.back() << endl;//4
}
insert
list中的insert支持下列三种插入方式：
在指定位置插入一个值为val的元素在指定位置插入n个值为val的元素在指定位置插入一段左闭右开的迭代器区间
void test()
{
list
for (int i = 1; i <= 4; i++)
{
lt.push_back(i);//1 2 3 4
}
//范围查找
list
//1.在指定位置插入一个值为val的元素
//在3的位置插入值7
lt.insert(pos, 7);
for (auto e : lt)
cout << e << " ";//1 2 7 3 4
cout << endl;
//2.在指定位置插入n个值为val的元素
//在3的位置插入5个-1
pos = find(lt.begin(), lt.end(), 3);
lt.insert(pos, 5, -1);
for (auto e : lt)
cout << e << " ";//1 2 7 -1 -1 -1 -1 -1 3 4
cout << endl;
//3.在指定位置插入一段左闭右开的迭代器区间
//在7的位置插入迭代器区间
pos = find(lt.begin(), lt.end(), 7);
list
lt.insert(pos, lt2.begin(), lt2.end());
for (auto e : lt)
cout << e << " ";//1 2 0 0 0 7 -1 -1 -1 -1 -1 3 4
}
erase
erase支持下列两种删除方式：
删除在指定迭代器位置的元素删除指定迭代器区间的元素
void test()
{
list
for (int i = 1; i <= 7; i++)
{
lt.push_back(i);//1 2 3 4 5 6 7
}
list
//1.删除在指定迭代器位置的元素
//删除2位置的元素
lt.erase(pos);
for (auto e : lt)
cout << e << " ";//1 3 4 5 6 7
cout << endl;
//2.删除指定迭代器区间的元素
//删除值为4后的所有元素
pos = find(lt.begin(), lt.end(), 4);
lt.erase(pos, lt.end());
for (auto e : lt)
cout << e << " ";//1 3
}
swap
swap用于交换两个list的内容。
void test()
{
list
list
lt2.swap(lt1);
for (auto e : lt1)
cout << e << " "; //7 7 7
cout << endl;
for (auto d : lt2)
cout << d << " "; //-1 -1 -1 -1 -1
}
clear
clear用来清空list中的有效数据。
void test()
{
list
for (auto e : lt)
cout << e << " ";//-1 -1 -1 -1 -1
cout << endl;
lt.clear();
for (auto e : lt)
cout << e << " ";//空
}
1.6、list的操作函数
函数声明接口说明sort对list进行排序unique删除list中的重复元素sort
list中的sort函数默认排升序。
void test()
{
list
for (int i = 3; i >= -3; i--)
{
lt.push_back(i);//3 2 1 0 -1 -2 -3
}
lt.sort();
for (auto e : lt)
cout << e << " ";//-3 -2 -1 0 1 2 3
}
unique
unique是删除list中的重复元素。
void test()
{
list
lt.push_back(1);
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(3);
lt.push_back(1);
lt.push_back(2);
lt.sort();
lt.unique();
for (auto e : lt)
cout << e << " ";//1 2 3
}
注意：要想对list进行真正的去重，必须先排序。
2、list与vector对比
vectorlist底层结构动态顺序表，一段连续空间带头结点的双向循环链表随机访问支持随机访问，访问某个元素效率O(1)不支持随机访问，访问某个元素效率O(N)插入和删除任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低迭代器原生态指针对原生态指针(节点指针)进行封装迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问二、list的模拟实现
前面list的学习中我们得知，list其实就是一个带头双向循环链表：
现在要模拟实现list，要实现下列三个类：
模拟实现结点类模拟实现迭代器的类模拟list主要功能的类
这三个类的实现层层递进，就好比整个核心list类的模拟实现其基本功能（增加删除……）要建立在迭代器类和结点类均已实现好的情况下才得以完成。
1、结点类接口实现
因为list的本质为带头双向循环链表，所以其每个结点都要确保有下列成员：
前驱指针后继指针data值存放数据
而结点类的内部只需要实现一个构造函数即可。
基本框架
//1、结点类的模拟实现
template
struct list_node//因为成员变量都是公有，就不设计成class了，直接struct
{
list_node
list_node
T _data;//数据
};
构造函数
构造函数这里是用来对其成员变量的一个初始化。
//构造函数
list_node(const T& val = T())//给一个缺省值T()
:_next(nullptr)
, _prev(nullptr)
, _data(val)
{}
2、迭代器类接口实现
因为list的特殊性，其本质是带头双向循环链表，对于链表，我们已然得知其内存空间是不连续的，是通过结点的指针顺序连接，我们不能像先前的string和vector一样直接解引用去访问其数据，结点的指针解引用还是结点，结点指针++还是结点指针，归根结底在于list物理空间不连续。而string和vector的物理空间是连续的，所以这俩不需要实现迭代器类，可以直接使用。
为了能让list像vector一样去解引用，++访问到下一个数据，我们需要单独写一个迭代器类的接口实现，在其内部进行封装补齐相应的功能，而这就要借助运算符重载来完成。
注意：
迭代器又分为正向迭代器和反向迭代器。
2.1、正向迭代器
基本框架
//迭代器类
template
struct __list_iterator//因为成员函数都是公有，就不设计成class了，直接struct
{
typedef list_node
typedef __list_iterator
Node* _node;
};
注意：
这里我迭代器类的模板参数里面包含了3个参数：
template
而后文list类的模拟实现中，我对迭代器进行了两种typedef：
typedef __list_iterator
typedef __list_iterator
根据这里的对应关系：Ref对应的是&引用类型，Ptr对应的是*指针类型，这里如果我是普通对象传过来的迭代器，生成对应的普通迭代器，如果是const对象传递过来的迭代器，会生成对应的const迭代器。
这样做的原因在于避免单独写一个支持不能修改迭代器指向结点数据的类而造成的复用性差。
默认成员函数
这里的默认成员函数我们只需要写构造函数。
析构函数 – 结点不属于迭代器，不需要迭代器释放拷贝构造 – 默认浅拷贝即可赋值重载 – 默认浅拷贝即可
构造函数
这里我们通过结点的指针即可完成构造。通过结点指针构造一个迭代器。
//构造函数
__list_iterator(Node* node)//通过结点指针构造一个迭代器
:_node(node)
{}
*运算符重载
解引用的目的是为了获取结点里的_data数据，因此我们直接return返回结点指向的_data即可。
//*运算符重载
Ref operator*()//结点出了作用域还在，用引用返回
{
return _node->_data;//返回结点指向的数据
}
->运算符重载
假设出现这样的场景，我链表存储的不是内置类型，而是自定义类型，如下：
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1;
int _a2;
};
void test()
{
cpp::list
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
lt.push_back(AA(4, 4));
}
对于内置类型和自定义类型成员的指针，其访问方式都是不同的：
int* *it
AA* (*it). 或者 it->
而这里我们应该重载一个->运算符。以便于访问自定义类型成员的指针的数据。
//->运算符重载
Ptr operator->()
{
return &(operator*());//返回结点指针所指结点的数据的地址
//或者return &_node->_data;
}
实现了->运算符重载后，我们执行it->_a1，编译器将其转换成it.operator->()，此时获得的是结点位置的地址即AA*，而理应还有一个箭头->才能获取数据，也就是这样：it.operator->()->_a1
总结：编译器为了可读性进行优化处理，如果不优化应该是it->->_a1，优化以后，省略了一个箭头->
++运算符重载
++运算符分为前置++和后置++
前置++
迭代器++的返回值还是迭代器，这里的++是为了让指针指向下一个结点，注意前置++是要返回自增后的结点指针。
//前置++
self& operator++()//迭代器++的返回值还是迭代器
{
_node = _node->_next;//直接让自己指向下一个结点即可实现++
return *this;//返回自增后的结点指针
}
后置++
为了区分前置++，后置++通常要加上一个参数以便区别。此外，后置++是返回自增前的结点指针。
//后置++
self operator++(int)//加参数以便于区分前置++
{
self tmp(*this);//拷贝构造tmp
_node = _node->_next;//直接让自己指向下一个结点即可实现++
return tmp;//注意返回tmp，才是后置++
}
–运算符重载
–运算符也分前置–和后置–
前置–
前置–是让此指针指向上一个结点，最后返回自减后的结点指针即可。
//前置--
self& operator--()
{
_node = _node->_prev;//让_node指向上一个结点即可实现--
return *this;
}
后置–
注意传参以区分前置–，最后返回的是自减前的结点指针即可。
//后置--
self operator--(int)//记得传缺省值以区分前置--
{
self tmp(*this);//拷贝构造tmp
_node = _node->_prev;
return tmp;
}
!=运算符重载
这里比较是否不等，是两个迭代器的比较，直接返回两个结点的位置是否不同即可。
//!=运算符重载
bool operator!=(const self& it)
{
return _node != it._node;//返回两个结点指针的位置是否不同即可
}
==运算符重载
这里直接返回俩结点指针是否相同即可。
//==运算符重载
bool operator==(const self& it)
{
return _node == it._node;//返回俩结点指针是否相同
}
2.2、反向迭代器
反向迭代器是一个适配器模式。相较于正向迭代器，反向迭代器有下面三种主要变化：
反向迭代器的++执行的操作是正向迭代器里的–，反向迭代器里的–执行的操作是正向迭代器里的++反向迭代器的*解引用和->操作指向的是前一个数
总代码如下：
template
struct Reverse_iterator
{
Iterator _it;
typedef Reverse_iterator
//构造函数
Reverse_iterator(Iterator it)
:_it(it)
{}
//*运算符重载
Ref operator*()
{
Iterator tmp = _it;
//返回上一个数据
//先减减在调用正向迭代器的operator*函数
return *(--tmp);
}
//->运算符重载
Ptr operator->()
{
//复用operator*，返回上一个数据
return &(operator*());
}
//++运算符重载
Self& operator++()
{
--_it;
return *this;
}
//--运算符重载
Self& operator--()
{
++_it;
return *this;
}
//!=运算符重载
bool operator!=(const Self& s)
{
return _it != s._it;//返回两个结点指针的位置是否不同即可
}
//==运算符重载
bool operator==(const Self& s)
{
return _it == s._it;//返回俩结点指针是否相同
}
};
3、list类接口实现
此接口的核心任务是为了模拟实现list类的一些核心功能，好比如插入删除，迭代器等等。
基本框架
在list类中的唯一成员变量即自定义类型的变量，由先前的结点类构成的头结点：
/*3、模拟实现list的功能类*/
template
class list
{
typedef list_node
public:
//正向迭代器
typedef __list_iterator
typedef __list_iterator
//反向迭代器适配支持
typedef Reverse_iterator
typedef Reverse_iterator
private:
Node* _head;
};
3.1、默认成员函数
构造函数
无参构造：
此目的是为了对哨兵位的头结点_head进行初始化：
//构造函数
list()
{
_head = new Node();//申请一个头结点
_head->_next = _head;//头结点的下一个结点指向自己构成循环
_head->_prev = _head;//头结点的上一个结点指向自己构成循环
}
传迭代器区间构造：
先初始化，再利用循环对迭代器区间的元素挨个尾插即可。
//传迭代器区间构造
template
list(InputIterator first, InputIterator last)
{
list();
while (first != last)
{
push_back(*first);
++first;
}
}
析构函数
这里可以先复用clear函数把除了头结点的所有结点给删除掉，最后delete头结点即可。
//析构函数
~list()
{
clear();
delete _head;//删去哨兵位头结点
_head = nullptr;
}
拷贝构造函数
假设要用lt1拷贝构造lt2。
传统写法：
首先复用empty_init对头结点进行初始化，接着遍历lt1的元素，在遍历的过程中尾插将lt1的元素尾插到lt2上即可。这里直接利用push_back自动开辟空间完成深拷贝。
//传统写法
list(const list
{
//先初始化lt2
list();
//遍历lt，把lt的元素push_back到lt2里头
for (auto e : lt)
{
push_back(e);//自动开辟新空间，完成深拷贝
}
}
现代写法：
这里先初始化lt2自己，再把lt1引用传参传给lt，传lt的迭代器区间构造tmp，复用swap交换头结点指针即可完成深拷贝的现代写法。
//现代写法
list(const list
{
//初始化自己
list();
list
//交换头结点指针即可完成深拷贝现代写法
swap(tmp);
}
赋值运算符重载函数
假设要把lt1赋值给lt2。
这里直接给出现代写法。注意这里传值传参把lt1传给lt自定义类型传值传参调用拷贝构造，拷贝构造完成的是深拷贝生成了lt，复用swap函数交换lt1与lt的头结点指针指向即可，最后返回*this。
//赋值运算符重载（现代写法）
list
{
swap(lt);
return *this;
}
3.2、迭代器相关函数
begin和end
begin的作用是返回第一个位置的结点的迭代器，而第一个结点就是哨兵位头结点的下一个结点，因此，直接return返回_head的_next即可。end的作用就是返回最后一个有效数据的下一个位置的迭代器，而这里对于list指的就是头结点_head的位置。
begin和end均分为普通对象调用和const对象调用，因此要写两个版本。
普通对象调用版
//begin
iterator begin()//begin返回的就是第一个有效数据，即头结点的下一个结点
{
return iterator(_head->_next);//构造了一个匿名对象，通过调用构造函数利用头结点指向的第一个结点作为参数，来返回头结点
//return _head->_next; 也可以这样写
//这会发生隐式类型转换为迭代器类型
}
//end
iterator end()
{
return iterator(_head);//end返回的是最后一个结点的下一个结点，就是头结点_head
//return _head; 也可以这样写
//这会发生隐式类型转换为迭代器类型
}
const对象调用版
//begin
const_iterator begin() const
{
return const_iterator(_head->_next);
//return _head->_next;
}
//end
const_iterator end() const
{
return const_iterator(_head);
//return _head; 也可以这样写
}
rbegin和rend
rbegin就是正向迭代器里end()的位置，rend就是正向迭代器里begin()的位置。
rbegin和rend同样分为普通对象调用和const对象调用：
普通对象调用：
//rbegin()
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
//rend
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const对象调用：
//const反向迭代器
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
3.3、增加的相关函数
insert
实现insert首先创建一个新的结点存储插入的值，接着取出插入位置pos的结点为cur，记录cur的上一个结点位置prev，先链接prev和newnode，再链接newnode和cur即可。最后记得要返回新插入元素的迭代器位置。
//insert，插入pos位置之前
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);//创建新的结点
Node* cur = pos._node; //迭代器pos处的结点指针
Node* prev = cur->_prev;
//prev newnode cur
//链接prev和newnode
prev->_next = newnode;
newnode->_prev = prev;
//链接newnode和cur
newnode->_next = cur;
cur->_prev = newnode;
//返回新插入元素的迭代器位置
return iterator(newnode);
}
补充：list的insert不存在野指针和意义变了的迭代器失效问题。
push_back尾插
法一：
首先，创建一个新结点用来存储尾插的值，接着找到尾结点。将尾结点和新结点前后链接构成循环，再将头结点和新结点前后链接构成循环即可。
//尾插
void push_back(const T& x)
{
Node* tail = _head->_prev;//找尾
Node* newnode = new Node(x);//创建一个新的结点
//_head tail newnode
//使tail和newnode构成循环
tail->_next = newnode;
newnode->_prev = tail;
//使newnode和头结点_head构成循环
newnode->_next = _head;
_head->_prev = newnode;
}
法二：
这里也可以复用insert函数，当insert中的pos位置为哨兵位头结点的位置时，实现的就是尾插，因为insert插入是在pos位置前插入，而pos位哨兵位头结点时，在其前一个位置（尾部）插入就是实现了尾插。
//尾插
void push_back(const T& x)
{
//法二：复用insert
insert(end(), x);
}
push_front头插
直接复用insert函数，当pos位置为begin()时，获得的pos就是第一个有效结点数据，即可满足头插。
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
3.4、删除的相关函数
erase
erase删除的是pos位置的结点，首先取出pos位置的结点为cur，记录cur上一个结点的位置为prev，再记录cur下一个结点的位置为next，链接prev和next，最后delete释放cur的结点指针即可。最后记得返回删除元素后一个元素的迭代器位置。
//erase
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
//prev cur next
//链接prev和next
prev->_next = next;
next->_prev = prev;
//delete要删去的结点
delete cur;
//返回删除元素后一个元素的迭代器位置
//return next;
return iterator(next);
}
pop_back尾删
直接复用erase即可，当pos位置为–end()时，pos就是最后一个结点的位置，实现的就是尾删。
//尾删
void pop_back()
{
erase(--end());
}
pop_front头删
直接复用erase即可，当pos位置为begin()时，pos就是第一个有效数据，实现的就是头删。
//头删
void pop_front()
{
erase(begin());
}
3.5、其它函数
clear清除
clear的作用是清除除了头结点外的所有结点，这里可以复用erase并通过遍历的方式一个一个删除。
//clear清除
void clear()
{
//复用erase
iterator it = begin();
while (it != end())
{
it = erase(it);//用it接收删除后的下一个结点的位置
//不能直接++it,因为此时it已经被释放了，迭代器失效了，所以直接接受erase的返回值
//即可获取下一个节点的地址
}
}
empty_init空初始化
此函数的作用把哨兵位的头结点开出来，再对齐初始化。该函数是库中的。
//空初始化 对头结点进行初始化
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
构造函数可以使用该函数初始化。
swap交换
对于链表的swap，直接交换头结点指针的指向即可完成。直接复用库函数的swap即可。
//swap交换函数
void swap(list
{
std::swap(_head, lt._head);//交换头指针
}