list容器（详解）

list的介绍及使用（了解，后边细讲）

1.1 list的介绍（双向循环链表）

https://cplusplus.com/reference/list/list/?kw=list（list文档介绍）

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

1.2 list的使用（可以对照模拟实现看，重要的都有，后边模拟实现都会讲）

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.2.1 list的构造

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

【注意】

1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

list中还有一些操作，需要用到时大家可参阅list的文档说明。

list的迭代器失效

注意，insert不会失效，迭代器依旧指向原来位置，erase会失效（删除后返回下一个地址），跟vector的迭代器失效类比，都是因为没有接收删除后的迭代器。insert不会失效，因为插入后返回新的节点地址，本身就指向新节点，不会失效

错误代码：
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
其赋值l.erase(it); ++it;}
}
改正后：
// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);两种写法都对}
}

list的反向迭代器

ReverseIterator.h
template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator cur;ReverseIterator(Iterator it):cur(it){ }Self& operator++(){--cur;return *this;}Ref operator*(){Iterator tmp = cur;--tmp;return *tmp;}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return cur != s.cur;}
};
List.h

在list类内部多了一些改动，将反向迭代器的类重命名，并且新加两个成员函数

test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<list>using namespace std;#include"List.h"int main()
{jzy::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);jzy::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}
可以看到反向迭代器起了作用，下面我来讲解反向迭代器的原理

反向迭代器可以理解成封装了正向迭代器，正向迭代器又封装了原生指针，反向迭代器++等价于正向迭代器--，反向迭代器解引用相当于正向迭代器--再解引用

因为反向迭代器的开始是正向迭代器结束位置，结束是正向的开始，所以反向迭代器要先--在解引用才是正确的值

反向迭代器的->也就是*拿到存放的值再取地址，和之前讲的是一个道理
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;//typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}
反向迭代器在list类那里要多加一些东西，重命名反向迭代器这个类，当是普通反向迭代器的时候实例化iterator，T&,T*，当是const反向迭代器的时候，实例化参数是const_iterator,const T&,const T*

总体来讲，可以把反向迭代器看成适配器，当实例化参数是普通迭代器，会按照普通迭代器的行为进行操作，当参数是const时，会调用const的操作

list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

list模拟实现讲解（超详细）

定义结点结构体，结构体成员是前仆后继指针和元素data，还要写一个构造函数用来初始化结点

迭代器封装为一个类，类定义的对象存放每个节点的地址，也就是_node，相当于迭代器指针被封装成了一个类里存放，typedef是将类型重命名，将长的类型重命名为短的，记住类名不是类型，类名<类型>才是类型

这里模版有三个参数，第一个T是实例化类型，第二个和第三个参数是为了*和->，const类型会匹配T,constT& ,constT* ，正常类型会匹配T,T&,T*

这里将原生指针封装了一层包装在一个类里边，类定义的对象会通过操作指针前后移动来操作结点，解引用拿到对应结点的值，或者->拿到对应的地址

迭代器构造函数，当返回值是iterator类型时，会构造一个临时对象来操作

迭代器++，--，和日期类的原理类似，++it是当前指针往后走一步，this是it的地址，然后返回++之后的值，后置++，参数多传一个int就行，构造一个局部对象，指针向后走一步，返回走之前的值，迭代器--和++同理，无非是向前走

operator*是（*it）相当于拿到对应的值，我们就把it当成指针，*it当成解引用地址即可，这里是把指针封装到类里边，和前边string和vector的指针有所区分；->箭头相当于拿到存放对象的地址，当在list内部存放结构体时会用到

最简单的两个运算符重载，当判断不等于的时候会用到

list类要把上边两个类typedef后的类型写上去，方便等会用

迭代器的重载，当我们用begin（）或者end（）的时候，会调用这四个重载，普通对象调用普通迭代器，返回普通可修改指向对象的迭代器（这个对象可以用类名（），也可以直接返回Node*的结点指针（单参数的构造函数支持隐式类型转换），这两个写法都会生成一个临时对象，然后进行使用），const类型调用const迭代器，返回const不可修改指向对象的迭代器（慢慢理解这部分，其实没有想象的那么难）

list类的私有成员是_head，充当一个指针用来声明第一个哨兵位头结点

默认构造是初始化一个哨兵位头结点，结点内部存放前仆后继指针和data值（是某个类型的默认构造），然后让_head指向第一个哨兵位结点，并且_next和_prev都指向自己，完成哨兵位结点的初始化

析构函数先用clear清理，删除除了哨兵位结点的剩余存放有效数据的结点（释放了空间），最后释放哨兵位结点空间，_head置空就OK

拷贝构造，先初始化一个哨兵位结点，然后将要构造的对象内容依次给给e，尾插到新对象后边

赋值拷贝，先拷贝构造一个lt，将lt和新对象交换，lt是局部对象，出作用域会调用析构函数，新对象引用返回，完成赋值拷贝

insert插入，参数是迭代器指针（生成临时对象+2次拷贝构造）和要插入的值，cur指向要插入位置，prev存放要插入位置前边的指针，new一个新节点是要插入的新结点

三个指针相对位置是这样的，一般都是在某个位置之前插入，所以是这样的关系，然后按顺序链接这三个位置，前一个位置的后继指针和后一个位置的前驱指针都指向中间位置，最后返回插入节点的迭代器（单参数构造函数支持隐式类型转换）

删除很简单，不能删除哨兵位结点，找到要删除节点，记录要删除结点的前一个和后一个，链接两边的节点，最后释放要删除节点的空间，返回下一个节点的迭代器（会隐式类型转换成iterator类型的对象）

尾插，可以自己重新写逻辑，也可以复用insert逻辑，将第一个参数换成最后一个位置的迭代器，相当于在哨兵位节点之前插入，效果是一样的

头插，尾插，尾删是一样的，复用insert，erase逻辑就行

这部分在c语言实现数据结构链表那里讲的很详细了，想看的可以看看

代码样例讲解

这是一个很基础的尾插和打印对象逻辑，可以用第一个迭代器打印，也可以用第二个，范围for打印（范围for底层就是迭代器，无脑替换成迭代器进行打印），可以看到*it和it++，都是我们封装成类的功劳，原理很简单前面讲过

测试插入删除逻辑，可以看到不管是头插，头删，尾插，尾删都很清晰明了，clear是直接删除有效结点只剩哨兵位，所以打印不出来

可以看到，拷贝构造和赋值拷贝都完成了使命，前边讲的很详细，这里不再赘述

这里主要测试普通迭代器和const迭代器，各自调用各自，const迭代器不可修改对象，普通迭代器可以修改对象

最后一个样例，插入AA类对象，*it是拿到存放的结构体变量，.操作符访问结构体成员，拿到1:1，打印第二行是编译器会将*it转换成it.operator*()，效果是一样的

->箭头访问操作符会特殊处理一个箭头可以当做两个->->，并且编译器会转换成it.operator->()->_a1去访问，会特殊处理，这里当成特殊处理就好

list的模拟实现(代码）

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

test.cpp


#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;#include"List.h"namespace jzy
{void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(5);lt.push_front(0);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(10);lt.push_back(20);for (auto e : lt){cout << e << " ";}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> copy(lt);for (auto e : copy){cout << e << " ";}cout << endl;list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt = lt1;for (auto e : copy){cout << e << " ";}cout << endl;}void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;}struct AA{int _a1;int _a2;AA(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){}};void test_list5(){list<AA> lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));list<AA>::iterator it = lt.begin();cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;cout << endl;}}int main(){jzy::test_list1();return 0;}

list.h

#pragma once
#include<assert.h>namespace jzy
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* x):_node(x){}// ++itself& operator++(){_node = _node->_next;return *this;}// it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//template<class T>//struct __list_const_iterator//{//	typedef ListNode<T> Node;//	typedef __list_const_iterator<T> self;//	Node* _node;//	__list_const_iterator(Node* x)//		:_node(x)//	{}//	// ++it//	self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	// it++//	self operator++(int)//	{//		self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	self operator--(int)//	{//		self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	const T& operator*()//	{//		return _node->_data;//	}//	bool operator!=(const self& s)//	{//		return _node != s._node;//	}//	bool operator==(const self& s)//	{//		return _node == s._node;//	}//};template<class T>class list{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}// lt1 = lt2;// list<T>& operator=(const list<T>& lt)/*list<T>& operator=(list<T>& lt){if (this != &lt){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}//list& operator=(list lt)list<T>& operator=(list<T> lt){swap(lt);return *this;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// vector insert会导致迭代器失效// list会不会？不会iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;//return iterator(newnode);return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}private:Node* _head;};
}